TOUGH TONGUE AI
  • Home
    LogoTOUGH TONGUE AI

    RESOURCES

    Loading...

    HomeLibrarySD Mock · Design Typeahead Suggestion

    SD Mock · Design Typeahead Suggestion

    Overview

    Design a search typeahead like Google or Facebook on a live architecture board — drag components, wire them up, and defend your design to an expert interviewer who watches every move.

    Your Instructions

    Design typeahead suggestion

    A 20-minute mock system design interview. You drive the pace. Jump to the board when you are ready; skip capacity math if you want. The interviewer grades your thinking, not a template match.

    This is the rare question where a data structure — the trie — is the centerpiece. Prefix match is the easy part. The interview is making the trie O(1), updating it without stopping the world, and sharding a tree.

    Two shared surfaces (only one is on screen at a time; use the panel arrow to switch):

    • Notepad. Shared notes. Requirements, capacity math, schema, and end-of-session feedback live here. You can type in it too.
    • Architecture board. Your design canvas. Drag typed components, wire them, label edges, mark scaled tiers as distributed. If it is not on the board, it is not in your design.

    Build incrementally while you talk. Trace one keystroke — the "n" after "di" — end to end through your diagram to a ranked top-5 list. Argue the tradeoff, not "industry standard."

    Design choices interviewers probe

    Read this before you go in. These are the decisions, and why they matter.

    Every keystroke is a request

    Typing "dinner" sends six requests (q=d, q=di, … q=dinner) — about 20 per completed query. That ×20 multiplier is the single best estimation signal in this question. It drives the QPS that kills a database round-trip, and the client etiquette that cuts load: debounce ~50 ms, cancel in-flight requests, do not fire until 2–3 characters, browser-cache responses (Cache-Control: private, max-age=3600 — Google caches autocomplete for an hour).

    The strawman: SQL LIKE

    SELECT query FROM freq_table WHERE query LIKE 'din%' ORDER BY frequency DESC LIMIT 5 is a fine warm-up and works small. At ~24K QPS with a ~100 ms budget, the round-trip plus prefix scan breaks. State it, then volunteer the transition: the aggregated index is small (~3 GB of unique terms, ~25 GB with a year's growth), so the whole thing lives in memory as a trie. Elasticsearch's completion suggester is equally defensible if you can name its operational cost against a purpose-built trie.

    Making the trie O(1)

    The naive algorithm is three steps: find the prefix node — O(p); walk the subtree for completions — O(c); sort by frequency and take five — O(c log c). A popular short prefix has a huge subtree, and that blows 100 ms.

    Two fixes. Cap prefix length (~50 chars) so the walk is constant. Cache the top five at every node — node "din" already holds its list. Query becomes find node + read list = O(1). Name the trade: space for time.

    Know the cost. Bumping one query's frequency means updating the cached list in every ancestor up to the root. That is why nobody updates the serving trie in place. A space refinement: store references to terminal nodes plus frequencies, and reconstruct the phrase by walking parents — do not duplicate full strings on every node. Single-child chains can collapse into a radix / compressed trie.

    Updating without stopping the world

    Do not update per search. Tens of thousands of writes would contend with 100 ms reads, and the top suggestions barely move. Instead: log completed searches (sampled 1-in-N — if a term under 1,000 searches never surfaces, 1-in-1,000 is safe) → aggregate periodically with MapReduce → workers rebuild the trie offline → atomic swap, or update a secondary while the primary serves and promote it.

    Ask how fresh suggestions must be before you pick the interval. Weekly is fine for Google keywords; breaking-news products need short intervals. A sliding window or exponential moving average weights recent data so old queries do not sit at the top forever. In-place update is only viable for a small trie.

    The typeahead API is read-only. There is no "record a search" endpoint on this service. The search system writes completed queries to the log; this service consumes the next rebuild.

    Sharding a tree

    Partitioning a tree is harder than partitioning a table: a prefix query must land on the shard that holds its subtree.

    • Alphabet ranges ('a' server, 'b' server): trivial routing, statically unbalanced — far more queries start with 'c' than 'x'.
    • Capacity-based ranges: fill a server, break the range there. Memory balances, but prefix "a" can span two servers, so you need an aggregator tier to merge results — and hotspots remain.
    • Hash of the term: even memory and load, but every query fans out to every shard. Latency is the slowest one.
    • Production default: a shard map built from historical query distribution — one shard for 's' alone, one for 'u'–'z' combined. Single-shard routing for most prefixes, load balanced on real traffic. The load balancer carries the map.

    Removing a suggestion today

    Legal or safety orders a suggestion gone now; your rebuild is weekly. Two-stage answer: a filter layer in front of the trie cache for immediate effect, plus asynchronous physical deletion from the Trie DB and aggregated data so the next rebuild is clean and the blocklist does not grow forever.

    Persistence and restart

    If a trie server dies, replaying raw logs takes hours. Snapshot the trie periodically. Grokking's encoding is level-order: each node's character plus child count, children immediately after (C2,A2,R1,T,P,O1,D). Do not serialize the top-k lists — children do not exist yet when a node is read — recompute them bottom-up on load. Trie DB options: a document store of weekly snapshots (MongoDB), or a key-value store where every prefix is a key and the node's top-k is the value. The KV shape is easy to shard and easy to cache.

    Reference solution

    One complete design you can study, then rebuild in your own words. Do not recite it. In the interview, draw your graph and defend the choices.

    Requirements (lock these or take the defaults)

    • Prefix match only (beginning of query); return top 5 complete queries
    • Ranked by popularity — historical query frequency
    • Fast: ~100 ms end to end (Facebook's published bar) or the UI stutters
    • English, lowercase alphabetic; no spell check or autocorrect
    • Scale: 10M DAU; highly available — degrade gracefully, stay up through partial failures
    • Out of scope unless wrap-up: multi-language, personalization, trending / real-time queries

    Capacity

    • 10M DAU × 10 searches/day = 100M completed queries/day
    • ×~20 requests per query (one per keystroke, ~20 chars) → 2B requests/day ÷ 86,400 ≈ 24K QPS average, ~48K peak
    • New data: 100M queries × 20 bytes × 20% new ≈ 0.4 GB/day
    • Aggregated index: ~100M unique terms × 30 B ≈ 3 GB (~25 GB with a year's growth) — that number is your license to keep the whole trie in memory

    Rough numbers are fine; the keystroke multiplier is what gets graded.

    Components to put on the board

    Two subsystems. The query path never leaves memory: a keystroke hits the API, the in-memory trie shard, and a filter — nothing else. The data-gathering pipeline rebuilds the trie offline from sampled search logs. Those logs do not come from the suggest API; they come from completed searches.

    Web Client / Mobile Client   (debounce ~50 ms, min 2–3 chars, browser cache 1 h)
        → Load Balancer          (carries the prefix → shard map)
        → Service "Query API"    (mark distributed)
        → Cache "Trie Cache"     (in-memory trie shards; mark distributed)
            -- miss --> MongoDB "Trie DB"  (serialized snapshots)
        → Service "Filter"       (blocklist; then respond)
    
    [offline — not on the suggest path]
    Web Client --completed search--> Blob Store "Analytics Logs"  (sampled 1-in-N)
        → Worker "Aggregator"    (weekly MapReduce → query, week, frequency)
        → Cron → Worker "Trie Builder"  (rebuild bottom-up, atomic swap)
        → MongoDB "Trie DB"  and  Cache "Trie Cache"
    
    • Web / Mobile Client. One request per keystroke past the minimum prefix: GET /v1/suggest?q=<prefix>&limit=5. Debounces ~50 ms, cancels in-flight requests, caches responses for an hour. The cheapest capacity you will ever buy.
    • Load Balancer. Routes by prefix using the shard map. Without it a hot first letter melts one box while others idle.
    • Query API (Service). Stateless. Validates and lowercases the prefix, consults the shard map, reads the trie shard, returns five strings. Mark distributed. Read-only — it does not log searches.
    • Trie Cache (Cache). The serving trie, in memory, sharded by prefix. Every node stores children plus its own precomputed top-5 with frequencies. Without node-level top-k this whole design misses the latency budget.
    • Filter (Service). Screens the five candidates against a blocklist before they leave. This is how a takedown lands today instead of at the next weekly rebuild.
    • Trie DB (MongoDB). Durable home of the weekly serialized snapshots; replenishes a shard on cache miss or restart. A key-value store (prefix → node data) is an equally good shape.
    • Analytics Logs (Blob Store). Raw, append-only, sampled. Written by the search system on a completed query. Never read on the live suggest path.
    • Aggregator (Worker). Weekly MapReduce turning sampled logs into (query, week, frequency). Interval is a freshness decision, not a default.
    • Cron + Trie Builder (Worker). Rebuilds the trie bottom-up — each node merges its children's top-5 lists — then swaps atomically or promotes a secondary. Serving never pauses.

    Walk one keystroke: user has typed "di", now types "n"

    1. The client's ~50 ms debounce fires. It cancels any in-flight request for di and issues GET /v1/suggest?q=din&limit=5. A fresh browser-cache hit would return here with no network call.
    2. Load Balancer looks up din in the shard map and routes to the shard that owns the d… range.
    3. Query API normalizes the prefix and walks three levels (d → di → din). Node "din" already holds its top five — dinner ideas 4200, dinosaur 3100, dining table 2750, dinner recipes 2600, dino game 1900. No subtree scan, no sort.
    4. Filter drops any block-listed entries. Query API returns the list with Cache-Control: private, max-age=3600.
    5. Total server-side work is a handful of pointer dereferences — well inside 100 ms.
    6. Separately, when the user later presses Enter, the completed search is written to Analytics Logs, sampled, and folded into next week's rebuild. That write is not on this path.

    Cache miss / server restart: replenish from the Trie DB snapshot. Serialization is level-order — character plus child count, children immediately after (C2,A2,R1,T,P,O1,D). Top-5 lists are not serialized; recompute them bottom-up on load. A secondary replica serves during recovery.

    Takedown today, rebuild weekly: add to the filter's blocklist for immediate effect; delete from the Trie DB and aggregated data asynchronously so the next rebuild is clean.

    Breaking news: a brand-new top query shows nothing until the next rebuild. Name the lag; sketch the extension — streaming aggregation (Kafka + a stream processor) and recency-weighted ranking — and acknowledge real-time top-k is a materially harder problem.

    Prefix spans two shards (capacity-range sharding): an aggregator tier between the load balancer and trie servers merges the partial top-5 lists.

    Schema

    QueryLog(query, timestamp)                     — raw, append-only, sampled
    AggregatedData(query, week, frequency)         — MapReduce output, trie weights
    TrieNode(prefix → {children, top5: [(query, freq)]})   — KV form: prefix is the key
    BlockList(query, reason)                       — filter layer + async delete queue
    
    • Shard the trie by prefix range from the shard map; replicate each shard (primary/secondary)
    • Frequency maintenance: sliding window (subtract the expired week, add the new) or EMA for recency
    • Nothing on the live suggest path reads QueryLog or AggregatedData

    Scaling and wrap-up

    • Trie shards + replicas scale reads; rebalance the shard map from historical distribution; give the head prefixes a dedicated hot cache
    • First metrics: p99 suggest latency, trie-cache hit rate, staleness (age of the serving trie)
    • If time: multi-language (Unicode explodes node fan-out), per-country tries served from a CDN, trending queries via stream processing

    Equally defensible variants

    A key-value trie (prefix → top-5 in DynamoDB or Redis) instead of document snapshots. Redis sorted sets per prefix instead of an explicit trie. Hourly aggregation instead of weekly, if you argue freshness. Elasticsearch's completion suggester, if you can defend its operational cost against a purpose-built trie. What matters is that you can argue the tradeoff.

    More in System Design Interview Prep: AI Coach Edition

    • SD Coach · The Data Layer
    • SD Coach · Unique IDs and the URL Shortener
    • SD Mock · Design Pastebin
    • SD Coach · News Feeds and Typeahead
    • SD Mock · Design Facebook News Feed
    • SD Mock · Design Twitter
    • SD Mock · Design Twitter Search
    • SD Coach · Rate Limiting
    • SD Mock · Design an API Rate Limiter
    • SD Coach · Event-Driven Systems and Notifications
    • SD Mock · Design a Notification System
    • SD Coach · Async Jobs, Schedulers and Crawlers
    View the full course (43 sessions) →