Urutan Berurutan Terpanjang dan Cache LRU
Selesaikan longest-consecutive-sequence dalam O(n) menggunakan set, lalu rancang cache LRU dengan OrderedDict.
Urutan Berurutan Terpanjang dan Cache LRU adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Masalah Rangkaian Berurutan Terpanjang
LeetCode 128 'Rangkaian Berurutan Terpanjang': diberikan larik yang tidak terurut, temukan panjang rangkaian bilangan bulat berurutan terpanjang. Contoh: [100,4,200,1,3,2] berisi rangkaian berurutan [1,2,3,4] dengan panjang 4. Tantangannya adalah menyelesaikannya dalam O(n), bukan O(n log n) (yang dihasilkan oleh pengurutan lalu pemindaian).
Gagasan utamanya: gunakan sebuah himpunan untuk melakukan pengujian keanggotaan dalam O(1), dan mulai menghitung rangkaian hanya dari elemen terkecilnya (yang dikenali dengan memeriksa bahwa pendahulunya tidak ada dalam himpunan).
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])) # 9Mengapa Pembuktian O(n) Berlaku
Setiap bilangan dikunjungi paling banyak satu kali dalam perulangan while di seluruh iterasi perulangan for bagian luar. Meskipun terdapat perulangan while di dalam perulangan for, jumlah total iterasi perulangan while di seluruh iterasi luar paling banyak n (karena setiap bilangan menjadi 'curr_n + 1' dari paling banyak satu rangkaian). Argumen teramortisasi ini menghasilkan O(n) secara keseluruhan, serupa dengan analisis tumpukan monoton.
# 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)Alternatif: Pendekatan Berbasis Pengurutan
Sebagai perbandingan, pendekatan pengurutan lalu pemindaian berjalan dalam O(n log n): urutkan larik, hilangkan duplikat yang berurutan, lalu hitung rangkaian yang berurutan. Meskipun lebih lambat, pendekatan ini menggunakan ruang tambahan O(1) (jika pengurutan dilakukan di tempat). Pendekatan himpunan menggunakan ruang tambahan O(n). Sebutkan keduanya dalam wawancara dan jelaskan apakah solusi O(n log n) dapat diterima berdasarkan batasan ruang.
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])) # 4Apa Itu Tembolok LRU?
Tembolok LRU (Least Recently Used) adalah struktur data berkapasitas tetap yang mengeluarkan item yang paling lama tidak digunakan ketika tembolok penuh dan item baru perlu disisipkan. Operasi: get(key) mengembalikan nilai jika kunci tersebut ada (dan menandainya sebagai baru digunakan) atau -1 jika tidak ada; put(key, value) menyisipkan pasangan tersebut (mengeluarkan LRU jika kapasitas sudah penuh).
Tembolok LRU digunakan dalam sistem operasi (penggantian halaman), tembolok peramban, dan tembolok kueri basis data. LeetCode 146 meminta Anda mengimplementasikannya dengan get dan put O(1).
Tembolok LRU Menggunakan OrderedDict
collections.OrderedDict milik Python mempertahankan urutan penyisipan dan mendukung move_to_end(key) (O(1)) untuk menandai item sebagai yang paling baru digunakan. Saat put, pindahkan kunci ke akhir; saat kapasitas terlampaui, keluarkan item pertama (LRU). Dengan demikian, get dan put membutuhkan O(1) menggunakan alat bawaan yang secara internal didukung oleh daftar tertaut ganda + peta 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)) # 4Tembolok LRU dari Awal: Daftar Tertaut Ganda + HashMap
Implementasi dari awal menggunakan daftar tertaut ganda (untuk mendukung penghapusan simpul dalam O(1)) dan peta hash (untuk pencarian simpul berdasarkan kunci dalam O(1)). Daftar tersebut mempertahankan urutan dari LRU (head.next) hingga MRU (tail.prev). Penjaga kepala dan ekor semu menghilangkan kasus khusus saat penyisipan dan penghapusan di batas-batas daftar.
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)Mengapa Daftar Tertaut Ganda untuk LRU?
Daftar tertaut tunggal tidak dapat menghapus simpul sembarang dalam O(1) tanpa mengetahui pendahulunya. Daftar tertaut ganda menyimpan kedua penunjuk prev dan next, sehingga penghapusan dapat dilakukan dalam O(1) jika referensi simpulnya diketahui. Peta hash menyediakan akses O(1) ke simpul berdasarkan kunci. Bersama-sama: get(key) membutuhkan O(1) untuk menemukan simpul dan O(1) untuk memindahkannya ke ekor; put(key) membutuhkan O(1) untuk menambahkan dan O(1) untuk menghapus simpul LRU dari kepala.
# 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')Tembolok LFU (Least Frequently Used)
Varian yang lebih sulit adalah tembolok LFU (LeetCode 460), tempat item dengan jumlah akses paling sedikit dikeluarkan. Jika frekuensinya sama, penentuannya berdasarkan kebaruan (item yang paling lama digunakan di antara item yang paling jarang digunakan). Implementasinya memerlukan tiga struktur data: peta kunci-ke-nilai, peta kunci-ke-frekuensi, dan peta frekuensi-ke-OrderedDict (untuk mempertahankan urutan penyisipan di dalam setiap kelompok frekuensi). Operasi get dan put LFU membutuhkan O(1) secara teramortisasi.
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 = 1Pola Desain: Peta Hash + Daftar Tertaut
Tembolok LRU menunjukkan pola desain yang kuat: gabungkan peta hash untuk pencarian kunci O(1) dengan daftar tertaut untuk operasi berurutan O(1). Pola ini muncul dalam beberapa masalah desain wawancara: tembolok LRU, tembolok LFU, daftar lompatan, dan beberapa varian antrean. Setiap kali suatu masalah memerlukan pencarian O(1) sekaligus operasi berbasis urutan O(1), pertimbangkan kombinasi ini.
Dalam wawancara, menyatakan pola ini secara eksplisit menunjukkan pola pikir tingkat sistem dan pemahaman terhadap kombinasi struktur data klasik.
Rangkaian Berurutan dalam Matriks
Perluasan gagasan rangkaian berurutan ke dua dimensi: diberikan matriks bilangan bulat, temukan panjang rangkaian berurutan terpanjang yang dapat ditelusuri (setiap langkah berpindah ke sel yang berdekatan). Ini menggabungkan BFS/DFS dengan pendekatan himpunan untuk rangkaian berurutan. Simpan posisi setiap nilai, lalu untuk setiap nilai awal periksa apakah nilai+1 ada sebagai tetangga.
# 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)Ringkasan Wawancara: Kekuatan Himpunan + HashMap
Kedua masalah ini memiliki tema yang sama: mengubah masalah O(n log n) atau O(n²) menjadi O(n) dengan menggunakan struktur hash yang tepat. Rangkaian berurutan terpanjang menggunakan himpunan untuk menjawab 'apakah pendahulunya ada?' dalam O(1). Tembolok LRU menggunakan peta hash untuk menemukan simpul secara langsung dan daftar tertaut ganda untuk memperbarui urutan dalam O(1). Keduanya menggantikan penelusuran lambat dengan keanggotaan atau pencarian O(1).
Saat pewawancara mengatakan 'dapatkah Anda melakukan yang lebih baik daripada O(n log n)?', jawabannya hampir selalu 'gunakan peta hash atau himpunan hash untuk menghindari pengurutan'.
Pemeriksaan Singkat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rekapitulasi Pelajaran
Dalam pelajaran ini Anda mempelajari: rangkaian berurutan terpanjang berjalan dalam O(n) dengan menggunakan himpunan untuk keanggotaan O(1) dan hanya memulai penghitungan dari awal rangkaian, tembolok LRU mencapai get dan put O(1) menggunakan OrderedDict (atau peta hash + daftar tertaut ganda dari awal), dan pola peta hash + daftar tertaut merupakan komponen dasar yang dapat digunakan kembali untuk struktur data O(1) yang peka terhadap urutan. Selanjutnya kita akan meninjau kembali rekursi dengan kerangka kasus dasar, kepercayaan, dan pembangunan.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Urutan Berurutan Terpanjang dan Cache LRU” gratis?
Ya — teks lengkap “Urutan Berurutan Terpanjang dan Cache LRU” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Urutan Berurutan Terpanjang dan Cache LRU”?
Selesaikan longest-consecutive-sequence dalam O(n) menggunakan set, lalu rancang cache LRU dengan OrderedDict. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Urutan Berurutan Terpanjang dan Cache LRU” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Internal Fungsi Hash dan Penanganan Tabrakan
- Two-Sum dan Berbagai Variasinya
- Penghitungan Frekuensi dan Pengelompokan
- Urutan Berurutan Terpanjang dan Cache LRU