¿Cómo interpretar las preguntas de las entrevistas de inteligencia en Microsoft, Google y Apple?

Hay un edificio que tiene 100 pisos de altura. Si se cae desde el enésimo piso o más, el huevo se romperá. Si se arroja desde pisos por debajo del enésimo piso, no se romperá. Le dan 2 huevos, encuentre N y exija que se arroje la cantidad mínima de huevos en el peor de los casos. ?

Descubrimos que no importa cómo arrojes el Huevo 1 y el Huevo 2, deben estar entre el "piso roto" y el siguiente piso más alto que no se romperá por las escaleras piso por piso (. de menor a mayor). Por ejemplo, si el Huevo 1 no se rompió al caer desde los pisos 5 y 10, pero se rompió al caer desde el piso 15, entonces, en el peor de los casos, el Huevo 2 debe intentar caer desde los pisos 11, 12, 13 y 14. pisos. Tíralo abajo.

Cómo hacerlo

Primero, intentemos lanzar huevos comenzando desde el piso 10, luego desde el piso 20, y así sucesivamente.

q Si el huevo 1 se rompe cuando se arroja escaleras abajo por primera vez (piso 10), entonces es necesario arrojarlo hasta 10 veces.

q Si el Huevo 1 se rompe después de ser arrojado escaleras abajo por última vez (piso 100), entonces habrá que tirarlo hasta 19 veces (piso 10, 20,..., 90, 100). , y luego del piso 91 al 99).

Está bien, pero solo consideramos el peor de los casos. Deberíamos realizar un "equilibrio de carga" para que la cantidad de huevos arrojados sea más uniforme en estas dos situaciones.

Nuestro objetivo es diseñar un método de lanzamiento de huevos para que al lanzar los huevos 1, no se rompan hasta la primera o la última vez que se arrojen escaleras abajo. Cuanto más estable sea el número de veces, más. mejor.

(1) El método de equilibrio de carga perfecto debería ser que el número de veces que se lanza el huevo 1 más el número de veces que se lanza el huevo 2 sean los mismos en cualquier momento, sin importar en qué piso se deje caer el huevo 1. desde y se rompe de.

(2) Si existe este método de lanzamiento, cada vez que se lanza el huevo 1 una vez más, el huevo 2 se puede lanzar una vez menos.

(3) Por lo tanto, cada vez que se lanza el huevo 1, se debe reducir el número de veces que es posible que sea necesario arrojar el huevo 2 por las escaleras. Por ejemplo, si el huevo 1 se arroja primero desde el piso 20 y luego desde el piso 30, es posible que sea necesario lanzar el huevo 2 9 veces. Si se vuelve a tirar el huevo 1, debemos reducir el número de veces que se tira el huevo 2 por las escaleras a 8 veces. En otras palabras, debemos tirar el huevo 1 desde el piso 39.

(4) De esto se puede ver que el huevo 1 debe lanzarse hacia abajo comenzando desde el

(5) Resuelve la ecuación X (X-1) (X-2)… 1 = 100, y obtiene X (X 1) / 2 = 100 → X = 14.

Empezamos por el piso 14, luego el piso 27, luego el piso 39, y así sucesivamente. En el peor de los casos, hay que tirar los huevos 14 veces.

Como ocurre con muchos otros problemas de maximización/minimización, la clave para este tipo de problemas es "equilibrar el peor de los casos". ?