Chương 6 - Hash Table

Hash Table (bảng băm) là “vũ khí thần kỳ” của phỏng vấn coding: nó biến nhiều bài O(n²) thành O(n). Triết lý: đổi bộ nhớ lấy thời gian - chấp nhận thêm O(n) bộ nhớ phụ để có look-up O(1). Chương này dạy bạn nhận diện khi nào nên và khi nào không nên dùng hash, cùng 6 bài kinh điển rất hay gặp ở Big Tech.

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Hiểu hash = đổi O(n) lookup thành O(1).
  • Pattern prefix → check complement (Two Sum, Subarray Sum K).
  • Pattern Counter + most_common cho top-k.
  • Biết khi nào hash KHÔNG đủ: cần order, range query, top-k, nearest.

Khi nào dùng pattern này?

  • Cần look-up / count / dedupe không yêu cầu thứ tự.
  • Có thể đổi O(n) search bên trong loop thành O(1) membership test.
  • Pattern phổ biến nhất: “thấy prefix nào đó → check complement” - Two Sum, Subarray Sum, …

Khi không nên dùng hash: - Cần thứ tự sort → dùng SortedSet/TreeMap (Python: sortedcontainers). - Cần O(1) worst-case (không phải amortized) → hash bị adversary tấn công collision. - Khoá là loại phức tạp (list, dict) → phải convert sang tuple/frozenset.

Template code 

from collections import Counter, defaultdict
from typing import List

# 1) Counter: đếm tần suất
cnt = Counter(nums)               # {value: count}
top3 = cnt.most_common(3)         # 3 phần tử thường gặp nhất

# 2) defaultdict(list): nhóm theo khoá
groups: dict[str, list[int]] = defaultdict(list)
for i, v in enumerate(arr):
    groups[v].append(i)

# 3) Prefix sum + dict: tìm subarray
prefix_index = {0: -1}            # prefix_sum -> index sớm nhất
cur = 0
for i, x in enumerate(arr):
    cur += x
    if cur - target in prefix_index:
        # tìm thấy subarray có sum = target
        ...
    if cur not in prefix_index:
        prefix_index[cur] = i

Bài tự luyện cuối chương

  • LC 1 - Two Sum (đã giải Chương 1)
  • LC 49 - Group Anagrams (đã giải Chương 2)
  • LC 219 - Contains Duplicate II
  • LC 220 - Contains Duplicate III
  • LC 525 - Contiguous Array (0/1 đếm prefix sum)
  • LC 974 - Subarray Sums Divisible by K
  • LC 30 - Substring with Concatenation of All Words
  • LC 380 - Insert Delete GetRandom O(1)

6.1 Contains Duplicate (LC 217)

Đề bài

Cho mảng nums. Trả về True nếu có ít nhất 1 phần tử xuất hiện ≥ 2 lần, ngược lại False.

Ví dụ 

Input:  nums = [1, 2, 3, 1]   → True
Input:  nums = [1, 2, 3, 4]   → False
Input:  nums = []             → False

Ràng buộc

  • 1 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9

Clarifying questions

  • Có yêu cầu nói *giá trị nào duplicate không?* → Không, chỉ True/False.
  • Có tối ưu bộ nhớ không? → Có thể follow-up O(1) extra space: sort tại chỗ rồi check.

Hướng tiếp cận

Brute force - O(n²). So sánh mọi cặp.

Sort - O(n log n), O(1) extra space. Sort rồi check 2 phần tử kề.

Hash set - O(n) time, O(n) space - đáp án phổ biến nhất.

One-liner Pythonic: return len(set(nums)) != len(nums).

Code Python 3 

from typing import List

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen: set[int] = set()
        for x in nums:
            if x in seen:
                return True
            seen.add(x)
        return False

Phân tích độ phức tạp

  • Thời gian: O(n) trung bình.
  • Bộ nhớ: O(n).

Bình luận

  • Tại sao không dùng len(set(nums)) != len(nums)? Tốt cho 1 dòng, nhưng không early-exit - vẫn duyệt hết mảng. Cách loop hỗ trợ break sớm.
  • Follow-up:
    1. LC 219 - Contains Duplicate II: duplicate trong khoảng cách k (sliding window + hash).
    2. LC 220 - Contains Duplicate III: khoảng cách value cũng có giới hạn (bucket sort hoặc SortedList).
  • Bẫy: hashing với float (NaN) hoặc list (unhashable)
    • nhưng theo đề chỉ là int nên OK.

Bài tự luyện liên quan

  • LC 219 - Contains Duplicate II.
  • LC 220 - Contains Duplicate III.
  • LC 287 - Find the Duplicate Number.

6.2 Longest Consecutive Sequence (LC 128)

Đề bài

Cho mảng nums không sort. Trả về độ dài của dãy số liên tiếp (consecutive integers, có thể không đứng cạnh trong mảng) dài nhất. Phải chạy O(n).

Ví dụ 

Input:  nums = [100, 4, 200, 1, 3, 2]
Output: 4
Giải thích: dãy [1, 2, 3, 4] dài 4.

Input:  nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Giải thích: dãy [0, 1, 2, 3, 4, 5, 6, 7, 8].

Input:  nums = []
Output: 0

Ràng buộc

  • 0 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9

Clarifying questions

  • “Liên tiếp” theo giá trị hay theo index? → Theo giá trị (consecutive integers).
  • Có duplicate trong nums? → Có thể; xử lý tự nhiên bằng set.
  • Có cho phép sort không? → Theo đề là O(n), sort O(n log n) không thoả.

Hướng tiếp cận

Brute force - O(n³). Với mỗi phần tử, đếm số x, x+1, x+2, ... có trong mảng.

Sort - O(n log n). Sort, đếm dãy liên tiếp. Đơn giản nhưng không thoả O(n).

Tối ưu - Hash Set + “chỉ bắt đầu từ điểm đầu dãy” - O(n).

Insight then chốt: Một số x là điểm bắt đầu dãy ↔︎ x - 1 không có trong mảng. Vậy chỉ với những x thoả điều kiện này, ta mới đếm dãy x, x+1, x+2, ... bằng cách lookup hash. Mỗi phần tử bị “đếm tới” tối đa 1 lần trên toàn quá trình → tổng O(n).

Hình minh hoạ với nums = [100, 4, 200, 1, 3, 2]:

Set: {100, 4, 200, 1, 3, 2}

Duyệt từng x trong set:
  x=100: 99 không có trong set → là điểm bắt đầu
         Đếm: 100 ✓, 101 ✗  → length 1
  x=4:   3 CÓ trong set → SKIP (sẽ được đếm khi bắt đầu từ 1)
  x=200: 199 không có → là điểm bắt đầu
         Đếm: 200 ✓, 201 ✗  → length 1
  x=1:   0 không có → là điểm bắt đầu
         Đếm: 1 ✓, 2 ✓, 3 ✓, 4 ✓, 5 ✗  → length 4  ★
  x=3:   2 CÓ → SKIP
  x=2:   1 CÓ → SKIP

Tổng: max length = 4.

Chìa khoá: mỗi phần tử của dãy 1-2-3-4 chỉ được "duyệt forward" đúng 1 lần
            (khi x=1). Tổng công ~ O(n).

Code Python 3 

from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        best = 0
        for x in num_set:
            # Chỉ bắt đầu khi x là điểm đầu dãy (x-1 không có).
            if x - 1 not in num_set:
                cur = x
                length = 1
                while cur + 1 in num_set:
                    cur += 1
                    length += 1
                best = max(best, length)
        return best

Phân tích độ phức tạp

  • Thời gian: O(n) - mỗi phần tử bị “đếm forward” tối đa 1 lần.
  • Bộ nhớ: O(n) cho set.

Bình luận

  • Tại sao O(n)? Nhìn vào vòng while: nó chỉ chạy với những x mà x - 1 không trong set (điểm đầu dãy). Mỗi phần tử của 1 dãy độ dài L chỉ được duyệt 1 lần (khi vòng while chạy từ điểm đầu). Tổng Σ L = n.
  • Bẫy thường gặp:
    • Không có check x - 1 not in num_set → O(n²) vì mỗi điểm trong dãy đều khởi đầu vòng while → TLE.
    • Đếm length bắt đầu từ 0 - phải bắt đầu từ 1 (vì x đã là 1 phần tử).
  • Follow-up phổ biến:
    1. LC 298 - Binary Tree Longest Consecutive Sequence.
    2. LC 1218 - Longest Arithmetic Subsequence of Given Difference.
    3. Union Find version (Chương 24) - đẹp về lý thuyết nhưng overhead lớn.

Bài tự luyện liên quan

  • LC 298 - Binary Tree Longest Consecutive Sequence.
  • LC 1218 - Longest Arithmetic Subsequence of Given Difference.
  • LC 1014 - Best Sightseeing Pair.

6.3 Top K Frequent Elements (LC 347)

Đề bài

Cho mảng nums và số nguyên k. Trả về k phần tử thường gặp nhất (output order tuỳ ý).

Ví dụ 

Input:  nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]

Input:  nums = [1], k = 1
Output: [1]

Ràng buộc

  • 1 <= len(nums) <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • k được đảm bảo nằm trong [1, số phần tử phân biệt].
  • Phải tốt hơn O(n log n) (gợi ý của LC).

Clarifying questions

  • Output có cần sort theo frequency không? → Không (LC: bất kỳ thứ tự).
  • Nếu có tie ở vị trí thứ k? → Theo đề bảo đảm answer duy nhất; nhưng nên hỏi rõ.

Hướng tiếp cận

Cách 1 - Counter + sort - O(n log n). Đơn giản nhưng không thoả gợi ý LC.

Cách 2 - Min-heap kích thước k - O(n log k). Duy trì heap kích thước k; khi vượt thì pop phần tử ít tần suất nhất.

Cách 3 - Bucket sort theo frequency - O(n) - xịn nhất.

Frequency tối đa là n → tạo n + 1 bucket, bucket i chứa các phần tử có frequency i. Duyệt bucket từ cao xuống thấp, gom k phần tử.

Hình minh hoạ với nums = [1,1,1,2,2,3], k=2:

Bước 1: Counter → {1:3, 2:2, 3:1}

Bước 2: Bucket sort theo frequency (n=6, có 7 bucket 0..6):
  bucket[0] = []
  bucket[1] = [3]      # số 3 xuất hiện 1 lần
  bucket[2] = [2]      # số 2 xuất hiện 2 lần
  bucket[3] = [1]      # số 1 xuất hiện 3 lần
  bucket[4..6] = []

Bước 3: Duyệt bucket từ index 6 xuống:
  i=6: rỗng
  i=5: rỗng
  i=4: rỗng
  i=3: [1] → result = [1]
  i=2: [2] → result = [1, 2]   đủ k=2, dừng

Output: [1, 2]

Code Python 3 

import heapq
from collections import Counter
from typing import List

class Solution:
    """Cách 3 - Bucket sort, O(n)."""

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        n = len(nums)
        buckets: list[list[int]] = [[] for _ in range(n + 1)]
        for x, freq in cnt.items():
            buckets[freq].append(x)
        result: list[int] = []
        for freq in range(n, 0, -1):
            for x in buckets[freq]:
                result.append(x)
                if len(result) == k:
                    return result
        return result


class SolutionHeap:
    """Cách 2 - Min-heap kích thước k, O(n log k)."""

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        # heapq.nlargest dùng heap-based partial sort
        return heapq.nlargest(k, cnt.keys(), key=cnt.get)

Phân tích độ phức tạp

Cách Time Space
Counter + sort O(n log n) O(n)
Min-heap O(n log k) O(n)
Bucket sort O(n) O(n)

Bình luận

  • Khi nào dùng cách nào?
    • k = O(n) → bucket sort thắng.
    • k rất nhỏ (~10) trong khi n cực lớn → min-heap đỡ tốn space.
  • Bẫy thường gặp:
    • Quên cấp đủ buckets (cần n + 1 vì freq có thể bằng n).
    • Dùng max-heap thay vì min-heap size k → cần O(n log n) đầy đủ.
  • One-liner: Counter(nums).most_common(k) trả về list cặp (val, freq) - chắc chắn sẽ dùng trong production. Trong phỏng vấn, nên trình bày một trong 3 cách trên trước, rồi nhắc đến most_common.

Bài tự luyện liên quan

  • LC 692 - Top K Frequent Words (Chương 15).
  • LC 451 - Sort Characters By Frequency.
  • LC 215 - Kth Largest Element in an Array.

6.4 Subarray Sum Equals K (LC 560)

Đề bài

Cho mảng số nguyên nums và số k. Trả về số lượng subarray (liên tục) có tổng đúng bằng k.

Ví dụ 

Input:  nums = [1, 1, 1], k = 2
Output: 2
Giải thích: 2 subarray [1,1] (vị trí 0..1 và 1..2).

Input:  nums = [1, 2, 3], k = 3
Output: 2
Giải thích: [1,2] và [3].

Ràng buộc

  • 1 <= len(nums) <= 2·10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

Clarifying questions

  • Phần tử có thể âm không? → Có. Quan trọng! Vì nếu chỉ có số dương, ta có thể dùng sliding window. Có số âm → phải dùng prefix sum + hash.
  • Subarray rỗng có tính không? → Theo đề: không (length ≥ 1).

Hướng tiếp cận

Brute force - O(n²). Với mỗi i, tính prefix sum dần và check == k. Chấp nhận được nhưng không tối ưu.

Tối ưu - Prefix sum + Hash map - O(n).

Đặt P[i] = tổng nums[0..i-1] (P[0] = 0). Khi đó tổng subarray nums[j..i-1] = P[i] - P[j]. Subarray có tổng k ↔︎ P[i] - P[j] = k ↔︎ P[j] = P[i] - k.

→ Duyệt và đếm số j < i thoả P[j] == cur - k. Dùng dict đếm {prefix_sum: số lần xuất hiện}.

Hình minh hoạ với nums = [3, 4, 7, 2, -3, 1, 4, 2], k = 7:

i    :   0    1    2    3    4    5    6    7
nums :   3    4    7    2   -3    1    4    2
P[i+1]:  3    7   14   16   13   14   18   20
                  ↑                   ↑
                P[3]=14            P[7]=18  ←  P[7]-P[3]=4? KHÔNG, =4

Tay xét:
P[]   = [0, 3, 7, 14, 16, 13, 14, 18, 20]
counts = {0:1}                        cur=0
i=0  cur=3   (3-7=-4 not in counts)  add 3 → {0:1, 3:1}
i=1  cur=7   (7-7= 0 in counts: +1)  add 7 → {0:1, 3:1, 7:1}   answer=1
i=2  cur=14  (14-7=7 in counts: +1)  add 14 → ...              answer=2
i=3  cur=16  (16-7=9 not in counts)                            answer=2
i=4  cur=13  (13-7=6 not in counts)                            answer=2
i=5  cur=14  (14-7=7 in counts: +1)  cur cũ đã có → counts[14]+=1
                                                              answer=3
i=6  cur=18  (18-7=11 not in counts)                          answer=3
i=7  cur=20  (20-7=13 in counts: +1)                          answer=4

Đáp án: 4 subarray có tổng = 7.

Code Python 3 

from collections import defaultdict
from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        counts: dict[int, int] = defaultdict(int)
        counts[0] = 1            # prefix sum 0 đã xuất hiện 1 lần (rỗng)
        cur = 0
        result = 0
        for x in nums:
            cur += x
            result += counts[cur - k]    # bao nhiêu j thoả P[j] = cur - k
            counts[cur] += 1
        return result

Phân tích độ phức tạp

  • Thời gian: O(n).
  • Bộ nhớ: O(n).

Bình luận

  • Bẫy thường gặp:
    • Quên counts[0] = 1 ban đầu → bỏ sót các subarray bắt đầu từ index 0.
    • Tăng counts[cur] trước check → đếm cả j == i (subarray rỗng). Phải result += counts[cur - k] trước, sau đó mới counts[cur] += 1.
  • Pattern tổng quát: “đếm số cặp (i, j) thoả f(j) = g(i)” → luôn duy trì counts[f(j)] cho j < i. Xuất hiện nhiều trong:
    • LC 974 - Subarray Sums Divisible by K (key = prefix % k).
    • LC 525 - Contiguous Array (key = count(1) - count(0)).
    • LC 437 - Path Sum III (chạy trên cây).
  • Cảnh báo: Nếu chỉ có số dương → sliding window O(n) không cần hash. Có số âm → bắt buộc prefix sum.

Bài tự luyện liên quan

  • LC 974 - Subarray Sums Divisible by K.
  • LC 525 - Contiguous Array.
  • LC 437 - Path Sum III.

6.5 Isomorphic Strings (LC 205)

Đề bài

Hai chuỗi s và t gọi là đồng cấu (isomorphic) nếu tồn tại một song ánh giữa các ký tự của s và t sao cho thay thế từng ký tự trong s theo ánh xạ đó cho ra t.

Ví dụ 

Input:  s = "egg", t = "add"   → True
Giải thích: e→a, g→d (bijection).

Input:  s = "foo", t = "bar"   → False
Giải thích: o phải map cả vào a và r (không là hàm).

Input:  s = "paper", t = "title"   → True

Input:  s = "badc", t = "baba"   → False
Giải thích: d→a và c→a, hai ký tự khác map vào cùng 1 → vi phạm song ánh.

Ràng buộc

  • 1 <= len(s) == len(t) <= 5·10^4
  • s, t chứa ký tự ASCII bất kỳ.

Clarifying questions

  • Song ánh? Cả 2 chiều phải injective? → Có. f: s → t và g: t → s phải injective.
  • s và t có cùng độ dài không? → Theo đề: có. Nếu không, return False ngay.

Hướng tiếp cận

Cách 1 - Dùng 2 dict (map cả 2 chiều).

Duyệt cùng lúc 2 chuỗi: - Nếu s[i] đã trong s2t → check s2t[s[i]] == t[i]. - Nếu chưa → kiểm tra t[i] chưa nằm trong t2s (tránh nhiều s map vào cùng 1 t). - Lưu cặp (s[i], t[i]) vào cả 2 dict.

Cách 2 - Thay bằng “first occurrence index”.

Một chuỗi có thể được “chuẩn hoá” bằng cách thay mỗi ký tự bằng vị trí xuất hiện đầu tiên của nó. Hai chuỗi isomorphic ↔︎ chuẩn hoá xong giống nhau.

Ví dụ "egg" → [0, 1, 1], "add" → [0, 1, 1] → bằng nhau → True.

Cách 1 trực quan hơn, cách 2 đẹp về mặt thuật toán. Cả 2 đều O(n).

Code Python 3 

class Solution:
    """Cách 1 - 2 dict, kiểm tra song ánh."""

    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        s2t: dict[str, str] = {}
        t2s: dict[str, str] = {}
        for a, b in zip(s, t):
            if a in s2t:
                if s2t[a] != b:
                    return False
            else:
                if b in t2s:        # b đã được map từ ký tự khác
                    return False
                s2t[a] = b
                t2s[b] = a
        return True


class SolutionNormalize:
    """Cách 2 - chuẩn hoá theo first-occurrence index."""

    def isIsomorphic(self, s: str, t: str) -> bool:
        return self._normalize(s) == self._normalize(t)

    @staticmethod
    def _normalize(s: str) -> list[int]:
        idx: dict[str, int] = {}
        out: list[int] = []
        for ch in s:
            if ch not in idx:
                idx[ch] = len(idx)
            out.append(idx[ch])
        return out

Phân tích độ phức tạp

  • Thời gian: O(n).
  • Bộ nhớ: O(k) với k = số ký tự phân biệt.

Bình luận

  • Bẫy thường gặp:
    • Chỉ dùng 1 dict s2t → bỏ sót case nhiều s map cùng 1 t (như "badc"/"baba").
    • Quên check độ dài bằng nhau.
  • Follow-up phổ biến:
    1. LC 290 - Word Pattern: tương tự nhưng pattern là chuỗi ký tự, words là list chuỗi.
    2. LC 49 - Group Anagrams: dùng “chữ ký” để gom (Chương 2).

Bài tự luyện liên quan

  • LC 290 - Word Pattern.
  • LC 242 - Valid Anagram.
  • LC 49 - Group Anagrams.

6.6 LRU Cache (LC 146)

Đề bài

Thiết kế Least Recently Used (LRU) Cache với 2 operations đều O(1):

  • get(key): trả value của key nếu có, ngược lại trả -1. Mỗi lần truy cập thành công làm key đó “vừa dùng” (most recently used).
  • put(key, value): thêm/cập nhật. Nếu vượt capacity, xoá key ít dùng gần nhất (least recently used).

Ví dụ 

Input (LC-style operation arrays):
  ops  = ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
  args = [[2],        [1,1], [2,2], [1],   [3,3], [2],   [4,4], [1],   [3],   [4]]

Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Trace từng bước (capacity = 2; cuối phải = MRU, trái = LRU):

  LRUCache(2)         → null;   cache = {}                    (LRU ← → MRU)
  put(1, 1)           → null;   cache = {1=1}
  put(2, 2)           → null;   cache = {1=1, 2=2}
  get(1)              → 1;      cache = {2=2, 1=1}   (1 vừa dùng → MRU)
  put(3, 3)           → null;   cache = {1=1, 3=3}   (evict 2: LRU)
  get(2)              → -1;     (key 2 không còn)
  put(4, 4)           → null;   cache = {3=3, 4=4}   (evict 1)
  get(1)              → -1
  get(3)              → 3;      cache = {4=4, 3=3}
  get(4)              → 4;      cache = {3=3, 4=4}

Ràng buộc

  • 1 <= capacity <= 3000
  • 0 <= key, value <= 10^4
  • Tối đa 2·10^5 lệnh get và put.

Clarifying questions

  • Khi put 1 key đã tồn tại? → Cập nhật value và đẩy key thành MRU.
  • Thread-safe có yêu cầu không? → Theo LC: không, single thread.

Hướng tiếp cận

Yêu cầu cốt lõi: O(1) cho cả get và put ↔︎ cần đồng thời: - Hash map: key → reference đến node (cho O(1) lookup). - Doubly Linked List (DLL): thứ tự truy cập (MRU ở 1 đầu, LRU ở đầu kia). Cho phép xoá node bất kỳ trong O(1) nếu có reference.

Mỗi get(k): - Nếu k trong map → lấy node, di chuyển node lên đầu DLL (= MRU), trả value. - Ngược lại trả -1.

Mỗi put(k, v): - Nếu k đã có → update value, di chuyển lên đầu. - Nếu không → thêm node mới ở đầu. Nếu vượt capacity → xoá node cuối (LRU) và xoá khỏi map.

Cách Pythonic - dùng OrderedDict (đã hỗ trợ sẵn 2 yêu cầu trên):

OrderedDict Python được triển khai bên dưới như hash map kết hợp doubly linked list. Lớp này có 2 method đắt giá cho LRU: move_to_end(key) và popitem(last=False) (pop đầu).

Hình minh hoạ - DLL state qua các operation:

capacity = 2
                    Head (MRU)              Tail (LRU)
                          │                       │
                          ▼                       ▼
put(1,1):   DLL:    1                              cache = {1: node1}
put(2,2):   DLL:    2 ─── 1                       cache = {1: ., 2: .}
get(1)=1:   DLL:    1 ─── 2     (1 → MRU)
put(3,3):   DLL:    3 ─── 1     (xoá 2 vì LRU)
get(2)=-1
put(4,4):   DLL:    4 ─── 3     (xoá 1)
get(1)=-1
get(3)=3:   DLL:    3 ─── 4
get(4)=4:   DLL:    4 ─── 3

Code Python 3 

from collections import OrderedDict

class LRUCache:
    """Cách Pythonic - OrderedDict đã có sẵn DLL + hash."""

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)        # đẩy thành MRU (cuối)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # pop LRU ở đầu


# ─────────────────────────────────────────────────────────────
# Phiên bản tự tay (interview-friendly): dict + doubly linked list.
# Trình bày khi interviewer hỏi: "Implement LRU không dùng built-in."

class _Node:
    __slots__ = ("key", "val", "prev", "next")

    def __init__(self, key: int = 0, val: int = 0):
        self.key, self.val = key, val
        self.prev: "_Node | None" = None
        self.next: "_Node | None" = None


class LRUCacheManual:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: dict[int, _Node] = {}
        # Dùng 2 sentinel head/tail để code rút gọn (không phải check None).
        self.head, self.tail = _Node(), _Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: _Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: _Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._add_to_front(node)
            return
        if len(self.cache) == self.cap:
            lru = self.tail.prev          # LRU = sát tail
            self._remove(lru)
            del self.cache[lru.key]
        new_node = _Node(key, value)
        self.cache[key] = new_node
        self._add_to_front(new_node)

Phân tích độ phức tạp

  • Thời gian: O(1) cho cả get và put (amortized).
  • Bộ nhớ: O(capacity).

Bình luận

  • Tại sao cần DLL + dict?
    • Dict đảm bảo O(1) lookup theo key.
    • DLL cho phép xoá/chèn O(1) ở bất kỳ vị trí nào khi đã có reference. Singly LL không làm được vì cần prev.
  • Bẫy thường gặp:
    • Quên cập nhật value khi put(k) với k đã tồn tại.
    • Sentinel head/tail giúp tránh nhiều nhánh kiểm tra None; trong phỏng vấn nên ưu tiên cách này để code rõ ràng và ít bug biên.
    • Xoá node ra khỏi DLL nhưng quên xoá khỏi dict.
  • Tại sao Big Tech rất hay hỏi bài này?
    • Test 4 thứ cùng lúc: hash, linked list, design class, edge cases.
    • Là component thật trong CPU cache, OS page replacement, Redis, …
  • Follow-up phổ biến:
    1. LFU Cache (LC 460) - Least Frequently Used. Khó hơn nhiều, cần 2 dict + 2 DLL.
    2. Thread-safe LRU - bọc lock hoặc dùng concurrent.OrderedDict.
    3. TTL-based cache - thêm expire time.

Bài tự luyện liên quan

  • LC 460 - LFU Cache.
  • LC 432 - All O(1) Data Structure.
  • LC 1166 - Design File System.

Tóm tắt chương & Quyết định

Khi hash KHÔNG đủ

Yêu cầu Hash đủ? Thay thế
Lookup O(1), không cần thứ tự ✅ -
Cần thứ tự duyệt ❌ OrderedDict / sorted list
Range query [l, r] ❌ Fenwick / Segment Tree (Chương 22)
Top-k frequent Partial Heap (Chương 15)
Nearest neighbor ❌ Sorted set / BST
Subarray sum có số âm ✅ Prefix sum + hash -
Subarray sum không âm Thường dùng sliding window (27) -

LRU 2 cách

  • OrderedDict (move_to_end): 5 dòng, demo tốt cho phỏng vấn.
  • Dict + Doubly Linked List custom: thể hiện hiểu rõ amortized O(1) cho cả get/put. Phỏng vấn senior thường yêu cầu cài.

Longest Consecutive - vì sao O(n)?

  • Mỗi số là starter chỉ khi x - 1 ∉ set. Mỗi chain chỉ có một starter ⇒ tổng chi phí “đi tới hết chain” cộng dồn = O(n).
  • Nếu thiếu điều kiện starter, mỗi số chạy chain → O(n²) worst-case.