Design Search Autocomplete

Problem introduction

Autocomplete looks like a small feature: a dropdown under a search box. It's a great HLD problem because the numbers force a design that's very different from "query the database": every keystroke is a request, the answer must arrive before the user types the next letter, and the data (what people search for) changes all day. The core lesson is one you'll reuse everywhere: split the system into a slow offline path that prepares answers and a fast online path that only reads them.

Problem statement

Someone in Mirpur opens a big shopping site and starts typing "dha". Before they finish the word, a dropdown already shows "dhaka weather", "dhakaiya biryani", "dhaka traffic". They tap one and skip typing the rest. On a slow phone keyboard, that saves real effort, and it steers people to queries that actually have results.

What we are building: a service that, given what a user has typed so far (a prefix), returns the 10 most popular complete queries that start with it, fast enough to feel instant.

Who uses it: everyone who types in the search box, on every keystroke. Indirectly, the search team, who need the suggestions to be fresh (a new metro line, an Eid sale, breaking news) and clean (no offensive or personal suggestions).

What it solves: less typing, fewer spelling mistakes, and searches that land on things that exist.

What makes it technically interesting:

• Latency: the answer must come back in well under 100 ms end to end, including a mobile network, or the dropdown lags behind the typing and is useless.
• Volume: one search becomes several requests (one per pause in typing), so suggestion traffic is many times search traffic.
• Short prefixes are huge: "d" matches millions of queries. Sorting them on every keystroke is impossible.
• Freshness vs speed: popularity changes during the day, but rebuilding answers on the request path would kill latency.
• Content safety: whatever people type can become a suggestion shown to millions, including slurs, rumours and phone numbers.

Requirements

Functional requirements

1. Suggest: for a prefix, return up to 10 complete queries that start with it, most popular first.
2. Only real searches: suggestions come from queries people actually submitted (pressed Enter), not from every keystroke.
3. Freshness: a query that becomes popular shows up within about an hour; fast-breaking trends within about 15 minutes (stretch goal).
4. Filtering: blocked words, offensive content and anything that looks like personal data are never suggested; a suggestion can be removed within minutes after a complaint.
5. Out of scope: spelling correction ("dhkaa"), personalised suggestions, and the search results page itself. We discuss the first two in the interview section.

Non-functional requirements

Latency and throughput drive the design. Note what's not strict: freshness is measured in minutes, durability is relaxed, and availability can be 99.9% because the feature degrades gracefully. That freedom is what lets us precompute everything.

Capacity estimation

Assumptions (said out loud, round numbers):

• 50 million daily active users, each submitting 6 searches a day.
• A typed query is about 18 characters, but with a short debounce the browser sends about 6 suggestion requests per search.
• The busiest hour is about 3× the average.
• Only queries searched by at least 20 different people in 30 days can become suggestions (this is also a privacy rule, see Security). That leaves about 10 million suggestible queries, 20 bytes long on average.
• We store the top 10 per prefix.

Traffic

Storage

Servers: a trie lookup in memory takes microseconds; the HTTP work around it dominates. Assuming a conservative 10,000 requests/s per server, peak needs about 7 servers. Run 10 across two zones so we can lose a zone and still be fine. Each server holds the whole 5 GB trie, so any server can answer any prefix.

Bandwidth: a response with 10 suggestions is about 400 bytes of JSON plus ~300 bytes of headers. 63,000 × 700 B ≈ 44 MB/s (~350 Mbit/s) at peak. Noticeable but fine, and gzip and the CDN cut it further.

Cache size: prefixes of 1 to 3 characters number about 37 + 37² + 37³ ≈ 52,000 (letters, digits, space). At 700 B each that's 36 MB, and these short prefixes are by far the most repeated, so they're perfect for a CDN edge cache.

What the numbers say: the serving data (5 GB) fits in one machine's memory, so a lookup can be a pointer walk with no database at all. The expensive part (counting 300 million searches and ranking every prefix) can happen offline, in batches, because freshness is measured in minutes. That's the whole design in two sentences.

API design

• Why GET with the prefix in the URL: it makes the response cacheable by the browser and the CDN, keyed by the URL. That's the most important property of this API.
• No counts in the response: popularity numbers are internal; exposing them invites manipulation.
• Authentication: suggestions are anonymous. That's deliberate: a cookie or user ID in the request would make the response personal and uncacheable. Rate limiting is per IP and per client app.
• Idempotency: GET is naturally idempotent. Search events carry an event_id so the counting pipeline can drop duplicates when the log delivers an event twice.
• version tells the client which trie answered; useful for debugging "why did I see this suggestion", and it lets the client ignore a response from an older version that arrives late.
• Client contract: the browser waits a short pause (about 50–100 ms) before sending, cancels the previous request when a new key is pressed, and caches answers for the session. These three rules cut server traffic a lot.

Database design

Access pattern: the online path reads "top 10 for this exact prefix", tens of thousands of times a second, and never writes. The offline path appends search events all day and, once an hour, rewrites all the counts.

Why not just query a database? SELECT query FROM queries WHERE query LIKE 'd%' ORDER BY count DESC LIMIT 10 can use a B-tree index for the prefix, but for "d" it still has to read millions of matching rows to sort them by count. That's fine for a site with 1,000 queries and hopeless at our scale. The fix is to precompute the answer for every prefix, and a trie is a compact way to store those answers.

So the "database" for serving is the trie itself, in memory, loaded from a file. The other stores are ordinary:

-- Raw search events: an append-only log (Kafka topic), then hourly files in object storage
-- (Parquet, partitioned by hour). Not a SQL table; shown as columns for clarity.
--   event_id, query, lang, region, user_hash, ts

-- Aggregated counts, rewritten by every batch (warehouse table or Parquet files).
CREATE TABLE query_counts (
  query        TEXT    NOT NULL,
  lang         TEXT    NOT NULL,
  score        BIGINT  NOT NULL,          -- decayed count: old score / 2 + new searches
  users_30d    INT     NOT NULL,          -- distinct users, for the privacy threshold
  PRIMARY KEY (lang, query)
);

-- Which trie version each shard should serve (small, PostgreSQL).
CREATE TABLE trie_versions (
  version     BIGINT PRIMARY KEY,
  shard       TEXT   NOT NULL,            -- e.g. 'a-c', 'd-k', 'l-z'
  path        TEXT   NOT NULL,            -- object storage key of the snapshot file
  checksum    TEXT   NOT NULL,
  queries     INT    NOT NULL,
  status      TEXT   NOT NULL,            -- building, validated, live, rolled_back
  built_at    TIMESTAMPTZ NOT NULL
);

-- Blocked words and removed suggestions (small, PostgreSQL, edited by staff).
CREATE TABLE blocked_terms (
  term        TEXT PRIMARY KEY,
  reason      TEXT NOT NULL,
  added_by    BIGINT NOT NULL,
  added_at    TIMESTAMPTZ NOT NULL DEFAULT now()
);

• The log is append-only and partitioned by time, so writing 10,000 events a second is cheap and an hour's data is one directory to read.
• Counts are recomputed, not updated in place: a batch reads the previous counts plus the new hour and writes a fresh set. No row is ever contended.
• trie_versions is the control plane: servers poll it (or get notified), download the file for their shard, verify the checksum and swap. Rolling back is setting an older row back to live.
• Replication and partitioning: the log is replicated by Kafka and object storage; the trie is "replicated" by loading the same file on every server; shards are prefix ranges (see Scaling). The small PostgreSQL tables need only a standby.

Visual architecture

On the prefix cache: a trie walk in RAM is already microseconds, so a shared Redis in front of it would add a network hop. Our cache here is an in-process LRU that saves the walk and the JSON encoding for hot prefixes. A shared Redis becomes worth it later, when an answer has to be merged from several shards or mixed with personal history. That's the caching strategy: browser first, CDN second, in-process third, Redis only for expensive merged answers.

We deliberately don't have: a database on the read path, any write on the read path, or a stream processor on day one (hourly batches meet the freshness requirement).

Request lifecycle

Typing a prefix (cache miss)

1. User types d, h, a. The browser waits ~100 ms after the last key, so it sends only one request: GET /v1/suggest?q=dha. If a request for dh is still in flight, it's cancelled.
2. Browser cache, then CDN: if anyone nearby asked for dha in the last 60 seconds, the edge answers and our servers never see it.
3. LB → any suggest server. The server normalises the prefix (lowercase, single spaces, max 50 characters; a trailing space is kept because dhaka and dhaka are different prefixes).
4. It reads the current trie pointer once (version 1) and asks the cache for 1:dha. Miss.
5. It walks d → h → a in the trie: three steps. The top-10 list is already stored at that node, so there's nothing to search or sort.
6. It stores the list under 1:dha and returns 200 with Cache-Control: public, max-age=60. Total server time: well under a millisecond.

A search being counted (the offline path)

1. The user presses Enter on "dhaka metro rail". The search service logs {event_id, query, lang, user_hash, ts} to the query log. The search itself doesn't wait for this.
2. Every hour, the aggregator reads the last hour of events, drops duplicate event_ids, normalises queries and counts them.
3. It merges with the previous scores: score = old_score / 2 + new_count (exponential decay, so last week fades and a new trend can overtake it), removes blocked words and queries below the 20-distinct-users threshold.
4. The builder makes a new trie, computes every node's top 10 bottom-up, and runs validation (size within ±20% of the last build, a set of "golden" prefixes still return sane results, no blocked terms).
5. The snapshot file goes to object storage with a checksum; a trie_versions row marks it validated, then live.
6. Each suggest server downloads the file, loads it into memory next to the old trie, and swaps one pointer. Requests already running finish on the old trie; new ones use the new one. Old cache entries have the old version in their key, so they're never served again and simply age out.

Component deep dive

The trie with top-K at every node

A plain trie answers "which queries start with d?" by walking the whole subtree under d: millions of nodes. We don't do that at request time. Instead, while building offline, each node stores the best K queries in its subtree. They're computed bottom-up: a node's list is its own query (if one ends there) merged with its children's lists, sorted, cut to K. Children's lists are already the best of their subtrees, so the merge only looks at K × children items, not the whole subtree.

Memory tricks for production: store 4-byte query IDs instead of strings in the lists; compress chains of single-child nodes (a radix tree); only keep lists on nodes up to some depth and fall back to a small scan below it; or use a finite-state transducer (what Lucene's suggesters use), which shares suffixes as well as prefixes.

Immutable snapshots and the atomic swap

The trie is never edited in place. Each build produces a complete new trie; a server loads it alongside the current one and then swaps a single pointer. That gives us three things for free:

• No locks on the read path: readers never see a half-updated trie, because nobody updates it.
• Consistent answers: a request reads the pointer once at the start, so its whole answer comes from one version (the Go test TestReadersDuringSwaps checks exactly this under -race).
• Instant rollback: the previous file is still in object storage; swapping back is the same operation.

The cost is memory: during a swap a server briefly holds two tries (2 × 5 GB). Size servers for that, or load shards one at a time.

Versioned cache keys

If the cache key were just the prefix, then after a swap the cache would keep serving the old list until each entry expired. Purging every key across servers on each swap is slow and racy. Instead the key contains the trie version: 412:dha. After the swap to 413, every lookup uses 413:... keys, so old entries are simply never hit again and the LRU evicts them. The CDN can't use our version in its key (it caches by URL), so there we accept up to max-age (60 s) of staleness, which the freshness requirement allows.

Counting with decay, and trends

The batch computes score = old_score / 2 + this_hour (in production the halving is tuned, e.g. a half-life of a few days). Without decay, last year's "eid ul adha 2025" would beat this week's news forever. With it, a query that suddenly gets searched a lot overtakes old favourites within one or two builds. The demo shows exactly this: "dhaka metro rail" goes from 1 search to the top of d after one day of heavy searching.

For "breaking news in 15 minutes", hourly batches aren't enough. The final design adds a small stream job that keeps counts for the last 15 minutes, finds queries rising much faster than usual, and pushes a short "boost list" to the servers, which merge it into answers until the next batch absorbs it. It's a separate, simpler path so the main build stays boring and reliable.

The core, runnable

This program is the heart of the design, small enough to read in one sitting: normalisation, an aggregator that counts submitted searches, a merge with decay and a blocklist, a trie that precomputes the top K of every prefix, an LRU cache keyed by version:prefix, and a service that answers keystrokes and swaps in new tries atomically.

autocomplete/
├── go.mod
├── trie.go               Trie: Build (with top K per node), Top
├── aggregate.go          Normalize, Aggregator, Merge (decay + blocklist)
├── cache.go              LRU cache of version:prefix -> suggestions
├── service.go            Service: Suggest, Publish (atomic swap)
├── autocomplete_test.go  top K vs brute force, swaps under -race, versioned cache, merge
└── cmd/demo/main.go      two days of searches, one user typing, a rebuild and a swap

// trie.go
package autocomplete

import "sort"

// Suggestion is one query and how often people searched for it.
type Suggestion struct {
	Query string
	Count int
}

// better orders suggestions: more searches first, then alphabetically, so every build and
// every language gives the same list.
func better(a, b Suggestion) bool {
	if a.Count != b.Count {
		return a.Count > b.Count
	}
	return a.Query < b.Query
}

type node struct {
	kids  map[byte]*node
	count int          // > 0 when a whole query ends here
	top   []Suggestion // the best k queries that start with this prefix, precomputed
}

// Trie is a read-only snapshot built offline from search counts. Every node already knows
// its top k, so a lookup is just "walk the prefix, return the list": no searching at query time.
type Trie struct {
	root    *node
	k       int
	Version int
	Queries int
	Nodes   int
}

// Build makes a trie from query counts and fills in the top k of every prefix.
func Build(version int, counts map[string]int, k int) *Trie {
	t := &Trie{root: &node{kids: map[byte]*node{}}, k: k, Version: version, Nodes: 1}
	for q, c := range counts {
		if c <= 0 || q == "" {
			continue
		}
		n := t.root
		for i := 0; i < len(q); i++ {
			next, ok := n.kids[q[i]]
			if !ok {
				next = &node{kids: map[byte]*node{}}
				n.kids[q[i]] = next
				t.Nodes++
			}
			n = next
		}
		n.count = c
		t.Queries++
	}
	t.fill(t.root, nil)
	return t
}

// fill computes top k bottom-up: a node's list is its own query plus its children's lists.
func (t *Trie) fill(n *node, path []byte) {
	var all []Suggestion
	if n.count > 0 {
		all = append(all, Suggestion{string(path), n.count})
	}
	for c, kid := range n.kids {
		t.fill(kid, append(path, c))
		all = append(all, kid.top...)
	}
	sort.Slice(all, func(i, j int) bool { return better(all[i], all[j]) })
	if len(all) > t.k {
		all = all[:t.k]
	}
	n.top = all
}

// Top returns the precomputed best k for a prefix (nil if nobody searched it). The slice
// belongs to the snapshot: callers must not change it.
func (t *Trie) Top(prefix string) []Suggestion {
	n := t.root
	for i := 0; i < len(prefix); i++ {
		if n = n.kids[prefix[i]]; n == nil {
			return nil
		}
	}
	return n.top
}

// aggregate.go
package autocomplete

import (
	"strings"
	"sync"
)

// MaxLen is the longest query we store or look up, in bytes.
const MaxLen = 50

// Normalize makes "  Dhaka   WEATHER " and "dhaka weather" the same query: lowercase, single
// spaces, trimmed, at most MaxLen bytes. (This demo uses ASCII; production also normalises
// Unicode, and Bangla queries work the same way.)
func Normalize(s string) string {
	s = strings.Join(strings.Fields(strings.ToLower(s)), " ")
	if len(s) > MaxLen {
		s = strings.TrimRight(s[:MaxLen], " ")
	}
	return s
}

// Aggregator counts searches as they happen, like the log pipeline that feeds the builder.
type Aggregator struct {
	mu     sync.Mutex
	counts map[string]int
	Seen   int
}

func NewAggregator() *Aggregator { return &Aggregator{counts: map[string]int{}} }

// Add records one search that the user actually submitted.
func (a *Aggregator) Add(raw string) {
	q := Normalize(raw)
	if q == "" {
		return
	}
	a.mu.Lock()
	defer a.mu.Unlock()
	a.counts[q]++
	a.Seen++
}

// Drain hands over the counts collected so far and starts a new period.
func (a *Aggregator) Drain() map[string]int {
	a.mu.Lock()
	defer a.mu.Unlock()
	out := a.counts
	a.counts = map[string]int{}
	a.Seen = 0
	return out
}

// Merge prepares the next build: old counts are halved (so last week fades and new trends can
// win), this period's counts are added, and queries with a blocked word are removed.
func Merge(old, recent map[string]int, blocked map[string]bool) (counts map[string]int, removed int) {
	counts = map[string]int{}
	for q, c := range old {
		if c/2 > 0 {
			counts[q] = c / 2
		}
	}
	for q, c := range recent {
		counts[q] += c
	}
	for q := range counts {
		for _, w := range strings.Fields(q) {
			if blocked[w] {
				delete(counts, q)
				removed++
				break
			}
		}
	}
	return counts, removed
}

// cache.go
package autocomplete

import (
	"container/list"
	"sync"
)

// Cache is a small LRU cache of "version:prefix" -> suggestions, like Redis (or a CDN edge)
// in front of the trie servers.
type Cache struct {
	mu           sync.Mutex
	cap          int
	order        *list.List // front = most recently used
	items        map[string]*list.Element
	Hits, Misses int
}

type entry struct {
	key  string
	list []Suggestion
}

func NewCache(capacity int) *Cache {
	return &Cache{cap: capacity, order: list.New(), items: map[string]*list.Element{}}
}

func (c *Cache) Get(key string) ([]Suggestion, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()
	e, ok := c.items[key]
	if !ok {
		c.Misses++
		return nil, false
	}
	c.Hits++
	c.order.MoveToFront(e)
	return e.Value.(entry).list, true
}

func (c *Cache) Put(key string, list []Suggestion) {
	c.mu.Lock()
	defer c.mu.Unlock()
	if e, ok := c.items[key]; ok {
		c.order.MoveToFront(e)
		return
	}
	if c.order.Len() == c.cap {
		old := c.order.Back()
		c.order.Remove(old)
		delete(c.items, old.Value.(entry).key)
	}
	c.items[key] = c.order.PushFront(entry{key, list})
}

// service.go
// Package autocomplete is the core of a search autocomplete service: searches are counted,
// a trie with the top k per prefix is built offline, swapped in atomically, and served
// through a cache whose keys carry the trie's version.
package autocomplete

import (
	"strconv"
	"strings"
	"sync/atomic"
)

// Service is one suggestion server. Lookups never lock the trie: it is read-only, and a new
// build replaces it with one atomic pointer swap.
type Service struct {
	trie    atomic.Pointer[Trie]
	cache   *Cache
	lookups atomic.Int64 // requests that reached the trie (cache misses)
}

func NewService(t *Trie, cache *Cache) *Service {
	s := &Service{cache: cache}
	s.trie.Store(t)
	return s
}

// Publish swaps in a freshly built trie. Requests already running finish on the old one.
func (s *Service) Publish(t *Trie) { s.trie.Store(t) }

// Version is the version of the trie being served now.
func (s *Service) Version() int { return s.trie.Load().Version }

// Lookups is how many requests missed the cache and walked the trie.
func (s *Service) Lookups() int64 { return s.lookups.Load() }

// Suggest answers one keystroke. The prefix is normalised like stored queries, except that a
// trailing space is kept ("dhaka " should not suggest "dhakaiya"). The cache key includes the
// version, so after a swap old answers are never served; they simply age out of the LRU.
func (s *Service) Suggest(raw string) []Suggestion {
	p := Normalize(raw)
	if p == "" {
		return nil
	}
	if strings.HasSuffix(raw, " ") && len(p) < MaxLen {
		p += " "
	}
	t := s.trie.Load() // one snapshot for the whole request
	key := strconv.Itoa(t.Version) + ":" + p
	if list, ok := s.cache.Get(key); ok {
		return list
	}
	s.lookups.Add(1)
	list := t.Top(p)
	s.cache.Put(key, list)
	return list
}

// cmd/demo/main.go
// Command demo counts a day of searches, builds a trie, serves keystrokes through a cache,
// then counts a second day, rebuilds and swaps the new trie in.
package main

import (
	"fmt"
	"strings"

	"autocomplete"
)

func show(s *autocomplete.Service, typed string) {
	list := s.Suggest(typed)
	parts := []string{}
	for _, x := range list {
		parts = append(parts, fmt.Sprintf("%s %d", x.Query, x.Count))
	}
	if len(parts) == 0 {
		parts = append(parts, "(no suggestions)")
	}
	fmt.Printf("  %-12s -> %s\n", `"`+typed+`"`, strings.Join(parts, " | "))
}

func searches(a *autocomplete.Aggregator, q string, times int) {
	for i := 0; i < times; i++ {
		a.Add(q)
	}
}

func main() {
	blocked := map[string]bool{"fake": true}
	agg := autocomplete.NewAggregator()

	// Day 1: what people submitted, messy spelling and all.
	searches(agg, "dhaka weather", 3)
	searches(agg, "Dhaka Weather", 1)
	searches(agg, "  dhaka   weather ", 1)
	searches(agg, "dhakaiya biryani", 4)
	searches(agg, "dhaka fake certificate", 4)
	searches(agg, "dhaka traffic", 3)
	searches(agg, "dhaka to chittagong bus", 2)
	searches(agg, "dal recipe", 2)
	searches(agg, "dhaka metro rail", 1)
	searches(agg, "eid sale", 3)
	searches(agg, "egg price", 1)
	fmt.Printf("day 1: %d searches logged\n", agg.Seen)
	counts, removed := autocomplete.Merge(nil, agg.Drain(), blocked)
	t1 := autocomplete.Build(1, counts, 3)
	fmt.Printf("build v1: %d queries (%d blocked), %d trie nodes, top 3 kept per prefix\n", t1.Queries, removed, t1.Nodes)

	cache := autocomplete.NewCache(8)
	s := autocomplete.NewService(t1, cache)
	fmt.Println("user 1 types \"dhaka m\", one request per keystroke:")
	for _, p := range []string{"d", "dh", "dha", "dhak", "dhaka", "dhaka ", "dhaka m"} {
		show(s, p)
	}
	fmt.Println("user 2 and a few others:")
	for _, p := range []string{"d", "dh", "dha", "  DHAKA  ", "e", "xyz"} {
		show(s, p)
	}
	fmt.Printf("cache: %d hits, %d misses; trie lookups: %d\n", cache.Hits, cache.Misses, s.Lookups())

	// Day 2: a new metro line opens and everyone searches for it.
	searches(agg, "dhaka metro rail", 9)
	searches(agg, "dhaka weather", 1)
	searches(agg, "eid sale", 2)
	fmt.Printf("day 2: %d searches logged\n", agg.Seen)
	counts, _ = autocomplete.Merge(counts, agg.Drain(), blocked)
	t2 := autocomplete.Build(2, counts, 3)
	s.Publish(t2)
	fmt.Printf("build v2: old counts halved + day 2 added -> %d queries; now serving v%d\n", t2.Queries, s.Version())
	for _, p := range []string{"d", "dhaka ", "e"} {
		show(s, p)
	}
	fmt.Printf("cache: %d hits, %d misses; trie lookups: %d\n", cache.Hits, cache.Misses, s.Lookups())
}

Running the demo:

$ go run ./cmd/demo
day 1: 25 searches logged
build v1: 8 queries (1 blocked), 83 trie nodes, top 3 kept per prefix
user 1 types "dhaka m", one request per keystroke:
  "d"          -> dhaka weather 5 | dhakaiya biryani 4 | dhaka traffic 3
  "dh"         -> dhaka weather 5 | dhakaiya biryani 4 | dhaka traffic 3
  "dha"        -> dhaka weather 5 | dhakaiya biryani 4 | dhaka traffic 3
  "dhak"       -> dhaka weather 5 | dhakaiya biryani 4 | dhaka traffic 3
  "dhaka"      -> dhaka weather 5 | dhakaiya biryani 4 | dhaka traffic 3
  "dhaka "     -> dhaka weather 5 | dhaka traffic 3 | dhaka to chittagong bus 2
  "dhaka m"    -> dhaka metro rail 1
user 2 and a few others:
  "d"          -> dhaka weather 5 | dhakaiya biryani 4 | dhaka traffic 3
  "dh"         -> dhaka weather 5 | dhakaiya biryani 4 | dhaka traffic 3
  "dha"        -> dhaka weather 5 | dhakaiya biryani 4 | dhaka traffic 3
  "  DHAKA  "  -> dhaka weather 5 | dhaka traffic 3 | dhaka to chittagong bus 2
  "e"          -> eid sale 3 | egg price 1
  "xyz"        -> (no suggestions)
cache: 4 hits, 9 misses; trie lookups: 9
day 2: 12 searches logged
build v2: old counts halved + day 2 added -> 7 queries; now serving v2
  "d"          -> dhaka metro rail 9 | dhaka weather 3 | dhakaiya biryani 2
  "dhaka "     -> dhaka metro rail 9 | dhaka weather 3 | dhaka to chittagong bus 1
  "e"          -> eid sale 3
cache: 4 hits, 12 misses; trie lookups: 12

Reading the output:

• Day 1 and the build: 25 searches were logged, but "Dhaka Weather" and " dhaka weather " were normalised into "dhaka weather", so they count as one query with 5 searches. "dhaka fake certificate" was searched 4 times and would have been the second suggestion under dhaka ; the blocklist removed it before the build. 8 queries made a trie of 83 nodes.
• Typing "dhaka m": d to dhaka all show the same three suggestions: "dhaka weather" (5), "dhakaiya biryani" (4), "dhaka traffic" (3). That's right: those are the best queries under every one of those prefixes. The moment a space is typed, dhaka drops "dhakaiya biryani" (it doesn't start with "dhaka ") and "dhaka to chittagong bus" moves in. dhaka m leaves only "dhaka metro rail".
• User 2: d, dh, dha are cache hits: the first user already asked for them. DHAKA normalises to dhaka (the trailing space is kept) and is a hit too. xyz returns nothing, which is cached as well, so a bot can't hammer the trie with junk prefixes.
• Cache numbers: 4 hits and 9 misses so far; only the misses walked the trie.
• Day 2: a new metro line opens and "dhaka metro rail" is searched 9 times. The merge halves day 1 (weather 5 → 2, plus 1 new = 3) and adds day 2. "egg price" (1 → 0) disappears. In v2 "dhaka metro rail" (9) tops both d and dhaka .
• After the swap: d, dhaka and e are misses even though they were cached a minute ago, because the keys are now 2:d, not 1:d. Nobody sees a stale list, and nobody had to purge anything.

The tests check what matters most: the precomputed top K equals a brute-force answer for random data, normalisation and the trailing space, the merge's decay and blocklist, that a swap never serves an old cached list, that readers running during 49 swaps always get an answer from exactly one version (run with -race), and that concurrent counting doesn't lose searches. Replacing the atomic pointer with a plain one makes -race report a data race in the swap test, so the test really guards the swap.

$ go test -race -v ./...
=== RUN   TestTopKMatchesBruteForce
--- PASS: TestTopKMatchesBruteForce (0.00s)
=== RUN   TestNormalize
--- PASS: TestNormalize (0.00s)
=== RUN   TestMergeDecaysAndBlocks
--- PASS: TestMergeDecaysAndBlocks (0.00s)
=== RUN   TestSwapNeverServesOldCacheEntries
--- PASS: TestSwapNeverServesOldCacheEntries (0.00s)
=== RUN   TestTrailingSpaceMatters
--- PASS: TestTrailingSpaceMatters (0.00s)
=== RUN   TestReadersDuringSwaps
--- PASS: TestReadersDuringSwaps (0.00s)
=== RUN   TestAggregatorConcurrentAdds
--- PASS: TestAggregatorConcurrentAdds (0.01s)
PASS
ok  	autocomplete	1.022s
?   	autocomplete/cmd/demo	[no test files]

The same core in five more languages

Single-threaded versions with the same classes and the same output. The swap is still one assignment of a reference; what changes is how each language makes that safe when threads are involved:

• Python: assigning self.trie = new_trie is atomic under the GIL, and a request keeps its own reference t, so the old trie lives until that request finishes.
• TypeScript: Node runs requests on one event loop, so the swap can't interleave with a lookup. (The class is called SuggestCache because Cache is a browser global.)
• Rust: the service holds an Rc<Trie> and each request clones it. With threads you'd use Arc<Trie> behind an atomic swap (for example the arc-swap crate), and the compiler would refuse the non-thread-safe version.
• Java: AtomicReference<Trie> is the direct equivalent of Go's atomic.Pointer, and LinkedHashMap in access order is a ready-made LRU.
• C++: the service holds a std::shared_ptr<const Trie>; each request copies it, which keeps the old trie alive. With threads, use std::atomic<std::shared_ptr<const Trie>> (C++20) for the swap.

"""Search autocomplete's core: searches are counted, a trie with the top k per prefix is built
offline, swapped in as a whole, and served through a cache whose keys carry the trie's version."""
from collections import OrderedDict
from dataclasses import dataclass, field

MAX_LEN = 50


@dataclass(frozen=True)
class Suggestion:
    query: str
    count: int


def rank(s: Suggestion) -> tuple[int, str]:
    """More searches first, then alphabetical: the same order in every language."""
    return (-s.count, s.query)


@dataclass
class Node:
    kids: dict[str, "Node"] = field(default_factory=dict)
    count: int = 0  # > 0 when a whole query ends here
    top: list[Suggestion] = field(default_factory=list)  # best k with this prefix, precomputed


class Trie:
    """A read-only snapshot built offline. Every node already knows its top k."""

    def __init__(self, version: int, counts: dict[str, int], k: int):
        self.root, self.k, self.version = Node(), k, version
        self.queries, self.nodes = 0, 1
        for q, c in counts.items():
            if c <= 0 or not q:
                continue
            n = self.root
            for ch in q:
                if ch not in n.kids:
                    n.kids[ch] = Node()
                    self.nodes += 1
                n = n.kids[ch]
            n.count = c
            self.queries += 1
        self._fill(self.root, "")

    def _fill(self, n: Node, path: str) -> None:
        """Bottom-up: a node's list is its own query plus its children's lists."""
        everything = [Suggestion(path, n.count)] if n.count > 0 else []
        for ch, kid in n.kids.items():
            self._fill(kid, path + ch)
            everything += kid.top
        n.top = sorted(everything, key=rank)[: self.k]

    def top(self, prefix: str) -> list[Suggestion]:
        n = self.root
        for ch in prefix:
            n = n.kids.get(ch)
            if n is None:
                return []
        return n.top


def normalize(s: str) -> str:
    """Lowercase, single spaces, trimmed, at most MAX_LEN characters."""
    s = " ".join(s.lower().split())
    return s[:MAX_LEN].rstrip(" ")


class Aggregator:
    """Counts submitted searches, like the log pipeline that feeds the builder."""

    def __init__(self):
        self.counts: dict[str, int] = {}
        self.seen = 0

    def add(self, raw: str) -> None:
        q = normalize(raw)
        if q:
            self.counts[q] = self.counts.get(q, 0) + 1
            self.seen += 1

    def drain(self) -> dict[str, int]:
        out, self.counts, self.seen = self.counts, {}, 0
        return out


def merge(old: dict[str, int], recent: dict[str, int], blocked: set[str]) -> tuple[dict[str, int], int]:
    """Old counts halved, recent counts added, queries with a blocked word removed."""
    counts = {q: c // 2 for q, c in old.items() if c // 2 > 0}
    for q, c in recent.items():
        counts[q] = counts.get(q, 0) + c
    kept = {q: c for q, c in counts.items() if not any(w in blocked for w in q.split())}
    return kept, len(counts) - len(kept)


class Cache:
    """LRU cache of "version:prefix" -> suggestions, like Redis in front of the trie servers."""

    def __init__(self, capacity: int):
        self.cap, self.items = capacity, OrderedDict()
        self.hits = self.misses = 0

    def get(self, key: str) -> list[Suggestion] | None:
        if key not in self.items:
            self.misses += 1
            return None
        self.hits += 1
        self.items.move_to_end(key)
        return self.items[key]

    def put(self, key: str, value: list[Suggestion]) -> None:
        if key in self.items:
            self.items.move_to_end(key)
            return
        if len(self.items) == self.cap:
            self.items.popitem(last=False)
        self.items[key] = value


class Service:
    """One suggestion server. A new build replaces the trie in one assignment."""

    def __init__(self, trie: Trie, cache: Cache):
        self.trie, self.cache, self.lookups = trie, cache, 0

    def publish(self, trie: Trie) -> None:
        self.trie = trie

    def suggest(self, raw: str) -> list[Suggestion]:
        p = normalize(raw)
        if not p:
            return []
        if raw.endswith(" ") and len(p) < MAX_LEN:
            p += " "  # "dhaka " must not suggest "dhakaiya"
        t = self.trie  # one snapshot for the whole request
        key = f"{t.version}:{p}"
        cached = self.cache.get(key)
        if cached is not None:
            return cached
        self.lookups += 1
        found = t.top(p)
        self.cache.put(key, found)
        return found


def show(s: Service, typed: str) -> None:
    parts = [f"{x.query} {x.count}" for x in s.suggest(typed)] or ["(no suggestions)"]
    label = '"' + typed + '"'
    print(f"  {label:<12} -> {' | '.join(parts)}")


def searches(a: Aggregator, q: str, times: int) -> None:
    for _ in range(times):
        a.add(q)


def main() -> None:
    blocked = {"fake"}
    agg = Aggregator()
    # Day 1: what people submitted, messy spelling and all.
    searches(agg, "dhaka weather", 3)
    searches(agg, "Dhaka Weather", 1)
    searches(agg, "  dhaka   weather ", 1)
    searches(agg, "dhakaiya biryani", 4)
    searches(agg, "dhaka fake certificate", 4)
    searches(agg, "dhaka traffic", 3)
    searches(agg, "dhaka to chittagong bus", 2)
    searches(agg, "dal recipe", 2)
    searches(agg, "dhaka metro rail", 1)
    searches(agg, "eid sale", 3)
    searches(agg, "egg price", 1)
    print(f"day 1: {agg.seen} searches logged")
    counts, removed = merge({}, agg.drain(), blocked)
    t1 = Trie(1, counts, 3)
    print(f"build v1: {t1.queries} queries ({removed} blocked), {t1.nodes} trie nodes, top 3 kept per prefix")

    cache = Cache(8)
    s = Service(t1, cache)
    print('user 1 types "dhaka m", one request per keystroke:')
    for p in ["d", "dh", "dha", "dhak", "dhaka", "dhaka ", "dhaka m"]:
        show(s, p)
    print("user 2 and a few others:")
    for p in ["d", "dh", "dha", "  DHAKA  ", "e", "xyz"]:
        show(s, p)
    print(f"cache: {cache.hits} hits, {cache.misses} misses; trie lookups: {s.lookups}")

    # Day 2: a new metro line opens and everyone searches for it.
    searches(agg, "dhaka metro rail", 9)
    searches(agg, "dhaka weather", 1)
    searches(agg, "eid sale", 2)
    print(f"day 2: {agg.seen} searches logged")
    counts, _ = merge(counts, agg.drain(), blocked)
    t2 = Trie(2, counts, 3)
    s.publish(t2)
    print(f"build v2: old counts halved + day 2 added -> {t2.queries} queries; now serving v{s.trie.version}")
    for p in ["d", "dhaka ", "e"]:
        show(s, p)
    print(f"cache: {cache.hits} hits, {cache.misses} misses; trie lookups: {s.lookups}")


if __name__ == "__main__":
    main()

// Search autocomplete's core: searches are counted, a trie with the top k per prefix is built
// offline, swapped in as a whole, and served through a cache whose keys carry the trie's version.

const MAX_LEN = 50;

type Suggestion = { query: string; count: number };

/** More searches first, then alphabetical: the same order in every language. */
function better(a: Suggestion, b: Suggestion): number {
  if (a.count !== b.count) return b.count - a.count;
  return a.query < b.query ? -1 : a.query > b.query ? 1 : 0;
}

class TrieNode {
  kids = new Map<string, TrieNode>();
  count = 0; // > 0 when a whole query ends here
  top: Suggestion[] = []; // best k with this prefix, precomputed
}

/** A read-only snapshot built offline. Every node already knows its top k. */
class Trie {
  root = new TrieNode();
  queries = 0;
  nodes = 1;
  readonly version: number;
  readonly k: number;

  constructor(version: number, counts: Map<string, number>, k: number) {
    this.version = version;
    this.k = k;
    for (const [q, c] of counts) {
      if (c <= 0 || q === "") continue;
      let n = this.root;
      for (const ch of q) {
        let next = n.kids.get(ch);
        if (!next) {
          next = new TrieNode();
          n.kids.set(ch, next);
          this.nodes++;
        }
        n = next;
      }
      n.count = c;
      this.queries++;
    }
    this.fill(this.root, "");
  }

  /** Bottom-up: a node's list is its own query plus its children's lists. */
  private fill(n: TrieNode, path: string): void {
    const all: Suggestion[] = n.count > 0 ? [{ query: path, count: n.count }] : [];
    for (const [ch, kid] of n.kids) {
      this.fill(kid, path + ch);
      all.push(...kid.top);
    }
    n.top = all.sort(better).slice(0, this.k);
  }

  top(prefix: string): Suggestion[] {
    let n: TrieNode | undefined = this.root;
    for (const ch of prefix) {
      n = n.kids.get(ch);
      if (!n) return [];
    }
    return n.top;
  }
}

/** Lowercase, single spaces, trimmed, at most MAX_LEN characters. */
function normalize(s: string): string {
  const one = s.toLowerCase().split(/\s+/).filter((w) => w !== "").join(" ");
  return one.slice(0, MAX_LEN).replace(/ +$/, "");
}

/** Counts submitted searches, like the log pipeline that feeds the builder. */
class Aggregator {
  counts = new Map<string, number>();
  seen = 0;

  add(raw: string): void {
    const q = normalize(raw);
    if (q === "") return;
    this.counts.set(q, (this.counts.get(q) ?? 0) + 1);
    this.seen++;
  }

  drain(): Map<string, number> {
    const out = this.counts;
    this.counts = new Map();
    this.seen = 0;
    return out;
  }
}

/** Old counts halved, recent counts added, queries with a blocked word removed. */
function merge(old: Map<string, number>, recent: Map<string, number>, blocked: Set<string>): [Map<string, number>, number] {
  const counts = new Map<string, number>();
  for (const [q, c] of old) if (Math.floor(c / 2) > 0) counts.set(q, Math.floor(c / 2));
  for (const [q, c] of recent) counts.set(q, (counts.get(q) ?? 0) + c);
  let removed = 0;
  for (const q of [...counts.keys()]) {
    if (q.split(" ").some((w) => blocked.has(w))) {
      counts.delete(q);
      removed++;
    }
  }
  return [counts, removed];
}

/** LRU cache of "version:prefix" -> suggestions, like Redis in front of the trie servers.
 *  (Not called Cache: the DOM already has a global with that name.) */
class SuggestCache {
  items = new Map<string, Suggestion[]>(); // insertion order = least recently used first
  hits = 0;
  misses = 0;
  readonly cap: number;

  constructor(capacity: number) {
    this.cap = capacity;
  }

  get(key: string): Suggestion[] | undefined {
    const v = this.items.get(key);
    if (v === undefined) {
      this.misses++;
      return undefined;
    }
    this.hits++;
    this.items.delete(key);
    this.items.set(key, v);
    return v;
  }

  put(key: string, value: Suggestion[]): void {
    if (this.items.has(key)) {
      this.items.delete(key);
      this.items.set(key, value);
      return;
    }
    if (this.items.size === this.cap) this.items.delete(this.items.keys().next().value!);
    this.items.set(key, value);
  }
}

/** One suggestion server. A new build replaces the trie in one assignment. */
class Service {
  trie: Trie;
  lookups = 0;
  readonly cache: SuggestCache;

  constructor(trie: Trie, cache: SuggestCache) {
    this.trie = trie;
    this.cache = cache;
  }

  publish(trie: Trie): void {
    this.trie = trie;
  }

  suggest(raw: string): Suggestion[] {
    let p = normalize(raw);
    if (p === "") return [];
    if (raw.endsWith(" ") && p.length < MAX_LEN) p += " "; // "dhaka " must not suggest "dhakaiya"
    const t = this.trie; // one snapshot for the whole request
    const key = `${t.version}:${p}`;
    const cached = this.cache.get(key);
    if (cached !== undefined) return cached;
    this.lookups++;
    const found = t.top(p);
    this.cache.put(key, found);
    return found;
  }
}

function show(s: Service, typed: string): void {
  const parts = s.suggest(typed).map((x) => `${x.query} ${x.count}`);
  if (parts.length === 0) parts.push("(no suggestions)");
  console.log(`  ${`"${typed}"`.padEnd(12)} -> ${parts.join(" | ")}`);
}

function searches(a: Aggregator, q: string, times: number): void {
  for (let i = 0; i < times; i++) a.add(q);
}

const blocked = new Set(["fake"]);
const agg = new Aggregator();
// Day 1: what people submitted, messy spelling and all.
searches(agg, "dhaka weather", 3);
searches(agg, "Dhaka Weather", 1);
searches(agg, "  dhaka   weather ", 1);
searches(agg, "dhakaiya biryani", 4);
searches(agg, "dhaka fake certificate", 4);
searches(agg, "dhaka traffic", 3);
searches(agg, "dhaka to chittagong bus", 2);
searches(agg, "dal recipe", 2);
searches(agg, "dhaka metro rail", 1);
searches(agg, "eid sale", 3);
searches(agg, "egg price", 1);
console.log(`day 1: ${agg.seen} searches logged`);
let [counts, removed] = merge(new Map(), agg.drain(), blocked);
const t1 = new Trie(1, counts, 3);
console.log(`build v1: ${t1.queries} queries (${removed} blocked), ${t1.nodes} trie nodes, top 3 kept per prefix`);

const cache = new SuggestCache(8);
const s = new Service(t1, cache);
console.log('user 1 types "dhaka m", one request per keystroke:');
for (const p of ["d", "dh", "dha", "dhak", "dhaka", "dhaka ", "dhaka m"]) show(s, p);
console.log("user 2 and a few others:");
for (const p of ["d", "dh", "dha", "  DHAKA  ", "e", "xyz"]) show(s, p);
console.log(`cache: ${cache.hits} hits, ${cache.misses} misses; trie lookups: ${s.lookups}`);

// Day 2: a new metro line opens and everyone searches for it.
searches(agg, "dhaka metro rail", 9);
searches(agg, "dhaka weather", 1);
searches(agg, "eid sale", 2);
console.log(`day 2: ${agg.seen} searches logged`);
[counts] = merge(counts, agg.drain(), blocked);
const t2 = new Trie(2, counts, 3);
s.publish(t2);
console.log(`build v2: old counts halved + day 2 added -> ${t2.queries} queries; now serving v${s.trie.version}`);
for (const p of ["d", "dhaka ", "e"]) show(s, p);
console.log(`cache: ${cache.hits} hits, ${cache.misses} misses; trie lookups: ${s.lookups}`);

// Search autocomplete's core: searches are counted, a trie with the top k per prefix is built
// offline, swapped in as a whole, and served through a cache whose keys carry the trie's version.
use std::collections::{HashMap, HashSet, VecDeque};
use std::rc::Rc;

const MAX_LEN: usize = 50;

#[derive(Clone, Debug, PartialEq)]
struct Suggestion {
    query: String,
    count: u32,
}

/// More searches first, then alphabetical: the same order in every language.
fn better(a: &Suggestion, b: &Suggestion) -> std::cmp::Ordering {
    b.count.cmp(&a.count).then_with(|| a.query.cmp(&b.query))
}

#[derive(Default)]
struct Node {
    kids: HashMap<u8, Node>,
    count: u32,            // > 0 when a whole query ends here
    top: Vec<Suggestion>,  // best k with this prefix, precomputed
}

/// A read-only snapshot built offline. Every node already knows its top k.
struct Trie {
    root: Node,
    version: u32,
    queries: usize,
    nodes: usize,
}

impl Trie {
    fn build(version: u32, counts: &HashMap<String, u32>, k: usize) -> Trie {
        let mut t = Trie { root: Node::default(), version, queries: 0, nodes: 1 };
        for (q, &c) in counts {
            if c == 0 || q.is_empty() {
                continue;
            }
            let mut n = &mut t.root;
            for &b in q.as_bytes() {
                if !n.kids.contains_key(&b) {
                    t.nodes += 1;
                }
                n = n.kids.entry(b).or_default();
            }
            n.count = c;
            t.queries += 1;
        }
        fill(&mut t.root, &mut Vec::new(), k);
        t
    }

    fn top(&self, prefix: &str) -> &[Suggestion] {
        let mut n = &self.root;
        for b in prefix.as_bytes() {
            match n.kids.get(b) {
                Some(next) => n = next,
                None => return &[],
            }
        }
        &n.top
    }
}

/// Bottom-up: a node's list is its own query plus its children's lists.
fn fill(n: &mut Node, path: &mut Vec<u8>, k: usize) {
    let mut all = Vec::new();
    if n.count > 0 {
        all.push(Suggestion { query: String::from_utf8(path.clone()).unwrap(), count: n.count });
    }
    for (&b, kid) in n.kids.iter_mut() {
        path.push(b);
        fill(kid, path, k);
        path.pop();
        all.extend(kid.top.iter().cloned());
    }
    all.sort_by(better);
    all.truncate(k);
    n.top = all;
}

/// Lowercase, single spaces, trimmed, at most MAX_LEN bytes (ASCII in this demo).
fn normalize(s: &str) -> String {
    let one = s.to_lowercase().split_whitespace().collect::<Vec<_>>().join(" ");
    one[..one.len().min(MAX_LEN)].trim_end_matches(' ').to_string()
}

/// Counts submitted searches, like the log pipeline that feeds the builder.
#[derive(Default)]
struct Aggregator {
    counts: HashMap<String, u32>,
    seen: usize,
}

impl Aggregator {
    fn add(&mut self, raw: &str) {
        let q = normalize(raw);
        if !q.is_empty() {
            *self.counts.entry(q).or_insert(0) += 1;
            self.seen += 1;
        }
    }

    fn drain(&mut self) -> HashMap<String, u32> {
        self.seen = 0;
        std::mem::take(&mut self.counts)
    }
}

/// Old counts halved, recent counts added, queries with a blocked word removed.
fn merge(old: &HashMap<String, u32>, recent: HashMap<String, u32>, blocked: &HashSet<&str>) -> (HashMap<String, u32>, usize) {
    let mut counts: HashMap<String, u32> = old.iter().filter(|(_, &c)| c / 2 > 0).map(|(q, &c)| (q.clone(), c / 2)).collect();
    for (q, c) in recent {
        *counts.entry(q).or_insert(0) += c;
    }
    let before = counts.len();
    counts.retain(|q, _| !q.split(' ').any(|w| blocked.contains(w)));
    let removed = before - counts.len();
    (counts, removed)
}

/// LRU cache of "version:prefix" -> suggestions, like Redis in front of the trie servers.
struct Cache {
    cap: usize,
    items: HashMap<String, Vec<Suggestion>>,
    order: VecDeque<String>, // front = least recently used (fine for a tiny demo cache)
    hits: usize,
    misses: usize,
}

impl Cache {
    fn new(cap: usize) -> Cache {
        Cache { cap, items: HashMap::new(), order: VecDeque::new(), hits: 0, misses: 0 }
    }

    fn touch(&mut self, key: &str) {
        self.order.retain(|k| k != key);
        self.order.push_back(key.to_string());
    }

    fn get(&mut self, key: &str) -> Option<Vec<Suggestion>> {
        match self.items.get(key).cloned() {
            None => {
                self.misses += 1;
                None
            }
            Some(v) => {
                self.hits += 1;
                self.touch(key);
                Some(v)
            }
        }
    }

    fn put(&mut self, key: &str, value: Vec<Suggestion>) {
        if !self.items.contains_key(key) && self.items.len() == self.cap {
            if let Some(old) = self.order.pop_front() {
                self.items.remove(&old);
            }
        }
        self.items.entry(key.to_string()).or_insert(value);
        self.touch(key);
    }
}

/// One suggestion server. A new build replaces the trie by swapping one shared pointer;
/// a request holds its own Rc, so it finishes on the trie it started with.
struct Service {
    trie: Rc<Trie>,
    cache: Cache,
    lookups: usize,
}

impl Service {
    fn publish(&mut self, t: Trie) {
        self.trie = Rc::new(t);
    }

    fn suggest(&mut self, raw: &str) -> Vec<Suggestion> {
        let mut p = normalize(raw);
        if p.is_empty() {
            return Vec::new();
        }
        if raw.ends_with(' ') && p.len() < MAX_LEN {
            p.push(' '); // "dhaka " must not suggest "dhakaiya"
        }
        let t = Rc::clone(&self.trie); // one snapshot for the whole request
        let key = format!("{}:{}", t.version, p);
        if let Some(v) = self.cache.get(&key) {
            return v;
        }
        self.lookups += 1;
        let found = t.top(&p).to_vec();
        self.cache.put(&key, found.clone());
        found
    }
}

fn show(s: &mut Service, typed: &str) {
    let mut parts: Vec<String> = s.suggest(typed).iter().map(|x| format!("{} {}", x.query, x.count)).collect();
    if parts.is_empty() {
        parts.push("(no suggestions)".to_string());
    }
    println!("  {:<12} -> {}", format!("\"{}\"", typed), parts.join(" | "));
}

fn searches(a: &mut Aggregator, q: &str, times: u32) {
    for _ in 0..times {
        a.add(q);
    }
}

fn main() {
    let blocked: HashSet<&str> = ["fake"].into_iter().collect();
    let mut agg = Aggregator::default();
    // Day 1: what people submitted, messy spelling and all.
    searches(&mut agg, "dhaka weather", 3);
    searches(&mut agg, "Dhaka Weather", 1);
    searches(&mut agg, "  dhaka   weather ", 1);
    searches(&mut agg, "dhakaiya biryani", 4);
    searches(&mut agg, "dhaka fake certificate", 4);
    searches(&mut agg, "dhaka traffic", 3);
    searches(&mut agg, "dhaka to chittagong bus", 2);
    searches(&mut agg, "dal recipe", 2);
    searches(&mut agg, "dhaka metro rail", 1);
    searches(&mut agg, "eid sale", 3);
    searches(&mut agg, "egg price", 1);
    println!("day 1: {} searches logged", agg.seen);
    let (counts, removed) = merge(&HashMap::new(), agg.drain(), &blocked);
    let t1 = Trie::build(1, &counts, 3);
    println!("build v1: {} queries ({} blocked), {} trie nodes, top 3 kept per prefix", t1.queries, removed, t1.nodes);

    let mut s = Service { trie: Rc::new(t1), cache: Cache::new(8), lookups: 0 };
    println!("user 1 types \"dhaka m\", one request per keystroke:");
    for p in ["d", "dh", "dha", "dhak", "dhaka", "dhaka ", "dhaka m"] {
        show(&mut s, p);
    }
    println!("user 2 and a few others:");
    for p in ["d", "dh", "dha", "  DHAKA  ", "e", "xyz"] {
        show(&mut s, p);
    }
    println!("cache: {} hits, {} misses; trie lookups: {}", s.cache.hits, s.cache.misses, s.lookups);

    // Day 2: a new metro line opens and everyone searches for it.
    searches(&mut agg, "dhaka metro rail", 9);
    searches(&mut agg, "dhaka weather", 1);
    searches(&mut agg, "eid sale", 2);
    println!("day 2: {} searches logged", agg.seen);
    let (counts, _) = merge(&counts, agg.drain(), &blocked);
    let t2 = Trie::build(2, &counts, 3);
    let queries = t2.queries;
    s.publish(t2);
    println!("build v2: old counts halved + day 2 added -> {} queries; now serving v{}", queries, s.trie.version);
    for p in ["d", "dhaka ", "e"] {
        show(&mut s, p);
    }
    println!("cache: {} hits, {} misses; trie lookups: {}", s.cache.hits, s.cache.misses, s.lookups);
}