Preguntas de entrevista de Algoritmos y estructuras de datos
56 preguntas de entrevista de Algoritmos y estructuras de datos con respuestas, de nivel junior a intermedio.
Fundamentos
Base
- ¿Cuál es la complejidad temporal de la búsqueda binaria en un array ordenado?
- ¿Cuál es el coste de búsqueda medio y en el peor caso en una hash table?
- Validar un string de paréntesis como
"([]{})". ¿Qué estructura de datos usas? - ¿Qué devuelve esta función y cuáles son sus costes de tiempo y espacio?
- En una lista de Python,
append(x)einsert(0, x)cuestan… - Las comprobaciones repetidas
x in datadentro de un bucle son lentas.dataes una lista de 1 millón de elementos. ¿Cómo lo arreglas? - ¿Cómo abordas en una entrevista un problema de código que nunca has visto?
- ¿Qué describe la notación Big-O?
- ¿Cuál es la complejidad temporal?
- ¿Cuál es la complejidad temporal?
- Acceder al elemento número 1000: ¿array (lista de Python) o linked list?
- Una pila (stack) es…
- Una cola (queue) es…
- ¿Por qué toda función recursiva debe tener un caso base?
- Buscar en una lista sin ordenar revisando cada elemento uno a uno es…
- En una estructura de árbol, ¿qué es una hoja?
- ¿Qué es un grafo en informática?
- ¿Qué debe cumplirse para poder usar búsqueda binaria en una lista?
- ¿Cuál es la complejidad temporal de
nums[5]en una lista de Python de 1 millón de elementos?
Intermedio
- ¿Cuál es la cota inferior de la ordenación basada en comparaciones?
- ¿Cuál es el peor caso de quicksort y cuándo ocurre?
- ¿Qué es cierto sobre merge sort?
- Two Sum: encuentra los índices de dos números que sumen
target. ¿Cuál es el enfoque óptimo? - ¿Cómo detectas un ciclo en una linked list con O(1) de espacio extra?
- ¿Cómo hallas el camino más corto (menos aristas) en un grafo sin pesos?
- ¿Cuál es la mejor forma de obtener los k elementos mayores de un flujo de n números?
- Subcadena más larga sin caracteres repetidos. ¿Cuál es la técnica óptima y su complejidad?
- En un array ordenado, averigua si dos números suman target usando O(1) de espacio.
- ¿Qué dos propiedades indican que un problema encaja con la programación dinámica?
- ¿Cuál es la complejidad temporal de Fibonacci con memoización
fib(n)? - Un DFS recursivo profundo en Python sobre un grafo en forma de camino de 100.000 nodos probablemente…
- Implementar una cola con dos pilas da, ¿qué coste por operación?
- Autocompletado por prefijo sobre un diccionario de palabras. ¿Cuál es la mejor estructura?
- ¿Qué recorrido de un árbol binario de búsqueda da las claves ordenadas?
- ¿Cuál es el tiempo de búsqueda en el peor caso de un BST sin balancear creado con entrada ordenada?
- Para un grafo disperso (E mucho menor que V²), ¿qué representación se prefiere?
- ¿Cómo respondes rápido a muchas consultas de rango
sum(nums[i:j])sobre un array estático? - ¿Cómo funciona un hash map por dentro?
- Invierte una linked list simple de forma iterativa. Explica los punteros.
Avanzado
- El algoritmo de Dijkstra requiere…
- Necesitas un orden para instalar paquetes dadas relaciones 'A depende de B'. ¿Qué algoritmo usas?
- Contar componentes conexas mientras las aristas llegan de forma dinámica. ¿Cuál es la mejor estructura?
- ¿Cuál es la complejidad espacial de un DFS recursivo en un árbol binario de altura h?
- ¿Cómo obtienes la suma máxima de un subarray en O(n)?
- Generar todas las permutaciones de n elementos distintos cuesta como mínimo…
- El 'siguiente elemento mayor' de cada elemento de un array en O(n) usa…
- Una caché LRU con get y put en O(1) se construye normalmente con…
- Para un entero positivo n, ¿qué comprueba
n & (n - 1) == 0? - Un dynamic array duplica su capacidad cuando se llena. ¿Cuál es el coste amortizado de append?