Engineering Atlas › Low-Level Design

Code a prefix-based suggestion engine

15 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Requirements

Functional:

Non-functional:

Out of scope: spelling correction, multi-language tokenisation, sharding, and time-decayed popularity. Name them and place them in Extensibility.

Entities and relationships

Start from the nouns in the requirements and keep only those that hold state or vary.

Relationships: the service is composed of the trie and the stats (they do not exist without it). Sessions reference the service but do not own it, and many sessions share one service. Policies are injected, so the service depends on their interfaces, not on concrete classes.

Class diagram

classDiagram
    class AutocompleteService {
      -root: TrieNode
      -counts: Map~string, int~
      -history: Map~UserId, Map~string, int~~
      -k: int
      +add(term, count) string
      +select(user, term)
      +suggest(prefix, user) string[]
      +session(user) TypingSession
    }
    class TrieNode {
      -children: Map~char, TrieNode~
      -term: string
    }
    class TypingSession {
      -user: UserId
      -prefix: string
      -path: TrieNode[]
      +type(ch) string[]
      +backspace() string[]
      +accept(term)
    }
    class Normalizer {
      <<interface>>
      +normalize(text) string
    }
    class Ranker {
      <<interface>>
      +rank(candidates, history) string[]
    }
    class SuggestionFilter {
      <<interface>>
      +allows(term) bool
    }
    AutocompleteService "1" *-- "1" TrieNode
    TrieNode "1" *-- "many" TrieNode
    TypingSession --> AutocompleteService
    TypingSession --> TrieNode
    AutocompleteService --> Normalizer
    AutocompleteService --> Ranker
    AutocompleteService --> SuggestionFilter
    PersonalThenPopular ..|> Ranker
    WordBlocklist ..|> SuggestionFilter

Key flows

The two flows that matter are a keystroke inside a session and accepting a suggestion. Note that the keystroke never re-walks the prefix from the root.

sequenceDiagram
    participant U as User
    participant S as TypingSession
    participant A as AutocompleteService
    participant F as SuggestionFilter
    participant R as Ranker
    U->>S: type("y")
    S->>S: child of top node, push it
    S->>A: collect(node, user)
    A->>A: walk subtree, gather terms
    A->>F: allows(term) for each
    F-->>A: kept terms
    A->>R: rank(kept, history[user])
    R-->>A: ordered list
    A-->>S: first k terms
    S-->>U: ["new york", "new york times"]
    U->>S: accept("new york times")
    S->>A: select(user, term)
    A->>A: counts +1, history[user] +1
    S->>S: reset prefix and path

Design patterns used and why

Concurrency and edge cases

In the wild

Down the stack

Layer 1The contract

suggest(p, u) returns at most k distinct terms, each of which equals normalize(t) for some added term t, starts with normalize_prefix(p), and passes every filter. The list is sorted by (-history[u][t], -count[t], t). A session's type and backspace return exactly what suggest(session.prefix, user) would return at that moment, so the session is an optimisation, never a different answer. select(u, t) increases count[t] and history[u][t] by one and adds t if it is new.

Layer 2The mechanism

The trie maps each character to a child node; a node with a non-null term marks the end of a term. Finding the prefix node costs O(length of prefix). Collecting candidates walks the whole subtree below it, which for a one-letter prefix can be a large fraction of the index, so production systems precompute the top k at every node (the approach in the sdi lesson) or store the maximum score in each subtree and run a best-first search with a heap that stops after k results. A radix (compressed) trie merges chains of single-child nodes into one edge labelled with a string, cutting node count by 3 to 10 times for natural-language queries. Lucene's suggesters compile the terms into a finite-state transducer, which shares suffixes too.

Layer 3The machine

A trie is a pointer-chasing structure. Each step from parent to child is a dependent load; if the child is not in cache, that is a main-memory access of roughly 80 to 100 ns. A 10-character prefix in a cold trie can therefore cost around a microsecond before any ranking happens. Per-node memory matters too: a Python dict starts at about 64 bytes empty and over 200 bytes once it holds a few keys, plus about 56 bytes for the node object itself with __slots__. A Go map[rune]*node has a header of about 48 bytes plus buckets of 8 entries. An array of 26 child pointers is 208 bytes on a 64-bit machine, mostly empty below the first few levels. Ten million terms with an average of 12 characters can produce tens of millions of nodes, which is several gigabytes in Python and is why serving systems use compact arrays, radix tries or FSTs. A pointer-heavy Go heap also lengthens garbage collector marking.

Why it's built this way

  1. Users type faster than a server round trip, so the per-keystroke work must be tiny, which means navigation by prefix rather than scanning.
  2. Prefix navigation is exactly what a trie gives, and a session cursor removes even the repeated walk from the root.
  3. Walking subtrees is the expensive part, so ranking data is pushed up the tree (top k per node or subtree maximum) once the index grows.
  4. Pointer-heavy tries waste memory and cache, so production indexes are compressed into radix tries or FSTs that are built offline and swapped atomically.
  5. Business rules change weekly while the index structure changes rarely, so normalisation, ranking and filtering live outside the trie as injected policies.

Extensibility

Variant: full-text search engine

Autocomplete answers "which stored strings start with this prefix?" A small text search engine answers "which documents contain these words?", and that changes the data model more than the algorithm. The unit stored is no longer a term with a count but a document, and the trie gives way to an inverted index: a map from each token to its postings, the list of documents containing it.

Concurrency matches the trie: readers during a write need a lock or an immutable snapshot swap. Memory differs, since postings with positions can rival the raw text, which is why production engines compress and segment them. Stemming and synonyms are extra analyzer stages, not index changes.

Leadership lens

Check yourself

  1. Why must the filter run before the list is cut to k, not after?

    Show answer

    If you truncate first and then filter, every blocked term removes a slot and the user sees fewer than k suggestions even though valid ones exist. Filtering first keeps the list full.

  2. A session typed qz and has an empty cursor. Then qzx is added. What should the next keystroke x return, and why?

    Show answer

    It should return qzx, because the session promises the same answer as a fresh suggest. The session must re-resolve its cursor from the root when it holds an empty cursor, or the cache becomes a correctness bug.

  3. Why is alphabetical order part of the ranking key?

    Show answer

    Without a final tie-breaker, equal-scored terms come back in hash-map or traversal order, which can change between runs and languages. A total order makes results testable and cacheable.

  4. When would you prefer a copy-on-write snapshot over a reader-writer lock?

    Show answer

    When writes come in batches (an hourly rebuild) and reads are extremely frequent. Readers then never block and never see a partial insert; the cost is memory for two copies during the swap.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →