Cómo resolver el acertijo de los reclutadores de Google sobre lanzar huevos desde un edificio

Hay muchos acertijos geniales para programar entrevistas de trabajo. Mi favorito también es conocido como uno de los favoritos entre los reclutadores de Google:

Trabajas en un edificio de 100 pisos y obtienes 2 huevos idénticos. Debes determinar el piso más alto en el que se puede dejar caer un huevo sin romperse. Encuentre un algoritmo que minimice el número de lanzamientos en el peor de los casos.

Podemos hacer algunas suposiciones:

  • Si un huevo no se rompe cuando se deja caer desde algún piso, entonces no se romperá cuando se deje caer desde pisos inferiores.
  • Un huevo que sobrevive a una caída se puede volver a utilizar.
  • Debe desecharse un huevo roto.
  • El efecto de una caída es el mismo para todos los huevos.
  • Si un huevo se rompe al caer, se rompería si se dejara caer desde un piso más alto.

La mayoría de la gente escribe algunos algoritmos para resolver este acertijo (y nosotros también lo haremos), pero en realidad hay una solución fácil.

Respuesta más simple

La forma más sencilla de obtener el piso mínimo es tirar un huevo desde el primer piso, luego desde el segundo y así sucesivamente. De esta manera cuando el huevo finalmente se rompa sabremos que este es el piso. Este es un algoritmo confiable, pero en el peor de los casos se necesitarían 100 lanzamientos.

Lo importante a notar es que es el único algoritmo confiable cuando solo tienes un huevo. Por lo tanto, debe comenzar a usar este algoritmo cuando rompa el primer huevo.

Respuesta intuitiva

De esta manera, nuestro primer huevo debe usarse para dividir el rango de 100 pisos en rangos más pequeños de la manera más eficiente posible. Por lo tanto, una respuesta intuitiva y popular es lanzar el primer huevo desde el 1 / enésimo de los pisos para verificar. Por ejemplo 1/3. Entonces, el algoritmo se verá así:

  • Tira el huevo del piso 33. Si se rompe, revisamos los primeros 32 pisos con el segundo huevo.
  • De lo contrario, tiramos el huevo desde 33 + (67 * 1/3) = piso 55. Si se rompe, revisamos los pisos 34 a 55 con el segundo huevo.
  • ...

El peor escenario para 1/3 es max (33, 24,…) = 33. De esta manera podríamos encontrar una n perfecta que optimice el número de lanzamientos usando alguna programación dinámica. Esta es una solución valiosa que presenta el pensamiento de programación, pero no es una solución óptima.

Solución perfecta

Para comprender la solución perfecta, debemos comprender el equilibrio que se utiliza para calcular el número de lanzamientos en el peor de los casos:

Donde F (n) es el siguiente piso desde el que tiramos el primer huevo

Si introducimos la siguiente variable:

entonces el equilibrio sigue:

La solución óptima es cuando todos los argumentos de esta función máxima son iguales. Como lo logramos? Mirando desde el final, el último D (n) va a ser 1, porque finalmente llegaremos al punto donde solo hay un piso para el primer huevo. Por lo tanto, D (n-1) debería ser igual a 2 porque tiene un lanzamiento menos del primer huevo.

Vemos entonces que el primer huevo debe ser lanzado finalmente desde el piso 99, previamente de 99-2 = 97, previamente de 97-3 = 94, 90, 85, 79, 72, 64, 55, 45, 34, 22 y el noveno piso. ¡Esta es una solución óptima! De esta manera, necesitamos 14 lanzamientos en el peor de los casos (la diferencia más pequeña es 13, pero tuvimos que hacer un lanzamiento adicional en el noveno piso).

La ecuación simple para encontrar la respuesta es la siguiente:

Donde fes el número de pisos. Esto se puede simplificar a:

Eso es igual a:

Cheque

Bien, tenemos una solución y podemos calcularla sin ayuda. Es hora de comprobar si es correcto. Escribiremos un programa Kotlin simple para eso. Primero, expresemos cómo contar el número de lanzamientos para alguna decisión. Cuando hay 2 pisos o menos, necesitamos tantos tiros como pisos queden. De lo contrario, deberíamos usar el equilibrio ya presentado:

fun maxThrows(floorsLeft: Int, nextFloor: Int): Int = if (floorsLeft <= 2) floorsLeft else maxOf(nextFloor, bestMaxThrows(floorsLeft - nextFloor) + 1)

Hemos utilizado aquí la bestMaxThrowsfunción. Es una función hipotética que devuelve un número de lanzamientos suponiendo que las siguientes decisiones sean perfectas. Así es como podemos definirlo:

fun bestMaxThrows(floorsLeft: Int): Int = maxThrows(floorsLeft, bestNextStep(floorsLeft))

Nuevamente, acabamos de delegar la responsabilidad de la optimización del siguiente piso a bestNextStepfunción. Esta función nos da el mejor siguiente paso. Podemos definirlo simplemente: cuando queden 2 o menos pisos, lanzaremos un huevo desde el primer piso. De lo contrario, debemos verificar todas las opciones y encontrar la óptima. Aquí está la implementación:

val bestNextStep(floorsLeft: Int): Int = if (floorsLeft <= 2) 1 else (1..floorsLeft) .toList() .minBy { maxThrows(floorsLeft, it) }!!

Tenga en cuenta que esta función usa la maxThrowsfunción, por lo que tratamos con la recurrencia. No es un problema, porque cuando bestNextStepllama maxThrows, siempre lo llama con un valor menor que floorsLeft(porque nextFloorsiempre es mayor que 0). Antes de usarlo, agregaremos almacenamiento en búfer para acelerar los cálculos:

val bestNextStep: (Int) -> Int = memorise { floorsLeft -> if (floorsLeft <= 2) 1 else (1..floorsLeft) .toList() .minBy { maxThrows(floorsLeft, it) }!!}fun maxThrows(floorsLeft: Int, nextFloor: Int): Int = if (floorsLeft  Int = memorise { floorsLeft -> maxThrows(floorsLeft, bestNextStep(floorsLeft))}fun  memorise(f: (V) -> T): (V) -> T { val map = mutableMapOf
    
     () return { map.getOrPut(it) { f(it) } }}
    

Primero, podemos comprobar si devuelve el mismo resultado que el que hemos calculado:

fun main(args: Array) { print(bestMaxThrows(100)) // Prints: 14}

La respuesta es buena :) Veamos nuestros siguientes pasos:

fun main(args: Array) { var floor = 0 while (floor < 100) { val floorsLeft = 100 - floor val nextStep = bestNextStep(floorsLeft) floor += nextStep print("$floor, ") }}

Resultado:

9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100,

¡Cómo calculamos! Agradable: D

Imagen más grande

Now we have a nice algorithm that we can use for a lot of similar problems. For example, we can change it a little to calculate the number of throws for the most probabilistic scenario. We can also check how this minimal number of throws will differ depending on the height of the building. Here is a graph answering that:

Conclusion

You are now better prepared for your Google interview, but it is more important that you are now better prepared for general algorithmic thinking. This algorithm presented a nice, functional approach. A similar approach can be used for lot’s of different problems in our daily jobs.

I hope that you liked it. Clap to say thank you and to help others find this article. More interesting materials on my Twitter. Reference me using @marcinmoskala. If you are interested in Kotlin, check out Kotlin Academy and Kotlin Academy portal for Kotlin puzzlers and advanced materials.