Preguntas de entrevista tech y desarrollo: acertijos de algoritmos resueltos
Estos acertijos entrenan a reducir el número de intentos, a dividir el espacio de posibilidades y a elegir un algoritmo según su coste en tiempo y en memoria. Aquí tienes 4 acertijos clásicos con su solución explicada.
Acertijo de los dos huevos y los 100 pisos: ¿cuántos lanzamientos?
Pregunta de entrevista en tecnología: buscar un umbral con el mínimo de intentos.
Dispones de dos huevos idénticos y de un edificio de 100 pisos. Existe un piso crítico por encima del cual un huevo lanzado se rompe; por debajo, sobrevive y puede volver a usarse. ¿Cuál es el número mínimo de lanzamientos necesario, en el peor caso, para encontrar ese piso crítico?
¿Una pista?
Si el primer huevo se rompe, tendrás que probar los pisos uno a uno con el segundo: elige, pues, escalones cuyas distancias disminuyan.
Ver la respuesta y la solución
Respuesta: 14 lanzamientos como mínimo en el peor caso, lanzando el primer huevo por escalones cuyas distancias disminuyen de 14 a 1.
El razonamiento
En cada lanzamiento del primer huevo, se acepta tener que recorrer en el peor caso el intervalo que lo precede con el segundo huevo, piso a piso. Se suelta el primer huevo en los pisos 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 y después en el 100, lo que da distancias de 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4 y después 1. Si el primer huevo se rompe en un escalón, el segundo prueba los pisos uno a uno desde el escalón anterior: en el peor caso, son k lanzamientos para el k-ésimo escalón, más la distancia menos uno, es decir, 14 en total en todos los casos. El número n de lanzamientos debe cumplir n(n+1)/2 ≥ 100: para n = 13 se obtiene 91, insuficiente, y para n = 14 se obtiene 105, suficiente. La respuesta es, pues, 14 lanzamientos.
Encontrar el número que falta en una tabla: la solución del acertijo
Pregunta de entrevista para programador, sobre algoritmia y complejidad.
Una tabla contiene los enteros del 1 al n, excepto uno, y sus elementos están desordenados. Conoces el valor de n, pero ni el número que falta ni el orden de los elementos. ¿Cómo encontrar el número que falta de la forma más eficiente posible?
¿Una pista?
Piensa en una propiedad aritmética de la sucesión de enteros del 1 al n que permita hallar el elemento ausente sin buscarlo.
Ver la respuesta y la solución
Respuesta: Restar la suma de los elementos de la tabla a la suma esperada n(n+1)/2: la diferencia es el número que falta, con complejidad O(n) en tiempo y O(1) en memoria.
El razonamiento
La suma de los enteros del 1 al n vale n(n+1)/2, fórmula que basta calcular una sola vez. Si se suman todos los elementos presentes en la tabla, falta exactamente el número ausente, así que la suma real es menor que la suma esperada exactamente en ese número. La diferencia entre ambas sumas da directamente el valor buscado. El cálculo solo recorre la tabla una vez, así que la complejidad es O(n) en tiempo, y solo se necesitan unas pocas variables, es decir, O(1) de memoria adicional. Otro método, igual de eficiente, consiste en hacer la operación O exclusivo (XOR) de todos los números presentes con los de 1 a n: el resultado es el número que falta.
Adivinar un número del 1 al 1.000 con preguntas de sí o no: la solución
Algoritmia: pregunta sobre la búsqueda dicotómica, que divide el intervalo en cada pregunta.
Estoy pensando en un número entero comprendido entre 1 y 1.000. Puedes hacerme preguntas a las que solo respondo con sí o no. ¿Cuántas preguntas de sí o no bastan, en el peor caso, para adivinar ese número con seguridad?
¿Una pista?
No pruebes los números uno a uno: elige cada pregunta de modo que elimine la mitad de las posibilidades restantes.
Ver la respuesta y la solución
Respuesta: 10 preguntas: cada respuesta divide entre dos el número de posibilidades, y 2 elevado a 10 es 1.024, mayor que 1.000.
El razonamiento
Cada pregunta de sí o no reparte las posibilidades restantes en dos grupos, por ejemplo preguntando si el número es mayor que 500. Sea cual sea la respuesta, se conserva una mitad del intervalo y se repite el procedimiento sobre esa nueva mitad. Tras k preguntas, quedan como máximo unas 1.000 / 2 elevado a k posibilidades. Con 9 preguntas solo se pueden distinguir 2 elevado a 9, es decir, 512 casos, lo cual es insuficiente para 1.000 números. Con 10 preguntas se distinguen 2 elevado a 10, es decir, 1.024 casos, lo cual basta. La respuesta es, pues, 10 preguntas en el peor caso. Este principio es el de la búsqueda dicotómica, de complejidad O(log n).
Detectar un ciclo en una lista enlazada sin memoria: la solución
Pregunta de entrevista para programador, sobre estructuras de datos y complejidad de memoria.
Una lista enlazada es una sucesión de nodos, cada uno de los cuales apunta al siguiente. A veces un nodo apunta a otro ya encontrado: la lista forma entonces un ciclo y nunca termina. ¿Cómo detectar si existe un ciclo sin usar memoria adicional proporcional al tamaño de la lista?
¿Una pista?
Imagina dos corredores que recorren la lista a velocidades distintas: ¿qué ocurre si dan vueltas indefinidamente en un ciclo?
Ver la respuesta y la solución
Respuesta: Algoritmo de Floyd: un puntero avanza un nodo, el otro dos; si se encuentran, hay un ciclo (O(n) en tiempo, O(1) en memoria).
El razonamiento
Bastan dos punteros colocados al principio de la lista: la tortuga avanza un nodo en cada paso, y la liebre, dos nodos. Si la lista termina, la liebre llega al final y se concluye que no hay ciclo. Si existe un ciclo, los dos punteros acaban entrando en él: la liebre alcanza entonces a la tortuga, porque gana un nodo en cada paso, y se encuentran en un mismo nodo. El número de pasos es proporcional al tamaño de la lista, así que la complejidad es O(n) en tiempo. Como solo se almacenan dos punteros, la memoria adicional es O(1).
Preguntas frecuentes
¿Qué tipos de acertijos aparecen en esta página tech?
La página reúne cuatro acertijos de razonamiento algorítmico: la pregunta de los dos huevos y los 100 pisos, la búsqueda de un número que falta en una tabla, la búsqueda de un número entre 1 y 1000 con preguntas de sí o no, y la detección de un bucle en una lista enlazada. Cada uno se describe con un método breve y un coste en tiempo y memoria.
¿Hay que saber programar para resolver estos acertijos?
No: el método se describe primero con frases, por ejemplo dividiendo entre dos el número de posibilidades en cada pregunta, y solo después se traduce a código. El código llega cuando el razonamiento y su coste están establecidos.
¿Cómo prepararse para estos acertijos de algoritmos?
Para cada acertijo, enuncia el método e indica después su coste en tiempo y en memoria, como hacen las soluciones de esta página. Empieza por los problemas de división del espacio de posibilidades y pasa luego a las estructuras de datos, como las listas enlazadas.
¿Y ahora?
El razonamiento se entrena como la memoria: practicando a menudo. Ponte a prueba después con nuestros quiz de cultura general.