Definition
- Trie / edge-ngram – A prefix tree or pre-tokenized prefix index makes prefix lookups near-instant by direct traversal.
- Pre-ranked lists – Each node stores the top K completions already sorted by popularity and recency, so no sorting at query time.
- Debounce – The client waits 150-300ms after the last keystroke before sending, collapsing many characters into one request.
- Cache – Hot prefixes like "ho" and "lo" are cached in Redis so common queries skip the trie entirely.
- Latency budget – Suggestions must appear before the user types the next character: single-digit milliseconds.
When Rajesh types into National Bank of India's search box, as he types "ho" it should instantly suggest "home loan", "home insurance". Imagine a smart index where all known search phrases are filed by their first letters, and under "ho" there is already a short pinned list of the most popular phrases. The moment Rajesh types "ho", the clerk flips straight to that pre-written list. The box also waits a fraction of a second after he stops typing before asking (debounce).
Understanding the Concepts
Why do prefix lookups need a special structure?
Doing LIKE 'ho%' can use a B-tree index but still returns and ranks many rows per keystroke. A trie or edge-ngram index turns prefix search into a direct traversal.
package com.bank.autocomplete;
import java.util.*;
public class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
List<String> topSuggestions = new ArrayList<>(); // pre-ranked top K
}
public class PrefixTrie {
private final TrieNode root = new TrieNode();
public void insert(String phrase, int score) {
TrieNode node = root;
for (char c : phrase.toLowerCase().toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new TrieNode());
// Update top suggestions at each prefix node
updateTopK(node, phrase, score);
}
}
public List<String> suggest(String prefix) {
TrieNode node = root;
for (char c : prefix.toLowerCase().toCharArray()) {
node = node.children.get(c);
if (node == null) return List.of(); // no match
}
return node.topSuggestions; // pre-ranked, no sorting needed
}
private void updateTopK(TrieNode node, String phrase, int score) {
node.topSuggestions.remove(phrase);
node.topSuggestions.add(phrase);
// Sort by score and keep top 5
node.topSuggestions.sort(Comparator.comparingInt(this::getScore).reversed());
if (node.topSuggestions.size() > 5) {
node.topSuggestions = new ArrayList<>(node.topSuggestions.subList(0, 5));
}
}
private int getScore(String phrase) { return phrase.length(); } // simplified
public static void main(String[] args) {
PrefixTrie trie = new PrefixTrie();
trie.insert("home loan", 950);
trie.insert("home insurance", 720);
trie.insert("housing scheme", 680);
trie.insert("car loan", 850);
System.out.println("Prefix 'ho': " + trie.suggest("ho"));
System.out.println("Prefix 'hom': " + trie.suggest("hom"));
System.out.println("Prefix 'ca': " + trie.suggest("ca"));
}
}
Prefix 'ho': [home loan, home insurance, housing scheme]
Prefix 'hom': [home loan, home insurance]
Prefix 'ca': [car loan]
How do you debounce client requests?
Wait a short idle period after the last keystroke before sending. Cancel in-flight requests when new keys arrive.
package com.bank.autocomplete.client;
// JavaScript-style debounce (conceptual Java equivalent)
public class DebounceExample {
// Typing "home loan" without debounce: 9 requests (h, ho, hom, ...)
// With 200ms debounce: 1-2 requests ("home" after pause, "home loan" after pause)
// Savings: 80%+ fewer requests
// Cancel stale in-flight responses:
// If user types "ho" then immediately "hom",
// discard the response for "ho" so it does not overwrite "hom" results.
}
How do you cache hot prefixes?
A small number of prefixes account for most traffic. Cache them in Redis.
package com.bank.autocomplete.cache;
import java.util.List;
public class PrefixCache {
private final RedisClient redis;
private final PrefixTrie trie;
public PrefixCache(RedisClient redis, PrefixTrie trie) {
this.redis = redis;
this.trie = trie;
}
public List<String> suggest(String prefix) {
// Check cache first
List<String> cached = redis.getList("autocomplete:" + prefix);
if (cached != null) return cached;
// Cache miss: query trie, populate cache
List<String> suggestions = trie.suggest(prefix);
redis.setList("autocomplete:" + prefix, suggestions, 300); // TTL 5 min
return suggestions;
}
}
How do you rank suggestions?
Each phrase has a score combining popularity (search frequency) and recency (trending phrases surface). The score is precomputed at each trie node.
package com.bank.autocomplete.ranking;
public class SuggestionScorer {
public int computeScore(String phrase, long searchCount, long daysOld) {
// Popularity: higher search count = higher score
int popularity = (int) Math.min(searchCount, 1000);
// Recency: newer = higher boost
int recencyBoost = daysOld < 7 ? 200 : daysOld < 30 ? 100 : 0;
return popularity + recencyBoost;
}
}
How do you handle scale and updates?
Build the trie offline from query logs and product catalogs. Usage events stream in and refresh scores periodically.
package com.bank.autocomplete.build;
public class TrieBuilder {
public PrefixTrie buildFromQueryLogs() {
PrefixTrie trie = new PrefixTrie();
// Read query logs: "home loan" searched 950 times
trie.insert("home loan", 950);
trie.insert("home insurance", 720);
trie.insert("fixed deposit", 880);
// Load into memory on each suggestion server
return trie;
}
// Background: usage events update scores without blocking reads
}
What about fuzzy prefix matching?
Layer fuzzy matching on carefully, only when exact prefix returns too few results.
package com.bank.autocomplete.fuzzy;
public class FuzzyPrefixSearch {
public List<String> suggestWithFuzzy(String prefix) {
List<String> exact = trie.suggest(prefix);
if (exact.size() >= 3) return exact; // enough results
// Too few exact matches: try fuzzy (edit distance 1)
// "hoe" -> try "hom", "hob", "hoe" variants
// More expensive, use sparingly
return fuzzySearch(prefix, 1);
}
}
What are common interview follow-up questions?
How would you personalize autocomplete per user? How do you handle offensive or blacklisted suggestions? How do you shard the trie for a very large vocabulary? What is the difference between a trie and an edge-ngram index in Elasticsearch? How do you A/B test different ranking algorithms?
What should a senior engineer know?
A senior engineer personalizes autocomplete by blending a per-user model (recent searches) with the global popularity model, shards the trie by first character for a large vocabulary, and A/B tests ranking algorithms by measuring click-through rate on the second-ranked suggestion versus the first.
package com.bank.autocomplete;
public class SeniorAutocompleteGuidelines {
public static void main(String[] args) {
System.out.println("Senior autocomplete guidelines:");
System.out.println(" 1. Personalize: blend user-recent + global-popularity scores");
System.out.println(" 2. Shard trie by first character across servers for scale");
System.out.println(" 3. Blacklist: filter offensive or confidential suggestions");
System.out.println(" 4. A/B test ranking: measure click-through on top-K results");
System.out.println(" 5. Edge-ngram in Elasticsearch: alternative to in-memory trie");
System.out.println(" 6. Latency budget: trie lookup < 1ms, total with cache < 5ms");
System.out.println(" 7. Monitor: cache hit rate, p99 latency, suggestion click rate");
}
}
Expected output:
Senior autocomplete guidelines:
1. Personalize: blend user-recent + global-popularity scores
2. Shard trie by first character across servers for scale
3. Blacklist: filter offensive or confidential suggestions
4. A/B test ranking: measure click-through on top-K results
5. Edge-ngram in Elasticsearch: alternative to in-memory trie
6. Latency budget: trie lookup < 1ms, total with cache < 5ms
7. Monitor: cache hit rate, p99 latency, suggestion click rate
Visual Overview
┌──────────────────────────────────────────────────────────┐ │ AUTOCOMPLETE / TYPE-AHEAD │ ├──────────────────────────────────────────────────────────┤ │ │ │ Rajesh types: h → ho → hom → home │ │ │ │ │ ┌──────▼───────────────┐ │ │ │ Client Debounce │ (200ms idle → send) │ │ │ Cancel stale request │ │ │ └──────────┬───────────┘ │ │ │ "ho" (after debounce) │ │ ▼ │ │ ┌──────────────────────┐ │ │ │ Redis Cache │ │ │ │ Key: autocomplete:ho │ │ │ └────┬─────────┬───────┘ │ │ hit │ │ miss │ │ ▼ ▼ │ │ Return ┌──────────────┐ │ │ cached │ In-Memory │ │ │ list │ Trie │ │ │ │ │ │ │ │ root │ │ │ │ └─h │ │ │ │ └─o ◀──── │ node: topK=[home loan, │ │ │ └─m │ home insurance, │ │ │ └─e │ housing scheme] │ │ └──────────────┘ │ │ │ │ Response: ["home loan", "home insurance", ...] │ │ Latency: < 5ms │ └──────────────────────────────────────────────────────────┘
Key Takeaway
Autocomplete has one brutal requirement: return ranked completions faster than the user types the next character, targeting single-digit milliseconds. At National Bank of India, a LIKE query returned results alphabetically and buried the most popular home loan. Pankaj replaced it with a trie where each prefix node stores the top K completions pre-ranked by popularity and recency, so the request path is a trivial pinned-list read with no sorting.
On the client side, debouncing collapses many keystrokes into one or two requests (a 200ms idle wait before sending), cutting volume by 80 percent. Hot prefixes like "ho" and "lo" are cached in Redis so common queries skip the trie entirely. The structure is built offline from query logs and the product catalog, and usage events refresh scores in the background without blocking reads.
For typos, fuzzy prefix matching using edit distance is layered on carefully, only when the exact prefix returns too few results, because fuzzy is more expensive. For a huge vocabulary, the trie is sharded by first letters across servers. The guiding principle is a read-heavy, precompute-everything mindset: move all expensive work (ranking, sorting, aggregation) to an offline path and make the request a trivial pinned-list read.
Remember one sentence: Store phrases in a trie with pre-ranked completions pinned at every prefix node, debounce keystrokes, cache hot prefixes, and move all ranking to the background so the request is a trivial list read in a few milliseconds.
---