Lengste sammenhengende sekvens og LRU-cache
Løs longest-consecutive-sequence i O(n) med et set, og utform deretter en LRU-cache med OrderedDict.
Lengste sammenhengende sekvens og LRU-cache er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Problemet med lengste sammenhengende tallsekvens
LeetCode 128 «Longest Consecutive Sequence»: gitt en usortert tabell skal De finne lengden på den lengste sekvensen av sammenhengende heltall. Eksempel: [100,4,200,1,3,2] inneholder den sammenhengende sekvensen [1,2,3,4] med lengde 4. Utfordringen er å løse problemet i O(n) i stedet for O(n log n), som De ville fått med sortering og gjennomgang.
Hovedideen er å bruke et set til medlemskapstester i O(1), og bare begynne å telle en sekvens fra dens minste element (identifisert ved å kontrollere at forgjengeren ikke finnes i settet).
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])) # 9Hvorfor O(n)-beviset holder
Hvert tall besøkes høyst én gang i while-løkken på tvers av alle gjennomgangene i den ytre for-løkken. Selv om det finnes en while-løkke inni en for-løkke, er det totale antallet while-løkkeiterasjoner på tvers av alle ytre iterasjoner høyst n, siden hvert tall er «curr_n + 1» for høyst én sekvens. Dette amortiserte argumentet gir O(n) totalt, på samme måte som analysen av en monoton stakk.
# 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)Alternativ: sorteringsbasert tilnærming
Til sammenligning har sorterings- og gjennomgangstilnærmingen kjøretid O(n log n): sorter tabellen, fjern påfølgende duplikater, og tell sammenhengende løp. Selv om denne metoden er langsommere, bruker den O(1) ekstra plass hvis sorteringen gjøres på stedet. Set-tilnærmingen bruker O(n) ekstra plass. Nevn begge i et intervju, og avklar om løsningen i O(n log n) er akseptabel med tanke på plassbegrensninger.
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])) # 4Hva er en LRU-cache?
En LRU-cache (Least Recently Used) er en datastruktur med fast kapasitet som fjerner det elementet som sist ble brukt for lengst siden, når den er full og et nytt element må settes inn. Operasjoner: get(key) returnerer verdien hvis nøkkelen finnes (og markerer den som nylig brukt), eller -1 hvis den mangler; put(key, value) setter inn paret (og fjerner LRU-elementet hvis kapasiteten er nådd).
LRU-cacher brukes i operativsystemer (sideutskifting), nettleserbuffere og hurtigbuffere for databasespørringer. LeetCode 146 ber Dem implementere en med get og put i O(1).
LRU-cache med OrderedDict
Python-klassen collections.OrderedDict opprettholder innsettingsrekkefølgen og støtter move_to_end(key) (O(1)) for å markere et element som sist brukt. Ved put flyttes nøkkelen til slutten; ved overflyt fjernes det første elementet (LRU). Dette gir get og put i O(1) ved hjelp av en innebygd komponent som internt er basert på en dobbeltlenket liste og et hash map.
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 fra grunnen av: dobbeltlenket liste + HashMap
Implementasjonen fra grunnen av bruker en dobbeltlenket liste (for å støtte fjerning av noder i O(1)) og et hash map (for oppslag av noder med nøkkel i O(1)). Listen opprettholder rekkefølgen fra LRU (head.next) til MRU (tail.prev). Dummy-sentineler for head og tail eliminerer spesialtilfeller ved innsetting og fjerning i endene.
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)Hvorfor en dobbeltlenket liste for LRU?
En enkeltlenket liste kan ikke fjerne en vilkårlig node i O(1) uten å kjenne forgjengeren. En dobbeltlenket liste lagrer både prev- og next-pekere, slik at fjerning kan gjøres i O(1) når De har en referanse til noden. Hash mapet gir tilgang til noden med nøkkel i O(1). Til sammen tar get(key) O(1) for å finne noden og O(1) for å flytte den til tail; put(key) tar O(1) for å legge til og O(1) for å fjerne LRU-noden fra head.
# 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)
En vanskeligere variant er LFU-cache (LeetCode 460), der elementet med lavest antall tilganger fjernes. Ved likhet avgjøres det av hvor nylig elementene er brukt (det minst nylig brukte blant elementene med lavest frekvens fjernes). Implementasjonen krever tre datastrukturer: et map fra nøkkel til verdi, et map fra nøkkel til frekvens og et map fra frekvens til OrderedDict (for å opprettholde innsettingsrekkefølgen i hver frekvensgruppe). LFU get og put har amortisert O(1)-kompleksitet.
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 = 1Designmønstre: hash map + lenket liste
LRU-cachen illustrerer et kraftig designmønster: kombiner et hash map for oppslag av nøkler i O(1) med en lenket liste for ordnede operasjoner i O(1). Dette mønsteret forekommer i flere designproblemer fra kodeintervjuer: LRU-cache, LFU-cache, skip-lister og enkelte køvarianter. Når et problem krever både oppslag i O(1) og ordnede operasjoner i O(1), bør De vurdere denne kombinasjonen.
I intervjuer viser De systemtenkning og kjennskap til klassiske kombinasjoner av datastrukturer ved å oppgi dette mønsteret eksplisitt.
Sammenhengende sekvens i en matrise
Dette er en utvidelse av ideen om sammenhengende sekvenser til 2D: gitt en matrise med heltall skal De finne lengden på den lengste sammenhengende sekvensen som kan følges, der hvert trinn går til en tilstøtende celle. Dette kombinerer BFS/DFS med set-tilnærmingen for sammenhengende sekvenser. Lagre posisjonen til hver verdi, og kontroller deretter for hver startverdi om value+1 finnes som nabo.
# 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)Intervjuoppsummering: kraften i set + HashMap
Disse to problemene har et felles tema: å konvertere problemer med O(n log n) eller O(n²) til O(n) ved å bruke riktig hash-struktur. Problemet med den lengste sammenhengende sekvensen bruker et set til å svare på «finnes forgjengeren?» i O(1). LRU-cache bruker et hash map til å finne noden umiddelbart og en dobbeltlenket liste til å oppdatere rekkefølgen i O(1). Begge erstatter langsom gjennomgang med medlemskapstest eller oppslag i O(1).
Når intervjueren spør «kan De gjøre det bedre enn O(n log n)?», er svaret nesten alltid «bruk et hash map eller hash-sett for å unngå sortering».
Hurtigsjekk
Test forståelsen Deres av konseptene innen Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte De: problemet med den lengste sammenhengende sekvensen løses i O(n) ved å bruke et set for medlemskap i O(1) og bare starte tellingen ved begynnelsen av en sekvens, LRU-cache oppnår get og put i O(1) ved hjelp av OrderedDict (eller et hash map og en dobbeltlenket liste implementert fra grunnen av), og mønsteret med hash map og lenket liste er en gjenbrukbar byggestein for ordenssensitive datastrukturer i O(1). Neste tema er rekursjon med rammeverket basistilfelle, tillit og oppbygging.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Lengste sammenhengende sekvens og LRU-cache» gratis?
Ja – hele teksten i «Lengste sammenhengende sekvens og LRU-cache» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Lengste sammenhengende sekvens og LRU-cache»?
Løs longest-consecutive-sequence i O(n) med et set, og utform deretter en LRU-cache med OrderedDict. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Lengste sammenhengende sekvens og LRU-cache»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Interne detaljer i hashfunksjoner og kollisjonshåndtering
- Two-Sum og de mange variantene
- Frekvenstelling og gruppering
- Lengste sammenhengende sekvens og LRU-cache