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 class Autocomplete với API sau:

• void insert(String word, int 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.
• List<String> suggest(String prefix, int k) — trả về top K word có prefix matching, sorted desc theo frequency. Tie-break: alphabetical ascending.

Yêu cầu Big-O:

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

📦 Starter code

import java.util.*;

public class Autocomplete {
    // TODO: design data structure (Trie + frequency)

    public void insert(String word, int frequency) {
        // TODO
        throw new UnsupportedOperationException();
    }

    public List<String> suggest(String prefix, int k) {
        // TODO
        throw new UnsupportedOperationException();
    }
}

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

🧪 Test cases

Autocomplete a = new Autocomplete();
a.insert("laptop", 50);
a.insert("lap", 10);
a.insert("lapis", 30);
a.insert("legend", 5);

assertEquals(List.of("laptop", "lapis", "lap"), a.suggest("la", 3));
assertEquals(List.of("laptop"), a.suggest("lap", 1));
assertEquals(List.of(), a.suggest("xyz", 5));

// tie-break: same frequency -> alphabetical asc
a.insert("apple", 20);
a.insert("apply", 20);
assertEquals(List.of("apple", "apply"), a.suggest("ap", 2));

💡 Gợi ý

✅ Lời giải

import java.util.*;

public class Autocomplete {

    private static class Node {
        Map<Character, Node> children = new HashMap<>();
        int frequency; // 0 if not end of word
        String word;   // null if not end of word
    }

    private final Node root = new Node();

    public void insert(String word, int frequency) {
        Node node = root;
        for (char c : word.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new Node());
        }
        node.frequency += frequency; // accumulate on repeated insert
        node.word = word;
    }

    public List<String> suggest(String prefix, int k) {
        Node node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) return List.of();
        }

        // Min-heap of size k: comparator evicts least valuable first.
        // "Least valuable" = lowest frequency; on tie = alphabetically largest.
        PriorityQueue<Node> heap = new PriorityQueue<>(
            (a, b) -> a.frequency != b.frequency
                ? Integer.compare(a.frequency, b.frequency)
                : b.word.compareTo(a.word)
        );

        collect(node, heap, k);

        List<String> result = new ArrayList<>();
        while (!heap.isEmpty()) result.add(heap.poll().word);
        Collections.reverse(result); // heap pops smallest first; flip for desc
        return result;
    }

    private void collect(Node node, PriorityQueue<Node> heap, int k) {
        if (node.word != null) {
            heap.offer(node);
            if (heap.size() > k) heap.poll(); // evict least valuable
        }
        for (Node child : node.children.values()) {
            collect(child, heap, k);
        }
    }
}

⚠️ Pitfall phổ biến

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

// AWKWARD: no word field -- must carry prefix string through recursion
private void collect(Node node, String current,
                     PriorityQueue<String> heap, int k) {
    if (node.frequency > 0) {
        heap.offer(current); // string allocation every end-of-word
    }
    for (Map.Entry<Character, Node> e : node.children.entrySet()) {
        collect(e.getValue(), current + e.getKey(), heap, k); // O(L) allocation per step
    }
}

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.

// SLOW: sort all matches, then take first k
List<Node> all = new ArrayList<>();
collectAll(node, all);
all.sort((a, b) -> b.frequency - a.frequency);
return all.stream().limit(k).map(n -> n.word).toList();

O(matches × log matches) thay vì O(matches × log K). Với K=5 và matches=10.000: sort tốn khoảng 140k so sánh; min-heap top-5 tốn khoảng 30k so sánh — nhanh hơn gần 5 lần. Khi matches=100.000, gap càng lớn hơn.

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:

// WRONG: keeps "apply" over "apple" on tie -- inverted alphabetical priority
(a, b) -> a.word.compareTo(b.word)

// CORRECT: "apply" is "smaller" in the heap => evicted first => "apple" kept
(a, b) -> b.word.compareTo(a.word)

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: Module 7 (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: Module 7 (String Matching — Aho-Corasick, Levenshtein), Module 11 (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 size 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