Cómo resolver el enigma de los reclutadores de Google sobre tirar 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 descubrir el piso más alto donde 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 cae desde un piso, entonces no se romperá cuando se caiga desde cualquier piso inferior.
  • Un huevo que sobrevive a una caída puede ser usado nuevamente.
  • Un huevo roto debe ser descartado.
  • El efecto de una caída es el mismo para todos los huevos.
  • Si un huevo se rompe cuando se cae, se rompería si se deja caer desde un piso más alto.

La mayoría de la gente escribe algunos algoritmos para resolver este rompecabezas (y lo haremos también), 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 lanzar 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 tomaría 100 lanzamientos.

Lo importante a tener en cuenta es que es el único algoritmo confiable cuando solo tiene 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 tirar el primer huevo desde 1 / n-th de los pisos para verificar. Por ejemplo 1/3. Entonces el algoritmo se verá así:

  • Tira el huevo desde el piso 33. Si se rompe, verificamos 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 usando el segundo huevo.
  • ...

El peor de los casos para 1/3 es max (33, 24, ...) = 33. De esta manera, podríamos encontrar una n perfecta que optimice el número de lanzamientos utilizando 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 entender la solución perfecta, necesitamos entender el equilibrio que se usa para calcular el número de lanzamientos en el peor de los casos:

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

Si presentamos la siguiente variable:

entonces sigue el equilibrio:

La solución óptima es cuando todos los argumentos de esta función máxima son iguales. Como lo logramos? Mirando desde el final, la última D (n) 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 arrojarse finalmente desde el piso 99, previamente desde 99-2 = 97, previamente desde 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 f es el número de pisos. Esto se puede simplificar para:

Eso es igual a:

Comprobar

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

fun maxThrows (plantas Izquierda: Int, nextFloor: Int): Int =
  si (pisos Izquierda <= 2) pisos Izquierda
  sino maxOf (nextFloor, bestMaxThrows (plantasLeft - nextFloor) + 1)

Hemos utilizado aquí la mejor función MaxThrows. Es una función hipotética que devuelve varios lanzamientos, suponiendo que las siguientes decisiones son perfectas. Así es como podemos definirlo:

diversión bestMaxThrows (plantas Izquierda: Int): Int =
  maxThrows (plantas Izquierda, bestNextStep (plantas Izquierda))

Nuevamente, acabamos de delegar la responsabilidad de la optimización del siguiente piso a la función bestNextStep. Esta función nos da el mejor próximo paso. Podemos definirlo simplemente: cuando quedan 2 o menos pisos, arrojaremos 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 =
  si (pisos Izquierdo <= 2) 1
  más (1..pisos Izquierda)
        .Listar()
        .minBy {maxThrows (plantas, izquierda)} !!

Tenga en cuenta que esta función utiliza la función maxThrows, por lo que nos ocupamos de la recurrencia. No es un problema, porque cuando bestNextStep llama a maxThrows, siempre lo llama con un valor menor que floorLeft (porque nextFloor siempre es mayor que 0). Antes de usarlo, agregaremos almacenamiento en búfer para acelerar los cálculos:

val bestNextStep: (Int) -> Int = memorize {floorsLeft ->
  si (pisos Izquierdo <= 2) 1
  más (1..pisos Izquierda)
        .Listar()
        .minBy {maxThrows (plantas, izquierda)} !!
}

fun maxThrows (plantas Izquierda: Int, nextFloor: Int): Int =
  si (pisos Izquierda <= 2) pisos Izquierda
  sino maxOf (nextFloor, bestMaxThrows (plantasLeft - nextFloor) + 1)


val bestMaxThrows: (Int) -> Int = memorizar {floorsLeft ->
  maxThrows (plantas Izquierda, bestNextStep (plantas Izquierda))
}

divertido  memorizar (f: (V) -> T): (V) -> T {
    val map = mutableMapOf  ()
    return {map.getOrPut (it) {f (it)}}
}

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

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

La respuesta es buena :) Veamos nuestros próximos pasos:

fun main (args: Array ) {
    piso var = 0
    mientras que (piso <100) {
        Val pisos Izquierda = 100 - piso
        val nextStep = bestNextStep (floorsLeft)
        floor + = nextStep
        print ("$ piso")
    }
}

Resultado:

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

Justo como lo calculamos! Niza: D

Imagen más grande

Ahora tenemos un buen algoritmo que podemos usar para muchos problemas similares. Por ejemplo, podemos cambiarlo un poco para calcular el número de lanzamientos para el escenario más probabilístico. También podemos comprobar cómo este número mínimo de lanzamientos diferirá según la altura del edificio. Aquí hay un gráfico que responde que:

Conclusión

Ahora está mejor preparado para su entrevista en Google, pero es más importante que esté mejor preparado para el pensamiento algorítmico general. Este algoritmo presenta un enfoque agradable y funcional. Un enfoque similar se puede utilizar para muchos problemas diferentes en nuestros trabajos diarios.

Espero que les haya gustado. Aplauda para agradecer y ayudar a otros a encontrar este artículo. Más materiales interesantes en mi Twitter. Referenciame usando @marcinmoskala. Si está interesado en Kotlin, eche un vistazo a Kotlin Academy y al portal de Kotlin Academy para conocer los rompecabezas y materiales avanzados de Kotlin.