1.1 Bit Operators — Bộ công cụ

Tính chất XOR — quan trọng nhất

• x ^ x = 0 — XOR với chính nó = 0.
• x ^ 0 = x — XOR với 0 không đổi.
• a ^ b ^ a = b — XOR có tính giao hoán + kết hợp.

Ba tính chất này tạo nên trick "Single Number" và nhiều bài XOR khác.

1.2 Common Bit Tricks — Phải thuộc

1.3 Worked Example 1 — Single Number (#136)

Đề: Mảng nums. Mọi phần tử xuất hiện 2 lần, trừ 1 phần tử xuất hiện 1 lần. Tìm nó. Yêu cầu O(n) time, O(1) space.

Approach hashing — không thoả O(1) space

def singleNumber(nums):
    seen = set()
    for x in nums:
        if x in seen: seen.remove(x)
        else: seen.add(x)
    return seen.pop()
# O(n) time, O(n) space — vi phạm

Approach XOR — đẹp như thơ

def singleNumber(nums):
    result = 0
    for x in nums:
        result ^= x
    return result
# Hoặc: from functools import reduce; reduce(xor, nums)

Time O(n), Space O(1).

1.4 Worked Example 2 — Number of 1 Bits (#191)

Đề: Cho số nguyên n. Đếm số bit 1 trong biểu diễn nhị phân.

Approach 1 — Duyệt 32 bit

def hammingWeight(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count
# O(32) = O(1)

Approach 2 — Brian Kernighan (chỉ duyệt số bit on)

def hammingWeight(n):
    count = 0
    while n:
        n &= n - 1                      # bỏ LSB
        count += 1
    return count
# Chạy đúng k = số bit on. Khi k << 32, nhanh hơn.

Approach 3 — Python idiom

def hammingWeight(n):
    return bin(n).count('1')
# Hoặc: n.bit_count()  (Python 3.10+)

Trong phỏng vấn, viết approach 2 (Brian Kernighan) sẽ thể hiện chiều sâu — nhiều người chỉ biết approach 1.

1.5 Worked Example 3 — Counting Bits (#338)

Đề: Cho n. Trả mảng ans[i] = số bit 1 trong i, với i = 0..n.

Approach ngây thơ — gọi #191 cho mỗi i

O(n × 32) — đủ pass nhưng không tận dụng được tính chất.

Approach DP — O(n)

Quan sát: ans[i] = ans[i >> 1] + (i & 1).

• i >> 1: i bỏ LSB.
• i & 1: LSB của i (0 hoặc 1).
• Tổng số bit của i = số bit của (i bỏ LSB) + LSB.

def countBits(n):
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        ans[i] = ans[i >> 1] + (i & 1)
    return ans

Time O(n), Space O(n).

1.6 Bitmask DP — Giới thiệu

Khi tập items có size n nhỏ (≤ 20), có thể dùng bitmask để biểu diễn subset:

• Bit i = 1 ⟺ item i thuộc subset.
• 2ⁿ subsets ↔ 2ⁿ giá trị bitmask 0..2ⁿ-1.

Ví dụ: Travelling Salesman Problem nhỏ

# dp[mask][i] = chi phí thấp nhất thăm tập 'mask' và kết thúc tại i
# Recurrence: dp[mask][i] = min(dp[mask ^ (1<<i)][j] + dist[j][i])
#                            cho mọi j thuộc mask, j != i

Time O(2ⁿ × n²). Với n = 15, ~7 triệu ops — chấp nhận được.

Tín hiệu nhận biết Bitmask DP

• Constraint n ≤ 15..20.
• Bài liên quan tập subset / permutation / cover.
• Brute force là O(n!) hoặc O(2ⁿ × n) — bitmask đẹp hơn.

Đây là kỹ thuật nâng cao — không bắt buộc thuộc nhưng nên biết để khi gặp constraint nhỏ bất thường.

Knowledge Check — Bit Manipulation

2.1 Trie là gì?

Operations và complexity

• Insert(word): O(L) với L = len(word).
• Search(word): O(L).
• StartsWith(prefix): O(P) với P = len(prefix).

So với hashing: hash O(L) cho lookup chính xác — không hỗ trợ prefix search hiệu quả. Trie có thêm prefix.

2.2 Trie Implementation

class TrieNode:
    def __init__(self):
        self.children = {}            # ký tự → TrieNode
        self.is_end = False           # đánh dấu kết thúc 1 từ

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word):
        node = self._traverse(word)
        return node is not None and node.is_end

    def startsWith(self, prefix):
        return self._traverse(prefix) is not None

    def _traverse(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Đây là WE4: Implement Trie (#208). Time mỗi op O(L), Space O(tổng độ dài tất cả words).

2.3 Worked Example 5 — Word Search II (Hard)

Đề (LeetCode #212): Lưới ký tự + danh sách words. Trả về mọi từ trong words tìm được trên lưới (4 hướng, không lặp ô).

Brute force

Với mỗi word, gọi Word Search (#79, Tuần 11). Time O(M × N × số_word × 4^L) — chậm với nhiều word.

Trie + Backtracking — O(M × N × 4^L)

Build Trie từ tất cả words. DFS một lần qua lưới, đi theo cây Trie:

def findWords(board, words):
    # Build Trie
    root = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node['$'] = w                           # lưu từ khi end

    res = []
    m, n = len(board), len(board[0])
    def dfs(r, c, node):
        ch = board[r][c]
        if ch not in node: return
        nxt = node[ch]
        if '$' in nxt:
            res.append(nxt.pop('$'))           # tìm thấy từ, xoá để không trùng
        board[r][c] = '#'
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < m and 0 <= nc < n and board[nr][nc] != '#':
                dfs(nr, nc, nxt)
        board[r][c] = ch
    for r in range(m):
        for c in range(n):
            dfs(r, c, root)
    return res

2.4 Word Search II — Vì sao Trie nhanh hơn?

Brute force vs Trie approach

Pruning quan trọng — xoá khi tìm thấy

nxt.pop('$'): khi tìm thấy 1 từ, xoá khỏi Trie. Lần sau gặp prefix này nhưng không có từ → có thể prune.

Pruning nâng cao — xoá lá

Khi DFS quay lại và thấy node Trie không còn con → xoá node khỏi cha. Lần thăm sau biết "không còn từ nào ở nhánh này" → dừng sớm.

Knowledge Check — Trie

3.1 UMPIRE — Khung sườn 6 bước

UMPIRE là acronym của 6 bước nên thực hiện trong mỗi phỏng vấn coding. Tổng thời gian khuyến nghị 45 phút.

3.2 Bước U-M-P — Thực hành

U — Understand: 5 câu hỏi cần hỏi

1. Range của input? (n có thể lên 10⁵, 10⁹...?)
2. Có giá trị âm? Có duplicate? Có rỗng?
3. Output format chính xác là gì?
4. Có nhiều test case hay 1 lần?
5. Edge case: input rỗng, 1 phần tử, đã sort?

M — Match: 4 nhóm pattern phổ biến

• Array/String → Two Pointers, Sliding Window, Prefix Sum, Hashing.
• Tree/Graph → DFS, BFS, Topological, Union-Find, Dijkstra.
• Optimisation/Counting → DP (1D, 2D), Greedy.
• Search/Sort → Binary Search, Quick Select, Merge Sort.

P — Plan: Pseudocode 5-7 dòng

# Two Sum example pseudocode
# 1. Build hash map: value → index
# 2. For each (i, num):
#    - If target - num in map: return [map[target-num], i]
#    - Else: map[num] = i
# Time O(n), Space O(n)

Viết pseudocode ngắn trên whiteboard/note rồi mới code thật.

3.3 Communication Tips — Yếu tố thắng phỏng vấn

Think out loud — Nói khi đang nghĩ

• "Em đang nghĩ approach 1 là brute force O(n²) — duyệt mọi cặp."
• "Có thể tối ưu bằng hash map để giảm xuống O(n)."
• "Edge case em nghĩ: mảng rỗng → trả [] sớm."

Bốn cụm từ "vàng" trong phỏng vấn

1. "Để em làm rõ đề..." — tránh hiểu sai.
2. "Em nghĩ approach naive là... rồi sẽ tối ưu sau." — show thinking process.
3. "Trade-off ở đây là..." — show senior thinking.
4. "Em test trên ví dụ này..." — show debug skill.

Khi bí — đừng im lặng

Nói: "Em hơi bí, em sẽ thử cách khác — start với brute force để có baseline rồi cải tiến." Interviewer thích người không hoảng loạn — không thích người im lặng nhìn màn hình 5 phút.

Khi sai — đừng giấu

Nếu phát hiện bug giữa code, nói thẳng: "Em phát hiện lỗi ở dòng X — em sẽ sửa." Tự tìm ra bug được điểm cao hơn nhiều so với bị interviewer chỉ ra.

3.4 10 Common Interview Mistakes — Tránh ngay

1. Nhảy thẳng vào code mà không Understand.
2. Im lặng nghĩ > 30s — interviewer không biết đầu em đang ở đâu.
3. Không hỏi clarifying questions — assume sai input format.
4. Bỏ qua complexity analysis — không nói O(n) sau khi code xong.
5. Không test code sau khi viết — bug rõ ràng vẫn submit.
6. Code lộn xộn, không có comment — interviewer phải đoán logic.
7. Không xử lý edge cases — empty, single element, all same.
8. Cố gắng "sửa cho tốt" khi đang chạy đua thời gian — submit working version trước.
9. Phản ứng tiêu cực khi bị hint — hint là dấu hiệu interviewer muốn em thành công.
10. Không hỏi về role/team ở cuối — bỏ lỡ cơ hội thể hiện sự quan tâm.

4.1 Pattern Recognition Cheat Sheet — 14 tuần

4.2 Worked Example 7 — LRU Cache (#146) — Mock Interview

Đề: Thiết kế Least Recently Used Cache với capacity. Hỗ trợ:

• get(key): trả value nếu có, -1 nếu không. O(1).
• put(key, value): thêm/cập nhật. Nếu đầy, evict key ít dùng nhất. O(1).

U — Understand

• "capacity là cố định?" Yes.
• "Get/put cùng được tính là 'used'?" Yes.
• "Edge case: capacity = 0? key đã tồn tại khi put?" Cần xử lý.

M — Match

Cần O(1) lookup → HashMap (Tuần 3). Cần O(1) thao tác hai đầu (most recent + least recent) → Doubly Linked List (Tuần 5). Combo của 2 pattern!

P — Plan

# HashMap: key → node trong DLL
# DLL: head ←→ ... ←→ tail
# get: tra hash → move node lên front
# put: nếu key có → update + move; nếu không → add front, evict tail nếu vượt capacity

4.3 LRU Cache — Implementation

class Node:
    def __init__(self, key=0, val=0):
        self.key = key; self.val = val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}                          # key → node
        self.head = Node(); self.tail = Node()    # dummy
        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_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

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

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self._add_front(node)
        self.cache[key] = node
        if len(self.cache) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

4.4 LRU Cache — Tinh thần "Combine Patterns"

R — Review & E — Evaluate

Test case mẫu: capacity=2, put(1,1), put(2,2), get(1)=1, put(3,3) (evict 2), get(2)=-1.

Sau put(1,1): {1:N1}, DLL: head ↔ N1 ↔ tail
Sau put(2,2): {1:N1, 2:N2}, DLL: head ↔ N2 ↔ N1 ↔ tail
Sau get(1) = 1: move N1 lên front → DLL: head ↔ N1 ↔ N2 ↔ tail
Sau put(3,3): cap đầy → evict N2 (cuối). {1:N1, 3:N3}, DLL: head ↔ N3 ↔ N1 ↔ tail
Sau get(2): không có → -1 ✓

Complexity

Get/put đều O(1). Space O(capacity).

Bài học từ LRU Cache

• Không có cấu trúc đơn lẻ giải được — phải combine 2.
• HashMap cho O(1) lookup; DLL cho O(1) thao tác hai đầu + remove ở giữa.
• Dummy head/tail (Tuần 5) loại bỏ edge case khi list rỗng.

4.5 Sample Mock Interview Script

Đề: "Cho mảng nums và k. Tìm subarray dài nhất có nhiều nhất k loại số khác nhau."

Phỏng vấn 45 phút mẫu

[Phút 0-3] Understand:
Em: "Để em làm rõ — subarray là liên tiếp, đúng không?"
Anh: "Đúng."
Em: "n có thể lên bao nhiêu? Có số âm?"
Anh: "n ≤ 10⁵, mọi số nguyên."
Em: "Edge case: k = 0 → trả 0; mảng rỗng → trả 0."

[Phút 3-5] Match:
Em: "Đề có 'subarray liên tiếp' + 'điều kiện trên window' → em nghĩ đây là Sliding Window
     biến thể, tương tự #340 Longest Substring K Distinct Characters."

[Phút 5-10] Plan:
Em: "Em dùng Variable Window:
     - Counter theo dõi loại số trong window.
     - Right mở rộng window.
     - Khi len(counter) > k: shrink left cho đến khi ≤ k.
     - Cập nhật max length.
     Time O(n), Space O(k)."

[Phút 10-30] Implement: viết code, nói to mỗi bước.

[Phút 30-40] Review & Evaluate:
Em trace với [1,2,1,2,3], k=2 → expect 4 ([1,2,1,2]).
Em check edge: k=0, k >= n.

[Phút 40-45] Discussion:
Em: "Có thể tối ưu nếu k cố định và luôn ≤ 26 (chữ cái) — dùng array thay dict
     để giảm hằng số. Cũng có thể chuyển sang stream nếu input đến từng phần."
Anh: hỏi follow-up.

5.1 Lộ trình tự học sau khoá

1-3 tháng tiếp theo — Củng cố

• Code lại 30 bài đã học từ scratch, không nhìn lời giải. Đây là test retention thực sự.
• Mock interview tuần 1 lần — peer review hoặc dùng platforms như Pramp, interviewing.io.
• Thực hiện Daily Challenge LeetCode — 1 bài/ngày, kể cả khi đã giỏi.

3-6 tháng — Mở rộng

• Hard problems: làm 50 bài Hard từ NeetCode 150 hoặc Top 100 Hard.
• Competitive programming: Codeforces (Div 3-2), AtCoder Beginner Contest. Khác biệt với LeetCode: time pressure cao, problems bí ẩn hơn.
• Learn 1-2 thuật toán nâng cao: Segment Tree, Fenwick Tree, KMP, Network Flow, Suffix Array.

6-12 tháng — Áp dụng vào sự nghiệp

• System design: nếu nhắm phỏng vấn senior. Tham khảo "Designing Data-Intensive Applications".
• Open source contributions: contribute thuật toán cho dự án Python/JS open source.
• Phỏng vấn thật: bắt đầu apply ở mid-tier companies trước, sau đó FAANG.

5.2 Tài nguyên đáng dùng

Practice platforms

• NeetCode 150 (neetcode.io) — danh sách bài đã sắp xếp theo pattern, có video.
• LeetCode Premium — company-tagged questions (Google, Facebook list).
• Codility Lessons — task series 1-17.
• HackerRank Interview Prep Kit.
• Pramp (free) / interviewing.io — peer mock interviews.

Books

• Cracking the Coding Interview (Gayle McDowell) — chuẩn vàng phỏng vấn.
• Algorithm Design Manual (Skiena) — sâu hơn về thuật toán.
• CLRS — Introduction to Algorithms — reference cuốn cho graduate-level.

Online courses

• MIT 6.006 / 6.046 (free trên OCW) — algorithm classics.
• Princeton Algorithms (Sedgewick, Coursera).
• Educative — Grokking the Coding Interview — pattern-based.

Cộng đồng tiếng Việt

• Discord/Facebook các nhóm "LeetCode Việt Nam".
• VNOI — competitive programming Việt Nam.

Tổng kết toàn khoá — 14 tuần đã đi qua

Số liệu

• 14 tuần — khoảng 90 giờ học chủ đề.
• ~140 worked examples đã được phân tích chi tiết.
• ~150-160 bài về nhà nếu hoàn thành đầy đủ.
• 20+ patterns chuẩn cho mọi loại bài LeetCode/Codility.

Bộ kỹ năng đạt được

• Phân tích complexity Big-O cho mọi thuật toán.
• Nhận diện pattern từ tín hiệu trong đề.
• Thiết kế state cho DP cả 1D và 2D.
• Combine nhiều pattern để giải bài "boss" như Min Window Substring, Reorder List, Burst Balloons, LRU Cache.
• Trình bày lời giải mạch lạc qua quy trình UMPIRE.

Mức độ kỳ vọng đạt được

• LeetCode: giải 80% Easy, 50% Medium trong 30 phút.
• Codility: pass 60-70 điểm trong các đợt phỏng vấn entry/mid-level.
• Phỏng vấn FAANG mid-level: vượt qua coding round với chuẩn bị thêm 1-2 tháng.

Đây là điểm khởi đầu — chứ không phải đích đến. Hành trình tiếp tục.