Trie Autocomplete (LLD)

Trie autocomplete LLD design uses a prefix tree where each node holds children keyed by next character plus a cache of the top-K completions through that prefix. suggest(prefix, k) walks the trie character by character and returns the cached list at the terminal node, making lookup O(prefix length).

classDiagram
  class Trie {
    -root : TrieNode
    -k : int
    +insert(word, weight) void
    +search(word) bool
    +suggest(prefix, k) List~Suggestion~
    +incrementFrequency(word) void
  }
  class TrieNode {
    -children : Map~char, TrieNode~
    -isEnd : bool
    -word : string
    -frequency : long
    -topK : List~Suggestion~
    +addSuggestion(s) void
  }
  class Suggestion {
    +word : string
    +score : double
  }
  Trie --> TrieNode
  TrieNode --> Suggestion : caches top K

Source: Wikimedia Commons. CC BY-SA / public domain.

Without caching, autocomplete would walk every descendant of the prefix node to find the K best: O(descendants) per query, too slow at scale. The cache trades insert-time cost (propagate upward) for query-time speed (single lookup).

Ranking by frequency: every search increments the leaf's frequency; the cache stores Suggestion(word, score) sorted by score descending. Weight aging: multiply all frequencies by 0.99 every hour so trending queries surface and stale ones fade. This is read-mostly, so a copy-on-write trie or ReadWriteLock keeps queries lock-free.

classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;

Trie autocomplete LLD is the workhorse of search suggestion: every typed character returns a fresh top-10 in under 10ms across millions of queries. This guide builds the data structure, the cached top-K, and the read-mostly concurrency story.

Problem statement (interviewer prompt)

Design the in-memory data structure that powers search autocomplete. Support insert(word, weight), suggest(prefix, k) returning the top-K words by score, and incrementFrequency(word) when a user clicks a suggestion. Discuss how to keep suggest O(prefix length), how to age weights, and how to handle concurrent reads with occasional writes.

Requirements

Functional

• insert(word, weight): add a word with an initial weight.
• suggest(prefix, k): return top-K words starting with prefix, sorted by score descending.
• incrementFrequency(word): bump score when user clicks.
• Optional delete(word).

Non-functional

• suggest O(prefix length) using cached top-K per node.
• Read-mostly: thousands of reads per write.
• Memory bounded: cache at most K per node.
• Periodic weight aging (anti-staleness).

Class design

classDiagram
  class Trie {
    -root : TrieNode
    -k : int
    -lock : ReadWriteLock
    +insert(word, weight)
    +suggest(prefix, k) List~Suggestion~
    +incrementFrequency(word, delta)
    +delete(word)
    +ageAll(factor)
  }
  class TrieNode {
    -children : Map~Character, TrieNode~
    -isEnd : bool
    -word : string
    -frequency : double
    -topK : ArrayList~Suggestion~
    +updateTopK(s, k)
  }
  class Suggestion {
    +word : string
    +score : double
    +compareTo(o) int
  }
  Trie --> TrieNode
  TrieNode --> Suggestion

topK is an ArrayList (small, cache-friendly) sorted by score descending. K is usually 10. Memory per node: ~10 references plus the children map.

Core flow

sequenceDiagram
  participant U as User
  participant A as Trie
  participant N as TrieNodes
  Note over A: insert("apple", 5)
  U->>A: suggest("ap", 5)
  A->>N: walk root.children['a']
  N-->>A: node_a
  A->>N: walk node_a.children['p']
  N-->>A: node_p
  A-->>U: node_p.topK (precomputed)
  Note over A: incrementFrequency("apple", 1)
  U->>A: click "apple"
  A->>N: walk to leaf "apple", freq += 1
  A->>N: propagate topK up to root

The hot path is the walk: 2 character lookups for "ap". The slow path is insert and increment, which propagate upward, costing O(word length * K).

Code

import threading
from typing import Optional

class Suggestion:
    __slots__ = ('word', 'score')
    def __init__(self, word: str, score: float):
        self.word = word
        self.score = score
    def __lt__(self, other): return self.score > other.score  # max-first

class TrieNode:
    __slots__ = ('children', 'is_end', 'word', 'frequency', 'top_k')
    def __init__(self):
        self.children: dict[str, 'TrieNode'] = {}
        self.is_end = False
        self.word: Optional[str] = None
        self.frequency = 0.0
        self.top_k: list[Suggestion] = []

    def update_top_k(self, s: Suggestion, k: int) -> bool:
        """Insert s into top_k sorted by score desc; return True if list changed."""
        for i, existing in enumerate(self.top_k):
            if existing.word == s.word:
                if existing.score == s.score: return False
                existing.score = s.score
                self.top_k.sort()
                return True
        if len(self.top_k) < k:
            self.top_k.append(s)
            self.top_k.sort()
            return True
        if s.score > self.top_k[-1].score:
            self.top_k[-1] = s
            self.top_k.sort()
            return True
        return False

class Trie:
    def __init__(self, k: int = 10):
        self.root = TrieNode()
        self.k = k
        self.lock = threading.RLock()  # writer lock; readers use COW snapshot

    def insert(self, word: str, weight: float = 1.0) -> None:
        with self.lock:
            node = self.root
            path = [node]
            for ch in word:
                node = node.children.setdefault(ch, TrieNode())
                path.append(node)
            node.is_end = True
            node.word = word
            node.frequency = max(node.frequency, weight)
            s = Suggestion(word, node.frequency)
            for n in path:
                n.update_top_k(s, self.k)

    def suggest(self, prefix: str, k: int) -> list[Suggestion]:
        # Lock-free read: the worst case is a slightly stale top_k.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None: return []
        return node.top_k[:k]

    def increment_frequency(self, word: str, delta: float = 1.0) -> None:
        with self.lock:
            node = self.root
            path = [node]
            for ch in word:
                node = node.children.get(ch)
                if node is None: return
                path.append(node)
            if not node.is_end: return
            node.frequency += delta
            s = Suggestion(word, node.frequency)
            for n in path:
                n.update_top_k(s, self.k)

    def age_all(self, factor: float = 0.99) -> None:
        with self.lock:
            self._age_recursive(self.root, factor)

    def _age_recursive(self, node: TrieNode, factor: float) -> None:
        node.frequency *= factor
        for s in node.top_k:
            s.score *= factor
        for child in node.children.values():
            self._age_recursive(child, factor)

The insert walks the path once, then walks it again to update each top_k. Total cost: O(L * K) where L is word length.

Ranking and aging

Score formula is more than raw frequency. A common production blend:

score = log(1 + frequency) * recency_decay + personalisation_boost

Aging: a scheduled task multiplies every frequency by 0.99 every hour. Words queried recently keep their lead; stale ones fade. Run during a low-traffic window. Note that aging is O(N) over the trie, expensive: alternative is to store last_updated_at per node and decay lazily on read.

Concurrency

This is a read-mostly workload, so the right primitive is read-write lock (writers exclude all reads) or copy-on-write (readers see an immutable snapshot; writers swap the root atomically).

Read-write lock is simpler. Java's ReentrantReadWriteLock, Python's threading.RLock with a sharded variant, or Go's sync.RWMutex. Cost: writers starve under read pressure if the lock is not fair.

Copy-on-write is what production systems (Lucene index segments, immutable B-trees) use. Writers build a new tree off the path being modified, then CAS the root pointer. Readers see either the old or new tree, never a half-update. Cost: extra allocation per write; usually amortised over many updates batched together.

The pragmatic shortcut: serialise writes via a single writer goroutine/thread, leave reads lock-free with volatile / atomic-pointer on top_k arrays. Readers may see a slightly stale top_k, which is fine for autocomplete.

Edge cases interviewers probe

• Unicode: replace Map<Character, TrieNode> with Map<Integer, TrieNode> for code points; consider Han-script compaction.
• Prefix not found: return empty list, not error.
• K larger than top_k size: return what we have.
• Tie-breaking by score: secondary sort by lexicographic order, otherwise UI flickers.
• Memory: a million 20-char words is ~20M nodes. Compress with radix tree (collapse single-child chains).
• Deletion: rare, expensive (must recompute every top_k on the path); often just mark is_end = false.

Extensions

Radix tree (Patricia trie) collapses single-child chains. "system" and "systematic" share prefix "system" then branch. Cuts node count by ~5x for English.

Fuzzy autocomplete uses BK-tree or trie + Levenshtein automaton to handle typos.

Personalised suggestions maintain a per-user trie overlay; merge with the global top_k at query time.

Multi-region: shard the trie by first character or hash; aggregate top_k across shards via a fan-out + merge.

flowchart LR
  TA((Trie<br/>autocomplete))
  SA[Search autocomplete<br/>HLD framing]
  DSC[Data structures<br/>complexity]
  CP[Concurrency primitives<br/>RW-lock, COW]
  SA -. concretizes .-> TA
  DSC -. underpins .- TA
  CP -. read-mostly .- TA

    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    class TA service;
    class SA,DSC,CP datastore;

Quick reference

Key classes

• Trie: orchestrator, holds root + K
• TrieNode: children: Map<char,TrieNode>, isEnd, word, frequency, topK
• Suggestion: (word, score), comparable by score desc

Operations

Op	Time	Notes
insert(word, w)	O(L * K)	walk + update topK on path
suggest(prefix, k)	O(prefix)	read cached topK, copy first K
incrementFrequency(word)	O(L * K)	same as insert
delete(word)	O(L * descendants)	expensive, often soft-delete
ageAll(factor)	O(N nodes)	scheduled, low-traffic window

L = word length, K = cache size, N = trie size.

Top-K cache invariant

• Every node n.topK lists the K best words in subtree(n)
• Sorted by score descending; tie-break lexicographic
• On insert/increment, walk the path and call updateTopK(s, K) at each node
• Skip nodes whose topK already contains the word with same score (early-exit)

Ranking

• Raw frequency: simplest, prone to runaway leaders
• log(1 + freq) * decay + personal_boost: production blend
• Add recency: decay by 0.99 ** hours_since_last_use

Aging

• Multiply all frequencies by factor (e.g. 0.99) every hour
• Lazy alternative: store lastUpdatedAt; decay on read
• Without aging, "yesterday's news" never gets dethroned

Concurrency (read-mostly)

Strategy	Read cost	Write cost	When
Big mutex	high contention	low	tiny / prototype
RW-lock	shared (fast)	exclusive	default
Copy-on-write	lock-free	extra alloc	search engines, hot reads
Single-writer + atomic refs	lock-free	serialised writes	pragmatic, what we'd ship

Edge cases

• Unicode: use Map<Integer, TrieNode> for code points
• Tie-break by lex order, else UI flickers
• Soft delete via isEnd = false, defer hard delete
• Radix tree compaction cuts node count ~5x

Interview questions to expect

• Why cache topK per node? otherwise suggest is O(descendants) per query
• Why aging? prevents stuck-leader; trending queries surface
• Memory cost of topK? K * sizeof(Suggestion) per node; tune K vs RAM
• Fuzzy match? BK-tree or trie + Levenshtein automaton
• Sharding? shard by first char or hash, fan-out + K-way merge

Pitfalls

• Forgetting tie-break (UI looks broken)
• Aging in-place during reads (snapshot first)
• Returning topK by reference (caller mutates internal state)
• Per-node mutex (memory bloat); use one big RW-lock or COW

Refs

• LeetCode 642 - Design Search Autocomplete System
• Lucene FST (finite-state transducer) for term dictionary
• Sajari blog - production autocomplete tuning
• Patricia trie / radix tree compaction

FAQ

How does a trie make autocomplete fast?

Walking N characters of the prefix takes O(N) regardless of dataset size. Caching the top-K suggestions at each node makes suggest(prefix) effectively O(prefix length).

How are suggestions ranked?

Each terminal node stores a frequency or weight. The trie keeps a sorted top-K cache per node so the highest-ranked completions are read in O(K) without scanning subtrees.

How are inserts and updates handled?

Insert walks character by character creating nodes as needed; incrementFrequency walks the path and updates the per-node top-K cache if the new weight enters the top K.

How do you keep popular queries fresh?

Apply exponential decay to weights periodically so an old viral term cannot dominate forever. Weight aging gives recent traffic more influence on rankings.

When is a trie better than Elasticsearch for autocomplete?

For pure prefix matching at very low latency on a fixed vocabulary the trie wins. Elasticsearch is better when you need fuzzy matching, multi-field scoring, or larger-than-RAM data.

Related Topics

• Search Autocomplete: the HLD framing with distributed shards
• Data Structures Complexity: tries in the broader DS taxonomy
• Concurrency Primitives: RW-locks and copy-on-write