Cuando tienes que tirar huevos desde la azotea: problema de codificación diario

Problema de codificación diaria 24

¡Bienvenido de nuevo con otro problema por resolver! Hoy nos enfrentamos a los huevos que caen de los tejados con este problema realmente bonito, que implicará dos posibles soluciones: una bastante ingenua y otra más inteligente. Este último también nos dará la oportunidad de hablar de un algoritmo bastante famoso.

Como siempre, el problema de hoy lo proporciona el maravilloso boletín. Problema de codificación diario , al que puedes suscribirte de forma gratuita para obtener también tu desafío diario de codificación. ¡Compruébalo e intenta resolver tus problemas también!

Entonces basta de hablar; ¡Veamos el problema!

El problema

Este problema lo planteó Goldman Sachs en una entrevista de trabajo. Veamos el problema.

Te dan N huevos idénticos y acceso a un edificio con k pisos. Tu tarea es encontrar el piso más bajo que hará que un huevo se rompa si se cae de ese piso. Una vez que un huevo se rompe, no se puede volver a dejar caer. Si un huevo se rompe al caer desde el piso xth , puedes asumir que también se romperá al caer desde cualquier piso mayor que x .

Escriba un algoritmo que encuentre el número mínimo de caídas de prueba que se necesitarán, en el peor de los casos, para identificar este piso.

Por ejemplo, si N = 1 y k = 5 , tendremos que intentar dejar caer el huevo en cada piso, comenzando por el primero, hasta llegar al quinto piso, por lo que nuestra solución será 5 .

Así, nos dan unos huevos para tirar desde distintos pisos de un edificio. Nos entristece que desde un determinado piso (al que llamaremos targetFloor ), los huevos arrojados no se rompan al caer al suelo.

Desde ese piso hasta todos los pisos debajo de él, los huevos no se romperán cuando se arrojen por la ventana. Lo que se nos pide que hagamos es encontrar un método eficiente para encontrar el targetFloor .

Como se anticipó, veremos dos métodos para resolver esto: uno realmente simple, que forzará la solución, pero no será eficiente. El segundo será mucho más eficiente e intentará solucionar el problema rompiendo el menor número de pasos.

También nos dará la oportunidad de hablar de un algoritmo realmente famoso e importante; uno de esos que necesitas saber para hacer… ¡básicamente cualquier cosa!

Configurar el entorno

Para comenzar, necesitamos configurar un poco del entorno, es decir, el edificio y el targetFloor . Para crear el edificio, simplemente creamos una matriz que contiene los números de los pisos, desde la planta baja hasta el piso nᵗʰ. Luego, generamos un número aleatorio que será nuestro targetFloor .

Escribiremos este problema en Go una vez más: lo suficientemente simple como para ser legible, pero lo suficientemente complejo como para comprender la mecánica interna.

Primero creamos el conjunto que servirá como nuestro edificio: podemos darle el tamaño que queramos, cuanto mayor sea el tamaño, más alto será el edificio. Después de eso, creamos una instancia de targetFlor usando el módulo math/rand integrado en Go.

Básicamente, creamos un nuevo entero aleatorio entre 0 y la altura del edificio (… la longitud de la matriz :D) usando como fuente la hora actual.

La solución de la fuerza bruta

Por supuesto, la solución más sencilla posible sería tirar cada huevo de cada piso, para ver en qué piso empiezan a romperse. Como tenemos una variable que contiene esa información, simplemente se podría hacer un bucle for para resolver el problema:

Si bien esta es la solución más sencilla, lamentablemente es muy ineficiente. Imagínese si el piso correcto fuera el superior: hay que romper 100.000 huevos para resolver el problema: ¡sería una tortilla enorme pero un desperdicio!

En términos generales, esta solución tiene una complejidad temporal de O(n) porque la complejidad de la solución crece linealmente con la complejidad del problema de entrada. Sin embargo, esta no es la solución más eficiente que se nos ocurre.

Una solución eficiente

Pensemos entonces en una solución eficiente. En lugar de caminar piso por piso rompiendo cada huevo en cada piso, podríamos hacer una suposición y, según el resultado de esa suposición, ajustar la siguiente suposición.

Aquí hay un ejemplo: supongamos que tenemos un edificio con 10 pisos y el targetFloor es el piso 7 (no lo sabemos, por supuesto). Podríamos hacer las siguientes conjeturas:

Básicamente, suponemos que el targetFloor es el piso medio del edificio. Tiramos el huevo desde ahí, y los resultados posibles son dos:

• el huevo se rompe, lo que significa que estamos demasiado drogados. Podemos descartar el suelo superior a este, incluido, y seguir con nuestras conjeturas.

• El huevo no se rompe, lo que significa que estamos demasiado bajos o en el suelo correcto. Desechamos todos los pisos inferiores a este, incluido, y

Teniendo esto en cuenta, ahora hacemos otra suposición fundamentada sobre el piso medio o el edificio "restante" y aplicamos la misma estrategia vista arriba. Podemos continuar con este enfoque hasta que nos quedemos con un piso.

Si reconoce este enfoque, tiene toda la razón: se trata simplemente de una búsqueda binaria aplicada a un problema del “mundo real”. La búsqueda binaria es un algoritmo simple y claro de divide y vencerás , lo que significa que en cada paso, el tamaño del problema se reduce a la mitad hasta que encontramos la solución.

Esto significa que este algoritmo, comparado con el anterior, es mucho más rápido. ¡Veamos el código!

Echemos un vistazo más profundo. La función de búsqueda binaria toma 4 argumentos:

• overArray , una matriz de números enteros, que es el edificio sobre el que estamos recorriendo;

• bottom , el índice inferior del edificio;

• top , el índice del último piso del edificio;

• breakFloor , la variable que contiene targetFloor para comprobar si podemos encontrarlo en el edificio.

Después de eso, recorremos el edificio mientras bottom está más baja que top : en la búsqueda binaria, cuando los dos argumentos posicionales se entrelazan y se intercambian, significa que no se encontró el elemento buscado.

Por lo tanto, si el algoritmo termina en esta situación, el bucle finaliza y devolvemos -1 , significando que el elemento que buscamos no estaba presente en el array. Si todavía estamos buscando el elemento, aplicamos lo que se muestra en la imagen superior.

Calculamos el elemento middlePoint como el piso entre bottom y top y verificamos si middlePoint == breakFloor . Si es así, devolvemos el middlePoint como resultado.

Si no es así, ajustamos la parte bottom o top en consecuencia: si middlePoint es mayor que breakFloor , significa que estamos demasiado altos en el edificio, por lo que reducimos nuestra predicción estableciendo el piso top posible en middlePoint — 1 .

Si middlePoint es más pequeño que breakFloor , ajustamos nuestro bottom estableciéndolo como middlePoint+1 .

Ahora, para verificar todo, en la función main , generamos el entorno como antes y creamos una nueva variable llamada bsFloor que contendrá nuestro resultado.

Para confirmar que nuestro algoritmo nos llevó al resultado correcto, imprimimos bsFloor y targetFloor , que se generó previamente de forma aleatoria.

Complejidad del tiempo

Como anticipamos antes, este algoritmo es mucho más rápido que el lineal. Como dividimos el edificio a la mitad en cada paso, podemos encontrar el piso correcto en log₂(n) donde n es igual a len(building) .

Esto significa que la complejidad temporal de este algoritmo es O(log(n)) . Para darle una comparación entre la solución lineal y esta última, si el edificio tiene 100 pisos, el algoritmo lineal toma en el peor de los casos 100 iteraciones, mientras que el algoritmo de búsqueda binaria toma log₂100 = 6,64, es decir, 7 iteraciones.

Además, este último es cada vez más eficiente que el lineal porque cuanto más crece el edificio, más eficiente es la búsqueda binaria. Para un edificio con 1.000.000.000 de pisos, el lineal toma 1.000.000.000 de pasos, mientras que el binario toma log₂1.000.000.000 = 29,9, es decir, 30 pasos. ¡Una gran mejora!

Conclusión

¡Eso es todo! ¡Espero que hayas disfrutado el artículo tanto como yo me divertí intentando resolver el desafío! Si es así, por favor deja un aplauso o dos, ¡sería un gran apoyo! Si te gustan este tipo de artículos y quieres ver más, sigue la página ya que publico este tipo de contenido cada vez que puedo.

Finalmente, si este artículo te resultó interesante o útil y te gustaría contribuir ofreciendo un café, no dudes en hacerlo en mi ko-fi ¡página!

¡Y como siempre, gracias por leer!

nicolás

También publicado aquí