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.  , 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!   Problema de codificación diario  Entonces basta de hablar; ¡Veamos el problema!  El problema  Este problema lo planteó Goldman Sachs en una entrevista de trabajo. Veamos el problema.      huevos idénticos y acceso a un edificio con   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   , puedes asumir que también se romperá al caer desde cualquier piso mayor que   . Te dan N k xth 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.      y   , 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á   . Por ejemplo, si N = 1 k = 5 5  Así, nos dan unos huevos para tirar desde distintos pisos de un edificio. Nos entristece que desde un determinado piso (al que llamaremos   ), los huevos arrojados no se rompan al caer al suelo. targetFloor  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   . 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 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.   https://gist.github.com/NicolaM94/85ae34f01e7de8cd00264276b385e137?embedable=true#file-main-go  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   usando el módulo   integrado en Go. targetFlor math/rand  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:   https://gist.github.com/NicolaM94/dd49b3b44a8938c40d0539512fd613cb?embedable=true#file-main-go  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   es el piso 7 (no lo sabemos, por supuesto). Podríamos hacer las siguientes conjeturas:  targetFloor  Básicamente, suponemos que el   es el piso medio del edificio. Tiramos el huevo desde ahí, y los resultados posibles son dos: targetFloor  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   aplicada a un problema del “mundo real”. La búsqueda binaria es un algoritmo simple y claro   , lo que significa que en cada paso, el tamaño del problema se reduce a la mitad hasta que encontramos la solución. búsqueda binaria de divide y vencerás  Esto significa que este algoritmo, comparado con el anterior, es mucho más rápido. ¡Veamos el código!   https://gist.github.com/NicolaM94/79d625ecef07cb26a7a8d9bcdb6143fd?embedable=true#file-main-go  Echemos un vistazo más profundo. La función de búsqueda binaria toma 4 argumentos:    , una matriz de números enteros, que es el edificio sobre el que estamos recorriendo; overArray    , el índice inferior del edificio; bottom    , el índice del último piso del edificio; top    , la variable que contiene   para comprobar si podemos encontrarlo en el edificio. breakFloor targetFloor  Después de eso, recorremos el edificio mientras   está más baja que   : en la búsqueda binaria, cuando los dos argumentos posicionales se entrelazan y se intercambian, significa que no se encontró el elemento buscado. bottom top  Por lo tanto, si el algoritmo termina en esta situación, el bucle finaliza y devolvemos   , 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. -1  Calculamos el elemento   como el piso entre   y   y verificamos si   . Si es así, devolvemos el   como resultado. middlePoint bottom top middlePoint == breakFloor middlePoint  Si no es así, ajustamos la parte   o   en consecuencia: si   es mayor que   , significa que estamos demasiado altos en el edificio, por lo que reducimos nuestra predicción estableciendo el piso   posible en   . bottom top middlePoint breakFloor top middlePoint — 1  Si   es más pequeño que   , ajustamos nuestro   estableciéndolo como   . middlePoint breakFloor bottom middlePoint+1  Ahora, para verificar todo, en la función   , generamos el entorno como antes y creamos una nueva variable llamada   que contendrá nuestro resultado. main bsFloor  Para confirmar que nuestro algoritmo nos llevó al resultado correcto, imprimimos   y   , que se generó previamente de forma aleatoria. bsFloor targetFloor  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   . 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. O(log(n))  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  ¡página!   ko-fi  ¡Y como siempre, gracias por leer!   nicolás   También publicado  aquí

Read My Stories

Este audio es producido en el idioma original de la historia!

Demasiado Largo; Para Leer

Make resilience your competitive advantage

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

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

El modelo Bitcoin UTXO, impulsando un ecosistema único

De los foros a los feeds: cómo los algoritmos de las redes sociales influyen en la interacción digital

La guía completa para una migración exitosa a la nube: estrategias y mejores prácticas

Toque para ganar: Telegram puede incorporar a los próximos 10 mil millones de usuarios de criptomonedas antes de Solana

El modelo Bitcoin UTXO, impulsando un ecosistema único

De los foros a los feeds: cómo los algoritmos de las redes sociales influyen en la interacción digital

La guía completa para una migración exitosa a la nube: estrategias y mejores prácticas

Toque para ganar: Telegram puede incorporar a los próximos 10 mil millones de usuarios de criptomonedas antes de Solana

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps