Längste aufeinanderfolgende Sequenz und LRU-Cache
Lösen Sie longest-consecutive-sequence in O(n) mit einem Set und entwerfen Sie anschließend einen LRU-Cache mit einem OrderedDict.
Längste aufeinanderfolgende Sequenz und LRU-Cache ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Problem der längsten aufeinanderfolgenden Sequenz
LeetCode 128 „Längste aufeinanderfolgende Sequenz“: Ermitteln Sie bei einem unsortierten Array die Länge der längsten Sequenz aufeinanderfolgender Ganzzahlen. Beispiel: [100,4,200,1,3,2] enthält die aufeinanderfolgende Sequenz [1,2,3,4] der Länge 4. Die Herausforderung besteht darin, das Problem in O(n) statt in O(n log n) zu lösen (was Sortieren und anschließendes Durchlaufen ergeben würden).
Die zentrale Erkenntnis: Verwenden Sie ein Set für Mitgliedschaftstests in O(1), und beginnen Sie nur beim kleinsten Element einer Sequenz mit dem Zählen (ermittelt, indem Sie prüfen, dass der Vorgänger nicht im Set vorhanden ist).
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])) # 9Warum der O(n)-Beweis gilt
Jede Zahl wird in der while-Schleife über alle Durchläufe der äußeren for-Schleife hinweg höchstens einmal besucht. Obwohl sich innerhalb einer for-Schleife eine while-Schleife befindet, beträgt die Gesamtzahl der while-Schleifendurchläufe über alle äußeren Durchläufe hinweg höchstens n (da jede Zahl für höchstens eine Sequenz das „curr_n + 1“-Element ist). Dieses amortisierte Argument ergibt insgesamt O(n), ähnlich wie bei der Analyse eines monotonen Stacks.
# 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)Alternative: Sortierbasierter Ansatz
Zum Vergleich benötigt der Sortier-und-Durchlauf-Ansatz O(n log n): Sortieren Sie das Array, entfernen Sie aufeinanderfolgende Duplikate und zählen Sie anschließend die zusammenhängenden Sequenzen. Obwohl dieser Ansatz langsamer ist, benötigt er O(1) zusätzlichen Speicherplatz (bei einer In-place-Sortierung). Der Set-Ansatz benötigt O(n) zusätzlichen Speicherplatz. Nennen Sie im Interview beide Ansätze und klären Sie, ob die O(n log n)-Lösung angesichts der Speicherbeschränkungen akzeptabel ist.
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])) # 4Was ist ein LRU-Cache
Ein LRU (Least Recently Used)-Cache ist eine Datenstruktur mit fester Kapazität, die das am längsten nicht verwendete Element entfernt, wenn sie voll ist und ein neues Element eingefügt werden muss. Operationen: get(key) gibt den Wert zurück, wenn der Schlüssel vorhanden ist (und markiert ihn als kürzlich verwendet), oder -1, wenn er fehlt; put(key, value) fügt das Paar ein (und entfernt bei voller Kapazität das LRU-Element).
LRU-Caches werden in Betriebssystemen (Seitenersetzung), Browser-Caches und Datenbankabfrage-Caches verwendet. LeetCode 146 fordert Sie auf, einen solchen Cache mit get und put in O(1) zu implementieren.
LRU-Cache mit OrderedDict
Python's collections.OrderedDict verwaltet die Einfügereihenfolge und unterstützt move_to_end(key) (O(1)), um ein Element als zuletzt verwendet zu markieren. Verschieben Sie bei put den Schlüssel ans Ende; entfernen Sie bei einem Überlauf das erste Element (LRU). Dadurch benötigen get und put jeweils O(1), wobei ein integrierter Typ verwendet wird, der intern auf einer doppelt verketteten Liste und einer Hashmap basiert.
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)) # 4LRU-Cache selbst implementieren: doppelt verkettete Liste + Hashmap
Die Implementierung von Grund auf verwendet eine doppelt verkettete Liste (um Knoten in O(1) entfernen zu können) und eine Hashmap (für die Suche nach Knoten anhand des Schlüssels in O(1)). Die Liste verwaltet die Reihenfolge vom LRU-Element (head.next) bis zum MRU-Element (tail.prev). Dummy-Knoten für head und tail beseitigen Sonderfälle beim Einfügen und Entfernen an den Grenzen.
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)Warum eine doppelt verkettete Liste für LRU
Eine einfach verkettete Liste kann einen beliebigen Knoten nicht in O(1) entfernen, ohne den Vorgänger zu kennen. Eine doppelt verkettete Liste speichert sowohl prev- als auch next-Zeiger, sodass das Entfernen bei bekannter Knotenreferenz O(1) benötigt. Die Hashmap ermöglicht den Zugriff auf den Knoten anhand des Schlüssels in O(1). Zusammen benötigt get(key) O(1), um den Knoten zu finden, und O(1), um ihn an das Ende zu verschieben; put(key) benötigt O(1) zum Hinzufügen und O(1), um den LRU-Knoten am Anfang zu entfernen.
# 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')LFU-Cache (Least Frequently Used)
Eine anspruchsvollere Variante ist der LFU-Cache (LeetCode 460), bei dem das Element mit der geringsten Zugriffshäufigkeit entfernt wird. Bei Gleichstand entscheidet die Aktualität: Unter den am seltensten verwendeten Elementen wird das am längsten nicht verwendete entfernt. Die Implementierung erfordert drei Datenstrukturen: eine Map von Schlüssel zu Wert, eine Map von Schlüssel zu Häufigkeit und eine Map von Häufigkeit zu OrderedDict (um die Einfügereihenfolge innerhalb jeder Häufigkeitsgruppe zu erhalten). get und put des LFU-Caches benötigen amortisiert 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 = 1Entwurfsmuster: Hashmap + verkettete Liste
Der LRU-Cache veranschaulicht ein leistungsfähiges Entwurfsmuster: eine Hashmap für die Suche nach Schlüsseln in O(1) mit einer verketteten Liste für geordnete Operationen in O(1) kombinieren. Dieses Muster tritt bei mehreren Entwurfsproblemen in Interviews auf: LRU-Cache, LFU-Cache, Skip-Listen und einige Queue-Varianten. Wenn ein Problem sowohl eine Suche in O(1) als auch reihenfolgebasierte Operationen in O(1) erfordert, sollten Sie diese Kombination in Betracht ziehen.
In Interviews zeigt das explizite Benennen dieses Musters Denken auf Systemebene und Vertrautheit mit klassischen Kombinationen von Datenstrukturen.
Aufeinanderfolgende Sequenz in einer Matrix
Eine Erweiterung des Konzepts der aufeinanderfolgenden Sequenz auf zwei Dimensionen: Ermitteln Sie bei einer Matrix aus Ganzzahlen die Länge der längsten aufeinanderfolgenden Sequenz, die sich verfolgen lässt (jeder Schritt führt zu einer benachbarten Zelle). Dies kombiniert BFS/DFS mit dem Set-Ansatz für aufeinanderfolgende Sequenzen. Speichern Sie die Position jedes Werts; prüfen Sie dann für jeden Startwert, ob value+1 als Nachbar existiert.
# 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)Interview-Zusammenfassung: Die Stärke von Set + Hashmap
Diese beiden Probleme haben ein gemeinsames Thema: Probleme mit O(n log n) oder O(n²) mithilfe der richtigen Hashstruktur auf O(n) reduzieren. Die längste aufeinanderfolgende Sequenz verwendet ein Set, um in O(1) zu prüfen, ob der Vorgänger vorhanden ist. Der LRU-Cache verwendet eine Hashmap, um den Knoten sofort zu finden, und eine doppelt verkettete Liste, um die Reihenfolge in O(1) zu aktualisieren. Beide ersetzen langsames Durchlaufen durch Mitgliedschafts- oder Suchoperationen in O(1).
Wenn ein Interviewer fragt: „Können Sie das besser als in O(n log n) lösen?“, lautet die Antwort fast immer: „Verwenden Sie eine Hashmap oder ein Hashset, um das Sortieren zu vermeiden.“
Schnelltest
Testen Sie Ihr Verständnis der in dieser Lektion behandelten Konzepte aus Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Die längste aufeinanderfolgende Sequenz läuft in O(n), indem ein Set für Mitgliedschaftstests in O(1) verwendet und nur an Sequenzanfängen mit dem Zählen begonnen wird, ein LRU-Cache erreicht mit einem OrderedDict (oder von Grund auf mit Hashmap und doppelt verketteter Liste) get und put in O(1) und das Muster aus Hashmap und verketteter Liste ist ein wiederverwendbarer Baustein für reihenfolgeabhängige O(1)-Datenstrukturen. Als Nächstes greifen wir Rekursion mit dem Framework aus Basisfall, Vertrauen und Aufbau erneut auf.
Häufig gestellte Fragen
Ist die Lektion „Längste aufeinanderfolgende Sequenz und LRU-Cache“ kostenlos?
Ja — der vollständige Text von „Längste aufeinanderfolgende Sequenz und LRU-Cache“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Längste aufeinanderfolgende Sequenz und LRU-Cache“?
Lösen Sie longest-consecutive-sequence in O(n) mit einem Set und entwerfen Sie anschließend einen LRU-Cache mit einem OrderedDict. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Längste aufeinanderfolgende Sequenz und LRU-Cache“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Interna von Hash-Funktionen und Kollisionsbehandlung
- Two-Sum und seine vielen Varianten
- Häufigkeiten zählen und gruppieren
- Längste aufeinanderfolgende Sequenz und LRU-Cache