最長連続列とLRUキャッシュ
setを使ってlongest-consecutive-sequenceをO(n)で解き、OrderedDictでLRUキャッシュを設計します。
「最長連続列とLRUキャッシュ」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
最長連続系列の問題
LeetCode 128「最長連続系列」では、ソートされていない配列が与えられたとき、連続する整数からなる最長の系列の長さを求めます。例として、[100,4,200,1,3,2] には、長さ 4 の連続系列 [1,2,3,4] が含まれています。課題は、ソートしてから走査する場合の O(n log n) ではなく、O(n) で解くことです。
重要なポイントは、メンバーシップテストを O(1) で行える集合を使い、系列の最小要素からのみカウントを開始することです。最小要素かどうかは、その直前の値が集合に存在しないことを確認して判定します。
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])) # 9O(n) の証明が成り立つ理由
外側の for ループのすべての反復を通して、各数値が while ループで訪問されるのは最大でも1回です。for ループの中に while ループがあるにもかかわらず、外側の反復全体における while ループの実行回数は最大 n 回です。各数値は、最大でも1つの系列における 'curr_n + 1' になるためです。この償却計算量の考え方により、全体の計算量は O(n) になります。これは単調スタックの分析と同様です。
# 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)別解：ソートを使う方法
比較のため、ソートしてから走査する方法の計算量は O(n log n) です。配列をソートし、連続する重複を除去してから、連続する区間を数えます。こちらは遅くなりますが、ソートをインプレースで行う場合は追加の空間計算量を O(1) にできます。集合を使う方法では O(n) の追加領域が必要です。面接では両方の方法を説明し、空間制約を考慮したときに O(n log n) の解法で問題ないかを確認してください。
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])) # 4LRU キャッシュとは
LRU（Least Recently Used）キャッシュは、容量が固定されたデータ構造です。キャッシュが満杯の状態で新しい項目を挿入する必要があるとき、最も長く使われていない項目を削除します。操作には、キーが存在する場合に値を返して最近使われたものとしてマークし、存在しない場合は -1 を返す get(key) と、キーと値のペアを挿入し、容量に達していれば LRU を削除する put(key, value) があります。
LRU キャッシュは、オペレーティングシステム（ページ置換）、ブラウザキャッシュ、データベースのクエリキャッシュなどで使われています。LeetCode 146 では、get と put が O(1) になるように実装することが求められます。
OrderedDict を使った LRU キャッシュ
Python の collections.OrderedDict は挿入順を維持し、move_to_end(key)（O(1)）によって項目を最も最近使われたものとしてマークできます。put ではキーを末尾に移動し、容量を超えた場合は先頭の項目を取り出します（LRU）。内部では二重連結リストとハッシュマップを組み合わせた組み込み機能によって、get と put を O(1) で実現しています。
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 キャッシュを自前実装する：二重連結リスト＋ハッシュマップ
自前実装では、ノードの削除を O(1) で行うための二重連結リストと、キーからノードを O(1) で検索するためのハッシュマップを使います。リストは LRU（head.next）から MRU（tail.prev）までの順序を維持します。head と tail にダミーのセンチネルを置くことで、境界での挿入や削除に関する例外的なケースをなくせます。
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)LRU に二重連結リストを使う理由
単方向連結リストでは、前のノードがわからない限り、任意のノードを O(1) で削除できません。二重連結リストでは prev と next の両方のポインタを保持するため、ノードへの参照があれば O(1) で削除できます。ハッシュマップによってキーからノードへ O(1) でアクセスできます。これらを組み合わせると、get(key) はノードの検索と末尾への移動をそれぞれ O(1) で行え、put(key) は追加と先頭からの LRU ノードの削除をそれぞれ O(1) で行えます。
# 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 キャッシュ（Least Frequently Used）
より難しい variant として LFU キャッシュ（LeetCode 460）があります。ここでは、アクセス回数が最も少ない項目を削除します。同数の場合は、最も頻度が低い項目の中で最も長く使われていないものを削除します。実装には、キーから値へのマップ、キーから頻度へのマップ、頻度から OrderedDict へのマップという3つのデータ構造が必要です。最後のマップによって、各頻度グループ内の挿入順を維持します。LFU の get と put は償却 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 = 1設計パターン：ハッシュマップ＋連結リスト
LRU キャッシュは、O(1) のキー検索を行うハッシュマップと、O(1) の順序操作を行う連結リストを組み合わせるという強力な設計パターンを示しています。このパターンは、LRU キャッシュ、LFU キャッシュ、スキップリスト、一部のキューの派生形など、複数の面接設計問題に登場します。O(1) の検索と O(1) の順序ベースの操作の両方が必要な問題では、この組み合わせを検討してください。
面接でこのパターンを明示的に説明すると、システムレベルの思考力と、古典的なデータ構造の組み合わせに関する知識を示せます。
行列内の連続系列
連続系列の考え方を2次元に拡張した問題です。整数の行列が与えられたとき、各ステップで隣接セルに移動しながらたどれる最長の連続系列の長さを求めます。この問題では、BFS/DFS と連続系列に対する集合の方法を組み合わせます。各値の位置を保存し、各開始値について value+1 が隣接セルに存在するかを確認します。
# 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)面接のまとめ：集合＋ハッシュマップの力
これら2つの問題には、適切なハッシュ構造を使って O(n log n) や O(n²) の問題を O(n) に変換するという共通のテーマがあります。最長連続系列では、集合を使って「直前の値が存在するか」を O(1) で判定します。LRU キャッシュでは、ハッシュマップでノードを即座に検索し、二重連結リストで順序を O(1) で更新します。どちらも、遅い走査を O(1) のメンバーシップテストや検索に置き換えています。
面接官から「O(n log n) より速くできますか」と聞かれたら、ほとんどの場合の答えは「ソートを避けるためにハッシュマップまたはハッシュセットを使う」です。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、最長連続系列は、O(1) のメンバーシップテストを行う集合を使い、系列の開始地点からのみカウントすることで O(n) で実行できること、LRU キャッシュは OrderedDict（または自前実装のハッシュマップ＋二重連結リスト）を使って get と put を O(1) で実現できること、そしてハッシュマップ＋連結リストのパターンは、順序に依存する O(1) のデータ構造を作るために再利用できる構成要素であることを学びました。次は、ベースケース、信頼、構築というフレームワークを使って、再帰をもう一度学びます。
よくある質問
「最長連続列とLRUキャッシュ」レッスンは無料ですか？
はい。「最長連続列とLRUキャッシュ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「最長連続列とLRUキャッシュ」で何を学びますか？
setを使ってlongest-consecutive-sequenceをO(n)で解き、OrderedDictでLRUキャッシュを設計します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「最長連続列とLRUキャッシュ」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- ハッシュ関数の内部動作と衝突処理
- Two-Sumとその多様な派生問題
- 頻度カウントとグループ化
- 最長連続列とLRUキャッシュ