Sequenza consecutiva più lunga e cache LRU
Risolva longest-consecutive-sequence in O(n) usando un set, poi progetti una cache LRU con OrderedDict
Sequenza consecutiva più lunga e cache LRU è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Problema della sequenza consecutiva più lunga
LeetCode 128 «Sequenza consecutiva più lunga»: dato un array non ordinato, trovi la lunghezza della sequenza più lunga di interi consecutivi. Esempio: [100,4,200,1,3,2] contiene la sequenza consecutiva [1,2,3,4] di lunghezza 4. La difficoltà consiste nel risolvere il problema in O(n) anziché in O(n log n), che è la complessità di un approccio basato su ordinamento e scansione.
L'idea chiave è usare un set per verificare l'appartenenza in O(1) e iniziare a contare una sequenza solo dal suo elemento più piccolo, identificato verificando che il predecessore sia assente dal set.
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])) # 9Perché la dimostrazione di O(n) è valida
Ogni numero viene visitato al massimo una volta nel ciclo while, considerando tutte le iterazioni del ciclo for esterno. Anche se all'interno di un ciclo for è presente un ciclo while, il numero totale di iterazioni dei cicli while in tutte le iterazioni esterne è al massimo n, perché ogni numero può essere il «curr_n + 1» di al massimo una sequenza. Questo argomento ammortizzato porta a una complessità complessiva O(n), in modo simile all'analisi dello stack monotono.
# 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: approccio basato sull'ordinamento
Per confronto, l'approccio basato su ordinamento e scansione richiede O(n log n): ordini l'array, elimini i duplicati consecutivi e poi conti le sequenze consecutive. Sebbene sia più lento, usa O(1) di spazio aggiuntivo se l'ordinamento viene eseguito in-place. L'approccio con set usa O(n) di spazio aggiuntivo. In un colloquio, presenti entrambi e chiarisca se la soluzione O(n log n) è accettabile considerando i vincoli di spazio.
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])) # 4Che cos'è una cache LRU
Una cache LRU (Least Recently Used) è una struttura dati a capacità fissa che espelle l'elemento utilizzato meno recentemente quando è piena e deve essere inserito un nuovo elemento. Operazioni: get(key) restituisce il valore se la chiave esiste e la contrassegna come utilizzata di recente, oppure restituisce -1 se la chiave è assente; put(key, value) inserisce la coppia ed espelle l'elemento LRU se la capacità è stata raggiunta.
Le cache LRU vengono usate nei sistemi operativi (sostituzione delle pagine), nelle cache dei browser e nelle cache delle query dei database. LeetCode 146 chiede di implementarne una con operazioni get e put in O(1).
Cache LRU con OrderedDict
collections.OrderedDict di Python mantiene l'ordine di inserimento e supporta move_to_end(key) (O(1)) per contrassegnare un elemento come utilizzato più di recente. In caso di put, sposti la chiave alla fine; in caso di superamento della capacità, usi pop per rimuovere il primo elemento (LRU). In questo modo get e put richiedono O(1), usando una struttura integrata basata internamente su una lista doppiamente concatenata + una mappa 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 da zero: lista doppiamente concatenata + HashMap
L'implementazione da zero usa una lista doppiamente concatenata (per supportare la rimozione di un nodo in O(1)) e una mappa hash (per trovare un nodo tramite la chiave in O(1)). La lista mantiene l'ordine da LRU (head.next) a MRU (tail.prev). I nodi sentinella head e tail fittizi eliminano i casi limite per l'inserimento e la rimozione alle estremità.
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)Perché usare una lista doppiamente concatenata per LRU
Una lista semplicemente concatenata non può rimuovere un nodo arbitrario in O(1) senza conoscere il predecessore. Una lista doppiamente concatenata memorizza entrambi i puntatori prev e next, rendendo la rimozione O(1) quando si dispone del riferimento al nodo. La mappa hash fornisce accesso O(1) al nodo tramite la chiave. Insieme: get(key) richiede O(1) per trovare il nodo e O(1) per spostarlo in coda; put(key) richiede O(1) per aggiungere un nodo e O(1) per rimuovere il nodo LRU dalla testa.
# 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 (Least Frequently Used)
Una variante più complessa è la cache LFU (LeetCode 460), in cui viene espulso l'elemento con il conteggio degli accessi più basso. In caso di parità, si usa la recenza: viene espulso l'elemento utilizzato meno recentemente tra quelli meno frequenti. L'implementazione richiede tre strutture dati: una mappa da chiave a valore, una mappa da chiave a frequenza e una mappa da frequenza a OrderedDict, per mantenere l'ordine di inserimento all'interno di ogni gruppo di frequenza. Le operazioni get e put di LFU richiedono O(1) ammortizzato.
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 = 1Pattern di progettazione: mappa hash + lista concatenata
La cache LRU illustra un potente pattern di progettazione: combinare una mappa hash per cercare una chiave in O(1) con una lista concatenata per eseguire operazioni ordinate in O(1). Questo pattern compare in diversi problemi di progettazione tipici dei colloqui: cache LRU, cache LFU, skip list e alcune varianti di coda. Ogni volta che un problema richiede sia una ricerca in O(1) sia operazioni basate sull'ordine in O(1), consideri questa combinazione.
Nei colloqui, dichiarare esplicitamente questo pattern dimostra una visione a livello di sistema e familiarità con le combinazioni classiche di strutture dati.
Sequenza consecutiva in una matrice
Un'estensione dell'idea della sequenza consecutiva alle due dimensioni: data una matrice di interi, trovi la lunghezza della sequenza consecutiva più lunga che può essere tracciata, spostandosi a ogni passo in una cella adiacente. Questo approccio combina BFS/DFS con l'approccio basato su set delle sequenze consecutive. Memorizzi la posizione di ogni valore, poi, per ogni valore iniziale, verifichi se value+1 esiste come vicino.
# 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)Riepilogo per il colloquio: la potenza di Set + HashMap
Questi due problemi condividono un tema: trasformare problemi O(n log n) o O(n²) in problemi O(n) usando la struttura hash corretta. La sequenza consecutiva più lunga usa un set per rispondere in O(1) alla domanda «il predecessore è presente?». La cache LRU usa una mappa hash per trovare immediatamente il nodo e una lista doppiamente concatenata per aggiornare l'ordine in O(1). Entrambe sostituiscono la scansione lenta con verifiche di appartenenza o ricerche in O(1).
Quando un intervistatore chiede «può fare di meglio di O(n log n)?», la risposta è quasi sempre «usi una mappa hash o un hash set per evitare l'ordinamento».
Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato: la sequenza consecutiva più lunga può essere trovata in O(n) usando un set per verificare l'appartenenza in O(1) e iniziando a contare solo dall'inizio delle sequenze, la cache LRU raggiunge get e put in O(1) usando un OrderedDict oppure, da zero, una mappa hash + una lista doppiamente concatenata e il pattern mappa hash + lista concatenata è un componente riutilizzabile per strutture dati O(1) sensibili all'ordine. Nella prossima lezione riprenderemo la ricorsione con il framework caso base, fiducia e costruzione.
Domande Frequenti
La lezione «Sequenza consecutiva più lunga e cache LRU» è gratuita?
Sì — il testo completo di «Sequenza consecutiva più lunga e cache LRU» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Sequenza consecutiva più lunga e cache LRU»?
Risolva longest-consecutive-sequence in O(n) usando un set, poi progetti una cache LRU con OrderedDict Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Sequenza consecutiva più lunga e cache LRU»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Interni delle funzioni hash e gestione delle collisioni
- Two-sum e le sue numerose varianti
- Conteggio e raggruppamento delle frequenze
- Sequenza consecutiva più lunga e cache LRU