Query understanding, hybrid retrieval, autocomplete, spell correction
The query-side pipeline — and the four search "design" problems from your topic list.
Concept → your projects
The query-side pipeline (before ranking): normalize (case, unicode, stemming) → parse (filters, phrases, fielded terms) → expand (synonyms, stemming, learned expansion) → rewrite (spell-correct, intent-shift) → route (which index/shard).
Spell correction / did-you-mean: candidate generation via edit distance (Levenshtein ≤ 2) constrained by an index of terms, or Norvig's noisy-channel model: argmax P(term) · P(typo|term) — prior (term frequency) × error model (edit operations with learned weights). Efficient candidate lookup: BK-trees (edit-distance-indexed), SymSpell (delete-variant hashing — the production trick: precompute deletes within distance k, look up O(1)), or trigram indexes. The key insight: correction needs frequency data (the corpus's own term stats) — which is why you build it on your inverted index, not as a separate model.
Autocomplete: three flavors — prefix trie (walk to prefix node, top-k by weight; the classic "typeahead" with per-node cached top-k), query-log completions (what real users typed — usually beats trie on relevance: rank by historical frequency + recency decay), and context-aware (personalized, session-based). Design questions that matter: where the top-k comes from (precomputed per node = memory-heavy but O(prefix)), how you handle updates (rebuild/merge), and the latency budget (<100 ms — it's keystroke-rate).
Recent searches: a small, per-user, ordered-by-recency store — your topic list marks it as a design exercise; the honest answer: it's a KV list (LPUSH/LTRIM in Redis, or a small table with (user_id, created_at) index), capped (say 10), deduped on insert, and privacy-scoped (per-device? synced? TTL?). The interesting design bit is not storage — it's whether recents are shared across devices (identity-scoped) or device-scoped, and how deletion works (GDPR: a "clear history" that must actually delete, not tombstone).
Related searches: query-query similarity — co-clicked queries (session mining), or embedding similarity over query logs (you have the machinery: pgvector + cosine over query embeddings is exactly the zoth pattern applied to a different corpus). This is the "your vector search is a reusable capability" point: same index, different embedding source.
Your systems' position (honest map)
- zoth: semantic retrieval for advisory grounding (Day 66); no query parser, no spell correction, no autocomplete — none are requirements (queries are programmatic: embed this request, fetch precedents).
- traverse: no search surface at all — problems are fetched by
(platform, slug)keys, not searched. If a "search my solved problems" feature appeared: Postgres full-text (tsvector+ GIN) is the right first answer; a trie/autocomplete is only worth it with a large catalog and a UX that demands sub-100 ms prefix completion.
The mature framing: "I know the full pipeline, and I also know which three stages my product doesn't need — search infra is easy to over-build." That sentence differentiates you from candidates who'd stand up Elasticsearch for a 200-row table.
Bulletproof your resume
Say these answers aloud before moving on
These are the follow-ups an interviewer will actually ask about your projects.
How would you build did-you-mean without a search cluster?
Postgres + a term-frequency table: extract terms from the corpus (tsvector/ts_stat), store frequencies, generate candidates for a mistyped query via trigram similarity (pg_trgm's GIN index over terms) or delete-variant hashing, then rank by noisy-channel (prior frequency × edit probability). At my corpus sizes, pg_trgm with a GIN index is O(ms) and needs zero new infrastructure — the same 'exhaust the database first' discipline as everywhere else in my stack.
Design autocomplete for a 1M-item catalog.
Offline: build a prefix index — a trie or a materialized table of (prefix, top-k items) with weights from popularity + recency; the latter is the classic memory-vs-compute trade (precomputed top-k per prefix = O(1) lookup, big table). Online: keystroke → prefix lookup → top-k → return in <100 ms, with a query-log layer blended in (real queries beat synthetic prefixes). Updates: rebuild or incremental merge on a schedule; personalization via a per-user recency boost at merge time, not in the index. And the failure mode to design for: empty/rare prefixes (fall back to fuzzy/lexical) and abusive prefixes (rate limit, cache negative results).
What's the design risk in recent-searches features?
Privacy and deletion semantics. Recents are query history — arguably sensitive (searches can reveal intent/health/finance). So: scope (device vs account), TTL, an actual delete path (not tombstone — 'clear history' must be unrecoverable), and exclusion rules (never store queries with PII, or hash them). Technically it's trivial storage — a capped list per user — so the design work is entirely about scope and retention. That's a good example of a 'simple' feature whose difficulty is policy, not code.