Secuencia consecutiva más larga y caché LRU
Resuelva longest-consecutive-sequence en O(n) usando un conjunto y diseñe una caché LRU con OrderedDict.
Secuencia consecutiva más larga y caché LRU es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Problema de la secuencia consecutiva más larga
LeetCode 128 'Longest Consecutive Sequence': dado un arreglo sin ordenar, encuentre la longitud de la secuencia más larga de enteros consecutivos. Ejemplo: [100,4,200,1,3,2] contiene la secuencia consecutiva [1,2,3,4], de longitud 4. El reto consiste en resolverlo en O(n) en lugar de O(n log n), que es lo que produciría ordenar y recorrer.
La idea clave es utilizar un conjunto para realizar pruebas de pertenencia en O(1) y comenzar a contar una secuencia únicamente desde su elemento más pequeño, identificado al comprobar que su predecesor no está presente en el conjunto.
def longestConsecutive(nums):
num_set = set(nums)
best = 0
for n in num_set:
if n - 1 not in num_set: # n is the start of a sequence
curr_n = n
length = 1
while curr_n + 1 in num_set:
curr_n += 1
length += 1
best = max(best, length)
return best
print(longestConsecutive([100,4,200,1,3,2])) # 4
print(longestConsecutive([0,3,7,2,5,8,4,6,0,1])) # 9Por qué se cumple la prueba de O(n)
Cada número se visita como máximo una vez en el bucle while, considerando todas las iteraciones del bucle for externo. Aunque hay un bucle while dentro de un bucle for, la cantidad total de iteraciones del bucle while en todas las iteraciones externas es como máximo n, ya que cada número es el 'curr_n + 1' de como máximo una secuencia. Este argumento amortizado da un coste total de O(n), de forma similar al análisis de una pila monótona.
# Demonstrate O(n) total inner iterations
nums = list(range(1000)) # worst case: one long sequence
num_set = set(nums)
inner_iters = 0
for n in num_set:
if n - 1 not in num_set:
curr = n
while curr + 1 in num_set:
curr += 1
inner_iters += 1
print('n =', len(nums), ' total inner iterations =', inner_iters)
# inner_iters = n-1 <= n => O(n)Alternativa: enfoque basado en ordenamiento
Como contraste, el enfoque de ordenar y recorrer cuesta O(n log n): ordene el arreglo, elimine los duplicados consecutivos y después cuente las secuencias consecutivas. Aunque es más lento, utiliza un espacio adicional de O(1) si el ordenamiento se realiza en el propio arreglo. El enfoque con un conjunto utiliza un espacio adicional de O(n). Mencione ambos en una entrevista y aclare si la solución O(n log n) es aceptable dadas las restricciones de espacio.
def longestConsecutive_sort(nums):
if not nums:
return 0
nums.sort()
best = length = 1
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
continue # skip duplicates
if nums[i] == nums[i-1] + 1:
length += 1
best = max(best, length)
else:
length = 1
return best
print(longestConsecutive_sort([100,4,200,1,3,2])) # 4¿Qué es una caché LRU?
Una caché LRU (Least Recently Used) es una estructura de datos de capacidad fija que expulsa el elemento usado menos recientemente cuando está llena y es necesario insertar un elemento nuevo. Operaciones: get(key) devuelve el valor si la clave existe (y la marca como usada recientemente) o -1 si está ausente; put(key, value) inserta el par (expulsando el elemento LRU si se ha alcanzado la capacidad).
Las cachés LRU se utilizan en sistemas operativos (sustitución de páginas), cachés de navegadores y cachés de consultas de bases de datos. LeetCode 146 le pide implementar una con get y put en O(1).
Caché LRU con OrderedDict
collections.OrderedDict de Python mantiene el orden de inserción y admite move_to_end(key) (O(1)) para marcar un elemento como el más recientemente usado. Al hacer put, mueva la clave al final; si se supera la capacidad, extraiga el primer elemento (LRU). Esto proporciona get y put en O(1) mediante una estructura integrada respaldada internamente por una lista doblemente enlazada + una tabla hash.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # evict LRU (first item)
cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
print(cache.get(1)) # 1 (and 1 becomes most recently used)
cache.put(3, 3) # evict key 2 (LRU)
print(cache.get(2)) # -1
cache.put(4, 4) # evict key 1 (LRU)
print(cache.get(1)) # -1
print(cache.get(3)) # 3
print(cache.get(4)) # 4Caché LRU desde cero: lista doblemente enlazada + tabla hash
La implementación desde cero utiliza una lista doblemente enlazada (para permitir la eliminación de nodos en O(1)) y una tabla hash (para buscar nodos por clave en O(1)). La lista mantiene el orden desde LRU (head.next) hasta MRU (tail.prev). Los sentinelas ficticios head y tail eliminan los casos especiales de inserción y eliminación en los extremos.
class DNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCacheDLL:
def __init__(self, capacity):
self.cap = capacity
self.map = {} # key -> DNode
self.head = DNode() # dummy LRU end
self.tail = DNode() # dummy MRU end
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_tail(self, node):
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_to_tail(node)
return node.val
def put(self, key, val):
if key in self.map:
self._remove(self.map[key])
node = DNode(key, val)
self._add_to_tail(node)
self.map[key] = node
if len(self.map) > self.cap:
lru = self.head.next
self._remove(lru)
del self.map[lru.key]
cache = LRUCacheDLL(2)
cache.put(1,1); cache.put(2,2)
print(cache.get(1)) # 1
cache.put(3,3)
print(cache.get(2)) # -1 (evicted)¿Por qué una lista doblemente enlazada para LRU?
Una lista simplemente enlazada no puede eliminar un nodo arbitrario en O(1) sin conocer su predecesor. Una lista doblemente enlazada almacena los punteros prev y next, lo que permite eliminar un nodo en O(1) cuando se dispone de su referencia. La tabla hash proporciona acceso O(1) al nodo mediante su clave. En conjunto: get(key) tarda O(1) en encontrar el nodo y O(1) en moverlo al final; put(key) tarda O(1) en añadirlo y O(1) en eliminar el nodo LRU del principio.
# Why not a singly linked list?
# To remove a node you need its predecessor
# With SLL: must traverse from head to find predecessor => O(n)
# With DLL: node.prev IS the predecessor => O(1) removal
print('SLL removal: O(n) — must find predecessor by traversal')
print('DLL removal: O(1) — node.prev is immediately available')
print('Hash map lookup: O(1) — get DNode reference by key')
print('Combined LRU get/put: O(1) average')Caché LFU (Least Frequently Used)
Una variante más compleja es la caché LFU (LeetCode 460), en la que se expulsa el elemento con el menor contador de accesos. Los empates se resuelven por recencia: se expulsa el menos recientemente usado entre los elementos menos frecuentes. La implementación requiere tres estructuras de datos: un mapa de clave a valor, un mapa de clave a frecuencia y un mapa de frecuencia a OrderedDict (para mantener el orden de inserción dentro de cada grupo de frecuencia). Las operaciones get y put de LFU tienen un coste amortizado de O(1).
from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.cap = capacity
self.min_f = 0
self.kv = {} # key -> val
self.kf = {} # key -> freq
self.fk = defaultdict(OrderedDict) # freq -> {key: None}
def _touch(self, key):
f = self.kf[key]
self.kf[key] = f + 1
del self.fk[f][key]
if not self.fk[f] and f == self.min_f:
self.min_f += 1
self.fk[f+1][key] = None
def get(self, key):
if key not in self.kv:
return -1
self._touch(key)
return self.kv[key]
def put(self, key, val):
if self.cap == 0: return
if key in self.kv:
self.kv[key] = val
self._touch(key)
else:
if len(self.kv) == self.cap:
lfu_key, _ = self.fk[self.min_f].popitem(last=False)
del self.kv[lfu_key]; del self.kf[lfu_key]
self.kv[key] = val; self.kf[key] = 1
self.fk[1][key] = None; self.min_f = 1Patrones de diseño: tabla hash + lista enlazada
La caché LRU ilustra un patrón de diseño potente: combinar una tabla hash para buscar claves en O(1) con una lista enlazada para realizar operaciones ordenadas en O(1). Este patrón aparece en varios problemas de diseño de entrevistas: cachés LRU, cachés LFU, listas de salto y algunas variantes de colas. Siempre que un problema requiera tanto búsquedas en O(1) como operaciones basadas en el orden en O(1), considere esta combinación.
En las entrevistas, explicar este patrón explícitamente demuestra pensamiento a nivel de sistema y familiaridad con las combinaciones clásicas de estructuras de datos.
Secuencia consecutiva en una matriz
Una extensión de la idea de secuencia consecutiva a 2D: dada una matriz de enteros, encuentre la longitud de la secuencia consecutiva más larga que se pueda recorrer, donde cada paso se desplaza a una celda adyacente. Esto combina BFS/DFS con el enfoque de conjunto para secuencias consecutivas. Almacene la posición de cada valor y, para cada valor inicial, compruebe si value+1 existe como vecino.
# Simpler: find longest consecutive values in a 2D matrix (no adjacency)
def longestConsecutiveMatrix(matrix):
all_vals = set()
for row in matrix:
for v in row:
all_vals.add(v)
best = 0
for v in all_vals:
if v - 1 not in all_vals: # start of sequence
length = 0
while v in all_vals:
v += 1
length += 1
best = max(best, length)
return best
m = [[1, 5, 3], [4, 6, 2], [8, 7, 9]]
print(longestConsecutiveMatrix(m)) # 9 (1..9 all present)Resumen de entrevista: el poder de los conjuntos + HashMap
Estos dos problemas comparten un tema: convertir problemas de O(n log n) u O(n²) en problemas de O(n) utilizando la estructura hash adecuada. La secuencia consecutiva más larga utiliza un conjunto para responder «¿está presente el predecesor?» en O(1). La caché LRU utiliza una tabla hash para encontrar el nodo al instante y una lista doblemente enlazada para actualizar el orden en O(1). Ambas sustituyen el recorrido lento por pertenencia o búsqueda en O(1).
Cuando un entrevistador pregunta «¿puede hacerlo mejor que O(n log n)?», casi siempre la respuesta es «utilice una tabla hash o un conjunto hash para evitar ordenar».
Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Repaso de la lección
En esta lección aprendió que: la secuencia consecutiva más larga se ejecuta en O(n) utilizando un conjunto para comprobar pertenencia en O(1) y comenzando los conteos únicamente desde el inicio de cada secuencia, la caché LRU logra get y put en O(1) mediante un OrderedDict (o una tabla hash + una lista doblemente enlazada desde cero), y el patrón de tabla hash + lista enlazada es un componente reutilizable para estructuras de datos sensibles al orden con operaciones en O(1). A continuación retomaremos la recursión con el marco de caso base, confianza y construcción.
Preguntas frecuentes
¿La lección «Secuencia consecutiva más larga y caché LRU» es gratis?
Sí — el texto completo de «Secuencia consecutiva más larga y caché LRU» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Secuencia consecutiva más larga y caché LRU»?
Resuelva longest-consecutive-sequence en O(n) usando un conjunto y diseñe una caché LRU con OrderedDict. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Secuencia consecutiva más larga y caché LRU»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Internals de las funciones hash y gestión de colisiones
- Two-sum y sus numerosas variantes
- Conteo y agrupación por frecuencia
- Secuencia consecutiva más larga y caché LRU