Solucion a quiz de google
Para hacer la historia corta:Soplín fue a una charla de Google y publicó un slide con una pregunta típica de las entrevistas laborales en Google:
Este quiz provocó un total alboroto chichero solucionando el problemita. Yo había publicado ya un rudimento del algoritmo y la respuesta, pero había dejado pendiente detallar la solución, asi que aqui va:
Y la solución programada y lista para usar:
#!/usr/bin/env python
def findsteps(numpisos):
res = 1
while True:
l = []
val = 0
for step in range(res, 0, -1):
val += step
if val >= numpisos:
l.append(numpisos)
break
l.append(val)
if val >= numpisos:
break
res += 1
return l
if __name__ == '__main__':
import sys
if len(sys.argv) > 1:
try:
numpisos = int(sys.argv[1])
except ValueError, errmsg:
sys.stdout.write('ERROR: num de pisos debe ser un entero\n')
sys.exit(-1)
else:
numpisos = 100
if numpisos < 1:
sys.stdout.write('ERROR: num de pisos debe ser un >= 1\n')
sys.exit(-1)
print '# Pisos-intervalo para edificio de %d pisos: \n' % (numpisos,)
res = findsteps(numpisos)
print res
print '# %d intentos en el peor escenario' % (res[0],)
Con este programita pueden encontrar la solución óptima para un edificio de cualquier altura, pero veamos los pasos necesarios para el edificio de 100 pisos del problema original:
# Pisos-intervalo para edificio de 100 pisos:
[14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100]
# 14 intentos en el peor escenario
Cumplido mis queridos chicheros, ahora espero que Soplín cumpla su promesa de publicar las otras preguntas!
(y creo que es aparente que si las empresas locales hicieran este tipo de preguntas en vez de "tiene un mcse?", el nivel de empleo local sería CERO!)
Por cierto: GRACIAS TIO KNUTH! No hubiera podido resolver esto sin ti!
Actualización: Antonio Ognio, demostrando sus capacidades de docente, hace una explicación for dummies del algoritmo del problema. Denle una mirada si no la captaron con mi dibujito y el código en Python ;-)
Actualización2: Optimizaciones, algoritmo O(n^2) es ahora O(1)
tags: google, entrevista, solucion, edificio, knuth, taocp, nerd
Etiquetas: edificio, entrevista, google, knuth, nerd, solucion, taocp
About this entry
You’re currently reading “
- Published:
- 11/09/2007 03:31:00 AM
- by tabo
- Te gustó este post?
13 Comments (Publicar un comentario en la entrada)