algorithm - what - Dos canicas y un edificio de 100 pisos

traducir de ingles a español (9)

¿Cada uno se rompe cuando se cae desde la misma altura, o son diferentes?

Si son iguales, voy al piso 50 y tiro el primer mármol. Si no se rompe, voy al piso 75 y hago lo mismo, siempre y cuando no se rompa, sigo subiendo un 50% de lo que queda. Cuando se rompe, vuelvo a uno más alto que donde estaba anteriormente (así que si se rompió en el piso 75, vuelvo al piso 51) y tiro el segundo mármol y me muevo por el piso a la vez hasta que se rompe, en ese punto sé el piso más alto desde donde puedo caer sin rotura de mármol.

Probablemente no sea la mejor respuesta, tengo curiosidad por ver cómo responden los demás.

Una de esas preguntas de entrevista de programación clásica ...

Le dan dos canicas y le dicen que se romperán cuando caigan desde cierta altura (y presumiblemente no sufrirán daños si caen desde debajo de esa altura). Luego lo llevan a un edificio de 100 pisos (presumiblemente más alto que la altura determinada), y le piden que busque el piso más alto desde el que pueda tirar una canica sin romperlo de la manera más eficiente posible.

Información extra

Debes encontrar el piso correcto (no un rango posible)
Las canicas están garantizadas para romperse en el mismo piso
Suponga que le toma cero tiempo cambiar de piso: solo el número de gotas de mármol
Suponga que el piso correcto se distribuye al azar en el edificio

Creo que la verdadera pregunta es cuán precisa es la respuesta. Porque tu eficiencia realmente va a depender de eso.

Voy a estar de acuerdo con Justin si quieres un 100% de precisión en los mármoles y una vez que el primer mármol te rompa tendrás que subir de piso en piso desde el último piso "bueno" conocido hasta que descubras qué piso es el ganador." Tal vez incluso incluya algunas estadísticas y comience en el piso 25 en lugar del piso 50, de modo que su peor escenario sería 24 en lugar de 49.

Si su respuesta puede ser más o menos un piso o dos, entonces podría haber algunas optimizaciones.

En segundo lugar, ¿caminar contra las escaleras cuenta en contra de su eficiencia? En ese caso, siempre suelte ambos mármoles y levante ambos mármoles en cada viaje arriba / abajo.

Personalmente, no soy un gran admirador de tales preguntas de rompecabezas, prefiero los ejercicios de programación reales en las entrevistas.

Dicho eso, primero dependería de si puedo decir si están rotos o no en el piso donde los tiro. Presumiré que puedo.

Subiría al segundo piso, dejaría caer la primera canica. Si se rompiera probaría el primer piso. Si eso se rompiera, sabría que no era piso.

Si el primero no se rompía, iría al cuarto piso y me iría de allí. Si eso se rompía, bajaba y cogía la otra canica, luego bajaba al 3er piso, rompiendo o no, sabía cuál era el límite.

Si ninguno de los dos se rompiera, obtendría ambos y haría el mismo proceso, esta vez comenzando en el 6 ° piso.

De esta manera, puedo omitir cualquier otro piso hasta que obtenga una canica que se rompa.

Esto se optimizaría si el mármol se rompe antes ... Supongo que probablemente haya una cantidad óptima de pisos que podría omitir para obtener el máximo de cada salto ... pero si uno se rompe, tendré que revisar cada piso individualmente. desde el primer piso sobre el último piso conocido ... lo que por supuesto sería un dolor si saltaba demasiados pisos (lo siento, no voy a encontrar la solución óptima en este momento).

Idealmente, quisiera una bolsa entera de canicas, luego podría usar un algoritmo de búsqueda binario y dividir el número de pisos a la mitad con cada gota ... pero entonces, esa no era la pregunta, ¿o sí?

Suelta el primer mármol del 3er piso. Si se rompe, sabes que es el piso 1 o 2, así que suelta el otro mármol del piso 2. Si no se rompe, has encontrado que el piso 2 es el más alto. Si se rompe, has encontrado que el piso 1 es el más alto. 2 gotas

Si cayendo desde el tercer piso no rompe el mármol, déjalo caer desde el piso 6. Si se rompe, sabes que el piso 4 o 5 es el más alto. Suelta el segundo mármol del piso 5. Si no se rompe, has encontrado que 5 es el más alto. Si lo hace, el piso 4 es el más alto. 4 gotas

Continuar.

3 plantas - máximo de 2 gotas

6 pisos - máximo de 4 gotas

9 pisos - máximo de 6 gotas

12 pisos - un máximo de 8 gotas

etc.

3x pisos - máximo de 2x gotas

Entonces, para un edificio de 99 pisos tendrías un máximo de 66 caídas. Y ese es el máximo. Probablemente tendrías menos gotas que eso. Ah, y 66 es el máximo para una construcción de 100 pisos también. Solo necesitarías 66 caídas si el piso de descanso fuera el piso 98 o 97. Si el piso de descanso fuera 100, usarías 34 caídas.

A pesar de que dijiste que no importaba, probablemente requeriría la menor cantidad de caminar y no tienes que saber qué tan alto es el edificio.

Parte del problema es cómo defines la eficiencia. ¿Es más "eficiente" tener siempre una solución en menos de x gotas, o es más eficiente tener una buena oportunidad de tener una solución en y cae donde y <x con la advertencia de que podrías tener más de x gotas? ?

Suelta la primera canica en el piso 10, 20, 30, etc. hasta que se rompa, salta de nuevo al último piso bueno conocido y comienza a soltar canicas desde allí un piso a la vez. El peor caso es 99 siendo el piso mágico y siempre puedes encontrarlo en 19 gotas o menos.

Lo interesante aquí es cómo puedes hacerlo en la menor cantidad posible de gotas. Ir al piso 50 y dejar caer el primero sería desastroso si el piso que rompe es el número 49, lo que significa que tenemos que hacer 50 caídas. Deberíamos dejar caer la primera canica en el piso n, donde n es la cantidad máxima de gotas requerida. Si el mármol se rompe en el piso n, es posible que tengamos que hacer n-1 gotas después de eso. Si el mármol no se rompe, subimos al piso 2n-1 y si se rompe aquí tenemos que soltar el segundo mármol n-2 veces en el peor de los casos. Continuamos así hasta el piso 100 y tratamos de romperlo en 3n-2, 4n-3 ...
y n + (n-1) + (n-2) + ... 1 <= 100
n = 14 ¿Se requieren las caídas máximas?

Lo primero que haría es usar el algoritmo muerto simple que comienza en el piso 1. Deja caer el mármol de un piso a la vez hasta que llegue a 100 o se rompa el mármol.

Luego preguntaría por qué debería perder tiempo optimizándolo hasta que alguien pueda demostrar que será un problema. Demasiadas veces las personas se obsesionan con encontrar el algoritmo complicado perfecto cuando uno mucho más simple resolverá el problema. En otras palabras, no optimices las cosas hasta que las necesites.

Esta podría ser una pregunta capciosa para ver si eres una de esas personas que pueden hacer una montaña desde una colina de topo.

Esto se puede hacer mejor con solo 7 canicas.

Entonces, siguiendo la respuesta, marque mármol en al menos 49º piso.

Piso 50 -> descansos (la respuesta está entre 1 y 50 inclusive)
Piso 25 -> no se rompe (26 a 50)
Piso 37 -> no se rompe (38 a 50)
Piso 43 -> no se rompe (44 a 50)
Piso 46 -> no se rompe (47 a 50)
Piso 48 -> no se rompe (49 o 50)
49th floor -> breaks (49th, este paso es realmente necesario porque podría haber sido el mínimo para que el mármol se rompa en 50º)

Esto se puede imaginar como hacer una búsqueda binaria en un conjunto ordenado para algunos k, donde tenemos la mitad del espacio de solución con cada intento. Para 100 plantas, necesitamos log2 100 = 6.644 (7 intentos). Con 7 canicas, podemos estar seguros de cuál es el piso mínimo en que el mármol se dividirá en 128 pisos.

Este problema se trata en el problema 6.5 del libro " Cracking the Coding Interview (5th) ", con soluciones resumidas de la siguiente manera:

Observación:

Independientemente de cómo eliminemos Marble1, Marble2 debe hacer una búsqueda lineal. Por ejemplo, si el Marble1 se rompe entre el piso 10 y 15, tenemos que verificar cada piso intermedio con el Marble2

El enfoque:

Una primera prueba: supongamos que tiramos un mármol del piso 10, luego el 20, ...

En los primeros descansos de Mármol en la primera caída (Piso 10), tenemos como máximo 10 caídas en total.
Si el primer Mármol se rompe en la última caída (Piso 100), entonces tenemos un máximo de 19 caídas en total (pisos 1 a 100, luego 91 a 99).
Eso es bastante bueno, pero todo lo que se nos considera es el peor de los casos. Deberíamos hacer un cierto "equilibrio de carga" para que esos dos casos sean más parejos.

Objetivo: Crear un sistema para eliminar Marble1 de manera que la mayoría de las gotas necesarias sean consistentes, independientemente de si Marble1 se rompe en la primera o última caída.

Un sistema perfectamente balanceado sería uno en el que Drops of Marble1 + Drops of Marble2 es siempre el mismo, independientemente de dónde se rompiera Marble1.
Para que ese sea el caso, dado que cada gota de Marble1 da un paso más, Marble2 tiene permitido un paso menos.
Debemos, por lo tanto, reducir el número de pasos requeridos por Marble2 en una gota cada vez. Por ejemplo, si Marble1 se descarta en el Piso 20 y luego en el Piso 30, Marble2 posiblemente tome 9 pasos. Cuando eliminemos Marble1 nuevamente, debemos reducir los posibles pasos de Marble2 a solo 8. Por ejemplo, debemos descartar Marble1 en el piso 39.
Sabemos, por lo tanto, Marble1 debe comenzar en el piso X, luego subir por X-1 pisos, luego X-2, ..., hasta que llegue a 100.
Resuelve para X + (X-1) + (X-2) + ... + 1 = 100. X (X + 1) / 2 = 100 -> X = 14

Vamos al piso 14, luego a 27, luego a 39, ... Esto toma 14 pasos como máximo.

Código y extensión:

Para la implementación del código, puede consultar aquí .
Para la extensión a N mármoles, pisos M , consulte el Capítulo 12: El rompecabezas de huevos y pisos .