Najdłuższy spójny ciąg i pamięć podręczna LRU
Rozwiążą Państwo longest-consecutive-sequence w O(n) z użyciem zbioru, a następnie zaprojektują pamięć podręczną LRU za pomocą OrderedDict.
Najdłuższy spójny ciąg i pamięć podręczna LRU to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Problem najdłuższego kolejnego ciągu
LeetCode 128 „Najdłuższy kolejny ciąg”: mając nieposortowaną tablicę, należy znaleźć długość najdłuższego ciągu kolejnych liczb całkowitych. Przykład: [100,4,200,1,3,2] zawiera kolejny ciąg [1,2,3,4] o długości 4. Wyzwaniem jest rozwiązanie problemu w O(n), a nie w O(n log n), które uzyskałoby się przez sortowanie, a następnie skanowanie.
Kluczowa obserwacja: należy użyć zbioru do testów przynależności w O(1) i rozpoczynać zliczanie ciągu wyłącznie od jego najmniejszego elementu (rozpoznawanego przez sprawdzenie, czy poprzednika nie ma w zbiorze).
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])) # 9Dlaczego dowód złożoności O(n) jest poprawny
Każda liczba jest odwiedzana w pętli while co najwyżej raz we wszystkich iteracjach zewnętrznej pętli for. Mimo że wewnątrz pętli for znajduje się pętla while, łączna liczba iteracji pętli while we wszystkich iteracjach zewnętrznych wynosi co najwyżej n, ponieważ każda liczba jest wartością „curr_n + 1” dla co najwyżej jednego ciągu. Ten argument amortyzowany daje łącznie O(n), podobnie jak analiza stosu monotonicznego.
# 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)Alternatywa: podejście oparte na sortowaniu
Dla porównania podejście polegające na sortowaniu i skanowaniu działa w O(n log n): sortuje tablicę, usuwa kolejne duplikaty, a następnie zlicza kolejne ciągi. Choć jest wolniejsze, wykorzystuje O(1) dodatkowej pamięci, jeśli sortowanie odbywa się w miejscu. Podejście ze zbiorem wykorzystuje O(n) dodatkowej pamięci. Podczas rozmowy rekrutacyjnej warto wspomnieć o obu rozwiązaniach i wyjaśnić, czy rozwiązanie O(n log n) jest akceptowalne przy danych ograniczeniach pamięci.
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])) # 4Czym jest pamięć podręczna LRU
Pamięć podręczna LRU (Least Recently Used) to struktura danych o stałej pojemności, która po zapełnieniu usuwa element używany najdawniej, gdy trzeba wstawić nowy element. Operacje: get(key) zwraca wartość, jeśli klucz istnieje, i oznacza go jako niedawno używany, albo zwraca -1, jeśli klucza nie ma; put(key, value) wstawia parę, usuwając element LRU, jeśli osiągnięto limit pojemności.
Pamięci podręczne LRU są używane w systemach operacyjnych (zastępowanie stron), pamięciach podręcznych przeglądarek i pamięciach podręcznych zapytań do baz danych. LeetCode 146 wymaga zaimplementowania takiej pamięci z operacjami get i put w O(1).
Pamięć podręczna LRU z użyciem OrderedDict
Pythonowy collections.OrderedDict zachowuje kolejność wstawiania i obsługuje move_to_end(key) (O(1)), aby oznaczyć element jako najdawniej używany. Podczas operacji put należy przenieść klucz na koniec, a w przypadku przepełnienia usunąć pierwszy element (LRU). Dzięki temu operacje get i put mają złożoność O(1), korzystając z wbudowanego narzędzia opartego wewnętrznie na dwukierunkowej liście wiązanej i mapie haszującej.
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)) # 4Pamięć podręczna LRU od podstaw: lista dwukierunkowa + HashMap
Implementacja od podstaw korzysta z dwukierunkowej listy wiązanej (aby umożliwić usuwanie węzła w O(1)) i mapy haszującej (aby wyszukiwać węzeł po kluczu w O(1)). Lista utrzymuje kolejność od LRU (head.next) do MRU (tail.prev). Atrapy head i tail pełniące funkcję węzłów wartowniczych eliminują przypadki brzegowe podczas wstawiania i usuwania na końcach listy.
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)Dlaczego lista dwukierunkowa w LRU
Lista jednokierunkowa nie może usunąć dowolnego węzła w O(1), jeśli nie zna jego poprzednika. Lista dwukierunkowa przechowuje oba wskaźniki: prev i next, dzięki czemu usunięcie węzła na podstawie jego referencji ma złożoność O(1). Mapa haszująca zapewnia dostęp do węzła po kluczu w O(1). Razem: get(key) wymaga O(1) do znalezienia węzła i O(1) do przeniesienia go na koniec; put(key) wymaga O(1) do dodania elementu i O(1) do usunięcia węzła LRU z początku listy.
# 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')Pamięć podręczna LFU (najrzadziej używane)
Trudniejszym wariantem jest pamięć podręczna LFU (LeetCode 460), w której usuwany jest element o najmniejszej liczbie dostępów. Remisy rozstrzyga się na podstawie aktualności użycia: spośród elementów o najmniejszej częstości usuwa się ten używany najdawniej. Implementacja wymaga trzech struktur danych: mapy klucz-wartość, mapy klucz-częstość oraz mapy częstość-OrderedDict (aby zachować kolejność wstawiania w każdej grupie częstości). Operacje get i put w LFU mają zamortyzowaną złożoność 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 = 1Wzorce projektowe: mapa haszująca + lista wiązana
Pamięć podręczna LRU ilustruje potężny wzorzec projektowy: połączenie mapy haszującej do wyszukiwania klucza w O(1) z listą wiązaną do wykonywania uporządkowanych operacji w O(1). Ten wzorzec pojawia się w kilku problemach projektowych spotykanych na rozmowach rekrutacyjnych: pamięci podręcznej LRU, pamięci podręcznej LFU, listach przeskokowych i niektórych wariantach kolejek. Gdy problem wymaga zarówno wyszukiwania w O(1), jak i uporządkowanych operacji w O(1), warto rozważyć takie połączenie.
Podczas rozmowy rekrutacyjnej jawne wskazanie tego wzorca pokazuje myślenie na poziomie systemu i znajomość klasycznych połączeń struktur danych.
Kolejny ciąg w macierzy
Rozszerzenie idei kolejnego ciągu na dwa wymiary: mając macierz liczb całkowitych, należy znaleźć długość najdłuższego kolejnego ciągu, który można prześledzić, wykonując każdy krok do sąsiedniej komórki. Łączy to BFS/DFS z podejściem wykorzystującym zbiór dla kolejnych ciągów. Należy zapisać położenie każdej wartości, a następnie dla każdej wartości początkowej sprawdzić, czy value+1 istnieje jako sąsiad.
# 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)Podsumowanie rozmowy: siła zbioru i HashMap
Te dwa problemy mają wspólny motyw: przekształcanie problemów O(n log n) lub O(n²) w problemy O(n) dzięki zastosowaniu właściwej struktury haszującej. Najdłuższy kolejny ciąg wykorzystuje zbiór do sprawdzenia w O(1), czy poprzednik jest obecny. Pamięć podręczna LRU wykorzystuje mapę haszującą do natychmiastowego znalezienia węzła oraz dwukierunkową listę wiązaną do aktualizowania kolejności w O(1). Oba rozwiązania zastępują powolne przechodzenie testami przynależności lub wyszukiwaniem w O(1).
Gdy rekruter zapyta: „Czy można zrobić to lepiej niż w O(n log n)?”, odpowiedzią niemal zawsze jest: „Należy użyć mapy haszującej lub zbioru haszującego, aby uniknąć sortowania”.
Szybki test
Proszę sprawdzić znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo: najdłuższy kolejny ciąg można znaleźć w O(n), używając zbioru do testów przynależności w O(1) i rozpoczynając zliczanie wyłącznie od początków ciągów, pamięć podręczna LRU zapewnia operacje get i put w O(1) dzięki OrderedDict (lub mapie haszującej i dwukierunkowej liście wiązanej w implementacji od podstaw), a wzorzec mapa haszująca + lista wiązana jest uniwersalnym elementem budulcowym struktur danych zależnych od kolejności, działających w O(1). Następnie wrócimy do rekurencji, korzystając ze schematu obejmującego przypadek bazowy, zaufanie i budowanie.
Często zadawane pytania
Czy lekcja „Najdłuższy spójny ciąg i pamięć podręczna LRU” jest bezpłatna?
Tak — pełny tekst „Najdłuższy spójny ciąg i pamięć podręczna LRU” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Najdłuższy spójny ciąg i pamięć podręczna LRU”?
Rozwiążą Państwo longest-consecutive-sequence w O(n) z użyciem zbioru, a następnie zaprojektują pamięć podręczną LRU za pomocą OrderedDict. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Najdłuższy spójny ciąg i pamięć podręczna LRU”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Wewnętrzne działanie funkcji haszującej i obsługa kolizji
- Two-Sum i jego liczne warianty
- Zliczanie częstotliwości i grupowanie
- Najdłuższy spójny ciąg i pamięć podręczna LRU