Mini-challenge — Autocomplete top-K với Trie + frequency

Bạn đang build search box cho sàn e-commerce có 1 triệu sản phẩm. Người dùng gõ "lap" — hệ thống cần trả về ngay top 5 sản phẩm phù hợp prefix đó, sắp xếp theo lượt tìm gần đây.

Giải pháp: kết hợp Trie (bài 08) để tìm prefix trong O(L) với frequency lưu tại mỗi node — sau đó DFS subtree từ prefix node và dùng min-heap để extract top-K hiệu quả.

Sau bài này bạn implement được autocomplete pattern Google search box, e-commerce search bar dùng — backbone của bộ gợi ý.

🎯 Yêu cầu bài toán

Viết cấu trúc Autocomplete với API sau:

• insert(word, frequency) — insert hoặc cộng dồn frequency cho word. Gọi nhiều lần cùng word thì cộng dồn frequency.
• suggest(prefix, k) — trả về top K word có prefix matching, sorted giảm dần theo frequency. Tie-break: alphabetical tăng dần.

Yêu cầu Big-O:

Constraint: 1 triệu word, alphabet a-z, độ dài tối đa 20.

📦 Starter — cấu trúc dữ liệu và interface

-- Cấu trúc node của Trie
AutocompleteNode:
    children: Map<ký_tự, AutocompleteNode>
    frequency: int      -- 0 nếu không phải cuối từ
    word: String        -- null nếu không phải cuối từ

-- Interface cần implement
Autocomplete:
    root: AutocompleteNode

    insert(word, frequency):
        -- TODO

    suggest(prefix, k):
        -- TODO: trả về List<String>

Dành 20–25 phút tự làm trước khi xem gợi ý.

🧪 Test cases

a <- Autocomplete mới
a.insert("laptop", 50)
a.insert("lap", 10)
a.insert("lapis", 30)
a.insert("legend", 5)

assert a.suggest("la", 3)  = ["laptop", "lapis", "lap"]
assert a.suggest("lap", 1) = ["laptop"]
assert a.suggest("xyz", 5) = []

-- tie-break: cùng frequency -> alphabetical tăng dần
a.insert("apple", 20)
a.insert("apply", 20)
assert a.suggest("ap", 2) = ["apple", "apply"]

💡 Gợi ý

✅ Lời giải

-- Cấu trúc Node
Node:
    children: Map<ký_tự, Node>
    frequency: int     -- 0 nếu không phải cuối từ
    word: String       -- null nếu không phải cuối từ

-- Cấu trúc chính
Autocomplete:
    root: Node mới (rỗng)

-- Insert word với frequency (cộng dồn nếu gọi lại)
insert(word, frequency):
    node <- root
    for each ký_tự c trong word:
        if c không trong node.children:
            node.children[c] <- Node mới
        node <- node.children[c]
    node.frequency <- node.frequency + frequency   -- cộng dồn khi insert lại
    node.word <- word

Time: O(L)  Space: O(L) cho node mới trên path

-- Suggest top K word có prefix matching
suggest(prefix, k):
    -- Bước 1: walk xuống trie theo prefix
    node <- root
    for each ký_tự c trong prefix:
        node <- node.children.get(c)
        if node = null: return []          -- prefix không tồn tại

    -- Bước 2: DFS subtree + min-heap kích thước k
    -- Comparator: evict phần tử "kém giá trị nhất" trước
    --   kém nhất = frequency thấp nhất; nếu bằng = alphabetically lớn nhất
    heap <- MinHeap(key: (frequency tăng dần; tie: word giảm dần alphabetical))
    collect(node, heap, k)

    -- Bước 3: poll + đảo ngược (heap pop nhỏ nhất trước)
    result <- []
    while heap không rỗng:
        result.append(heap.poll().word)
    result.reverse()
    return result

Time: O(L + matches × log K)  Space: O(k)

-- DFS collect: thêm word vào min-heap, giữ size <= k
collect(node, heap, k):
    if node.word != null:
        heap.push(node)
        if heap.size() > k:
            heap.poll()                -- evict phần tử kém nhất
    for each child trong node.children.values():
        collect(child, heap, k)

⚠️ Pitfall phổ biến

Pitfall 1 — Quên word field, phải maintain prefix string trong DFS.

-- LỘN XỘN: không có word field -- phải mang prefix string qua đệ quy
collect(node, currentPrefix, heap, k):
    if node.frequency > 0:
        heap.push(currentPrefix)      -- cấp phát string mỗi lần
    for each (ký_tự c, child) trong node.children:
        collect(child, currentPrefix + c, heap, k)   -- O(L) allocation mỗi bước

Lưu word tại end node: đánh đổi memory lấy code sạch hơn, tránh O(L) string allocation mỗi bước DFS. Với 1 triệu word, mỗi string tối đa 20 ký tự — tổng memory là manageable.

Pitfall 2 — Sort full subtree thay min-heap top-K.

-- CHẬM: sort toàn bộ match rồi lấy K đầu
all <- []
collectAll(node, all)
all.sort(theo frequency giảm dần)
return all[0..k-1]

-- O(matches × log matches) thay vì O(matches × log K)
-- K=5, matches=10.000: sort tốn ~140k so sánh; min-heap top-5 tốn ~30k so sánh

Pitfall 3 — Comparator ngược chiều cho tie-break.

Min-heap giữ lại phần tử lớn hơn theo comparator (phần tử nhỏ hơn bị evict). Để giữ word alphabetically nhỏ hơn (ưu tiên "apple" hơn "apply" khi frequency bằng nhau), comparator phải xem "apply" là nhỏ hơn trong heap:

-- SAI: giữ "apply" hơn "apple" khi tie -- đảo ngược priority alphabetical
comparator(a, b):
    if a.frequency != b.frequency: return a.frequency - b.frequency
    return a.word.compareTo(b.word)     -- "apple" < "apply" => "apple" bị evict trước -- sai!

-- ĐÚNG: "apply" "nhỏ hơn" trong heap => bị evict trước => giữ "apple"
comparator(a, b):
    if a.frequency != b.frequency: return a.frequency - b.frequency
    return b.word.compareTo(a.word)     -- đảo ngược: "apply" < "apple" trong heap

Test kỹ với tie-break case trước khi tin vào comparator logic.

📊 Benchmark tham khảo

1M words, 100k suggest calls, K=10:

  Naive HashMap full scan:       ~120s
  Trie + DFS + sort:             ~2s
  Trie + DFS + min-heap:         ~1.5s
  Trie + pre-cached top-K/node:  ~0.1s

Min-heap thắng sort rõ khi K nhỏ. Pre-cached top-K thắng tất cả cho query-heavy workload — nhưng insert chậm hơn và tốn memory hơn (trade-off section dưới).

🔀 Variant để tự thử

Variant 1 — Pre-cache top-K mỗi node (optimize suggest về O(L)):

Thay vì DFS mỗi lần suggest, lưu sẵn top-K list trong mỗi node. Khi insert, walk xuống từng node trên path và cập nhật top-K list tại mỗi node. suggest chỉ cần walk tới prefix node và trả về node.topK — O(L).

Trade-off: insert tốn O(L × K log K) thay vì O(L). Phù hợp khi suggest call rate cao hơn nhiều so với insert — điển hình cho production search box (vocabulary ổn định, query liên tục).

Variant 2 — Fuzzy matching với edit distance 1:

Prefix hiện tại yêu cầu exact match. Nếu user gõ "latop" thay vì "lapto" — bài này trả về rỗng. Thêm "tolerate 1 typo": DFS với counter mismatch cho phép, dừng nhánh khi counter vượt 1. Phức tạp hơn đáng kể. Cross-link: Thuật toán Ứng dụng — Module 2 (Levenshtein automaton — sẽ cover).

Variant 3 — Personalized frequency:

Thêm dimension user-specific: mỗi user có lịch sử search riêng. Approach 1: global Trie + per-user frequency map — suggest lấy global matches rồi re-rank theo user preference. Approach 2: per-user Trie — memory tốn nhưng query sạch hơn. Với 1 triệu user và 1 triệu word, per-user Trie hoàn toàn không khả thi — approach 1 (global trie + re-rank) là hướng sản phẩm thực tế.

🏭 Applied note

Elasticsearch completion field type — dùng Finite State Transducer (FST), là variant nén của trie. FST encode trie thành minimal acyclic finite automaton, tiết kiệm memory hơn trie thường với alphabet lớn. Suggest O(prefix length), không cần DFS subtree.

Lucene — engine dưới Elasticsearch, dùng FST cho term dictionary. Mỗi segment có FST riêng, không phải single global trie — cho phép merge và delete segment hiệu quả.

Google Search box — multi-tier: tier 1 là trie + pre-cached top-K per prefix (bài này, Variant 1), tier 2 là ML ranker personalize dựa trên user history, tier 3 là spell corrector (Levenshtein automaton + language model). Bài này là tier 1 — foundation của toàn bộ pipeline.

Cross-link: Thuật toán Ứng dụng — Module 2 (String Matching — Aho-Corasick, Levenshtein), Thuật toán Ứng dụng — Module 6 (Search Engine — full-text indexing, ranking).

✨ Điều bạn vừa làm được

• Extend Trie cơ bản (bài 08) với frequency field để support top-K ranked autocomplete.
• Implement DFS subtree collect + min-heap kích thước K: O(matches × log K) thay vì O(matches × log matches).
• Nắm tie-break comparator logic cho min-heap: cần invert hướng để heap giữ đúng phần tử.
• Hiểu trade-off lazy DFS vs pre-cached top-K: insert speed vs query speed.
• Biết pattern này là tier 1 của Google Search, Elasticsearch completion suggester, và e-commerce search bar.

Bài tiếp theo: Case Study: MySQL InnoDB B+tree + Redis dict rehash