Maior Sequência Consecutiva e Cache LRU
Resolva longest-consecutive-sequence em O(n) usando um conjunto e projete um cache LRU com um OrderedDict.
Maior Sequência Consecutiva e Cache LRU é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Problema da sequência consecutiva mais longa
LeetCode 128, «Sequência consecutiva mais longa»: dado um vetor não ordenado, encontre o comprimento da maior sequência de inteiros consecutivos. Exemplo: A ideia principal é usar um conjunto para realizar testes de pertencimento em O(1) e começar a contar uma sequência somente a partir do seu menor elemento, identificado verificando se o predecessor está ausente do conjunto.[100,4,200,1,3,2] contém a sequência consecutiva [1,2,3,4], de comprimento 4. O desafio é resolvê-lo em O(n)
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 que a prova de O(n) é válida
Cada número é visitado no laço interno no máximo uma vez ao longo de todas as iterações do laço externo. Embora haja um laço interno dentro de um laço externo, o número total de iterações do laço interno em todas as iterações externas é no máximo n, pois cada número pode ser o sucessor de no máximo uma sequência. Esse argumento amortizado resulta em O(n) no total, de modo semelhante à análise da pilha monotônica.
# 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: abordagem baseada em ordenação
Em contraste, a abordagem de ordenar e percorrer tem complexidade O(n log n): ordene o vetor, remova as duplicatas consecutivas e conte as sequências consecutivas. Embora seja mais lenta, ela usa espaço adicional O(1), se a ordenação for feita no próprio vetor. A abordagem com conjunto usa espaço adicional O(n). Mencione ambas em uma entrevista e esclareça se a solução O(n log n) é aceitável considerando as restrições de espaço.
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])) # 4O que é um cache LRU?
Um cache LRU (menos recentemente usado) é uma estrutura de dados de capacidade fixa que remove o item menos recentemente usado quando está cheio e é necessário inserir um novo item. Operações: get(key) retorna o valor se a chave existir (e a marca como usada recentemente) ou -1 se estiver ausente; put(key, value) insere o par, removendo o LRU quando a capacidade é atingida.
Caches LRU são usados em sistemas operacionais (substituição de páginas), caches de navegadores e caches de consultas a bancos de dados. LeetCode 146 pede que você implemente um com get e put em O(1).
Cache LRU usando OrderedDict
O collections.OrderedDict do Python mantém a ordem de inserção e oferece suporte a move_to_end(key) (O(1)) para marcar um item como usado mais recentemente. Ao executar put, mova a chave para o final; quando a capacidade for excedida, remova o primeiro item (LRU). Isso fornece get e put em O(1) usando uma estrutura integrada internamente baseada em uma lista duplamente ligada e um mapa 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)) # 4Cache LRU do zero: lista duplamente ligada + HashMap
A implementação feita do zero usa uma lista duplamente ligada (para permitir a remoção de nós em O(1)) e um mapa hash (para localizar nós pela chave em O(1)). A lista mantém a ordem do LRU (head.next) ao MRU (tail.prev). Sentinelas fictícias de início e fim eliminam casos especiais de inserção e remoção nas extremidades.
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 que usar uma lista duplamente ligada para LRU?
Uma lista simplesmente ligada não consegue remover um nó arbitrário em O(1) sem conhecer o predecessor. Uma lista duplamente ligada armazena os ponteiros prev e next, tornando a remoção O(1) quando se tem a referência do nó. O mapa hash fornece acesso O(1) ao nó pela chave. Juntos: get(key) requer O(1) para encontrar o nó e O(1) para movê-lo para o final; put(key) requer O(1) para adicionar e O(1) para remover o nó LRU do início.
# 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')Cache LFU (menos frequentemente usado)
Uma variante mais difícil é o cache LFU (LeetCode 460), em que o item com a menor contagem de acessos é removido. Os empates são resolvidos pela recência: entre os itens menos frequentes, remove-se o menos recentemente usado. A implementação exige três estruturas de dados: um mapa de chave para valor, um mapa de chave para frequência e um mapa de frequência para OrderedDict, para manter a ordem de inserção dentro de cada grupo de frequência. get e put do LFU têm complexidade O(1) amortizada.
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 = 1Padrões de projeto: mapa hash + lista ligada
O cache LRU ilustra um poderoso padrão de projeto: combinar um mapa hash para consultar chaves em O(1) com uma lista ligada para realizar operações ordenadas em O(1). Esse padrão aparece em vários problemas de projeto de entrevistas: cache LRU, cache LFU, listas de salto e algumas variantes de filas. Sempre que um problema exigir tanto consulta em O(1) quanto operações baseadas em ordem em O(1), considere essa combinação.
Em entrevistas, declarar esse padrão explicitamente demonstra pensamento em nível de sistema e familiaridade com combinações clássicas de estruturas de dados.
Sequência consecutiva em uma matriz
Uma extensão da ideia de sequência consecutiva para duas dimensões: dada uma matriz de inteiros, encontre o comprimento da maior sequência consecutiva que pode ser percorrida, movendo-se para uma célula adjacente a cada passo. Isso combina BFS/DFS com a abordagem de sequência consecutiva baseada em conjunto. Armazene a posição de cada valor e, para cada valor inicial, verifique se o valor seguinte existe como vizinho.
# 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)Resumo da entrevista: o poder de conjunto + HashMap
Esses dois problemas compartilham um tema: transformar problemas O(n log n) ou O(n²) em O(n) usando a estrutura hash adequada. A sequência consecutiva mais longa usa um conjunto para responder «o predecessor está presente?» em O(1). O cache LRU usa um mapa hash para encontrar o nó instantaneamente e uma lista duplamente ligada para atualizar a ordem em O(1). Ambos substituem um percurso lento por pertencimento ou consulta em O(1).
Quando um entrevistador pergunta «você consegue fazer melhor que O(n log n)?», a resposta quase sempre é «use um mapa hash ou um conjunto hash para evitar a ordenação».
Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação abordados nesta lição.
Recapitulação da lição
Nesta lição, você aprendeu: a sequência consecutiva mais longa é encontrada em O(n) usando um conjunto para pertencimento em O(1) e iniciando as contagens somente no começo das sequências, o cache LRU alcança get e put em O(1) usando um OrderedDict (ou um mapa hash + uma lista duplamente ligada implementados do zero) e o padrão mapa hash + lista ligada é um componente reutilizável para estruturas de dados O(1) sensíveis à ordem. Em seguida, retomaremos a recursão com a estrutura de caso-base, confiança e construção.
Perguntas Frequentes
A aula “Maior Sequência Consecutiva e Cache LRU” é grátis?
Sim — o texto completo de “Maior Sequência Consecutiva e Cache LRU” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Maior Sequência Consecutiva e Cache LRU”?
Resolva longest-consecutive-sequence em O(n) usando um conjunto e projete um cache LRU com um OrderedDict. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Maior Sequência Consecutiva e Cache LRU”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Internals de Funções Hash e Tratamento de Colisões
- Two-Sum e Suas Muitas Variantes
- Contagem e Agrupamento por Frequência
- Maior Sequência Consecutiva e Cache LRU