Design a Search Autocomplete / Typeahead

• Trie : a tree where each edge is a character; walking a path spells a prefix, and the node represents all queries starting with it.
• Top-K precomputation : storing the K most popular completions at each trie node for near-constant-time results.
• Query log : the source of popularity data; each search increments a query's frequency.
• Batched updates : periodically rebuilding top-K lists from recent logs to keep suggestions fresh without slowing reads.

How does the trie work?

A trie is a tree where each edge is a character. Walking the path for a prefix lands on the node that represents all completions starting with those characters. The walk costs only the length of the prefix, making it independent of vocabulary size. At National Bank of India, thousands of searchable actions exist, but the trie finds matches for "tra" in microseconds.

package com.bank.search;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;

public class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    List<String> topK = new ArrayList<>();
}

public class Trie {
    private final TrieNode root = new TrieNode();

    public TrieNode walk(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) return null;
        }
        return node;
    }
}

Why precompute top-K at each node?

Scanning every descendant of a prefix node would be too slow for real-time suggestions. By storing the K most popular completions directly at each node during a batch rebuild, answering a query becomes a simple lookup. The precomputed list at the "tra" node might hold "transfer money" (searched 50,000 times), "transaction history" (40,000), and "track cheque" (15,000).

package com.bank.search;

import java.util.*;
import java.util.stream.Collectors;

public class TopKBuilder {
    public void rebuild(TrieNode node, Map<String, Long> frequencies) {
        node.topK = frequencies.entrySet().stream()
            .sorted(Map.Entry.<String, Long>comparingByValue().reversed())
            .limit(10)
            .map(Map.Entry::getKey)
            .collect(Collectors.toList());
    }
}

How do popularity rankings get updated?

Query logs are processed in batches by a background job. The job reads recent search events, updates frequency counts, and rebuilds the top-K lists at affected trie nodes. This keeps reads fast (no locking during updates) while staying reasonably fresh. At National Bank of India, the batch runs every five minutes.

package com.bank.search;

import java.util.List;
import java.util.Map;
import java.util.HashMap;

public class QueryLogProcessor {
    public Map<String, Long> aggregate(List<String> recentQueries) {
        Map<String, Long> frequencies = new HashMap<>();
        for (String query : recentQueries)
            frequencies.merge(query, 1L, Long::sum);
        return frequencies;
    }
}

How does caching help?

The hottest prefixes (single letters like "t", "a", "s") are cached in Redis so even the trie walk is skipped. These prefixes account for the majority of requests because every search starts with a single character. The cache has a short TTL and is refreshed after each batch rebuild.

package com.bank.search;

import java.util.List;

public class PrefixCacheService {
    public List<String> suggest(String prefix) {
        List<String> cached = redis.get("suggest:" + prefix);
        if (cached != null) return cached;  // cache hit, skip trie
        TrieNode node = trie.walk(prefix);
        if (node == null) return List.of();
        redis.setex("suggest:" + prefix, 300, node.topK);  // cache for 5 min
        return node.topK;
    }
}

What is the freshness trade-off?

Reads must be instant (under 100 ms), so a new trending query may take minutes to appear in suggestions. This is eventual consistency applied to rankings. If the bank launches a new "instant loan" feature and customers start searching for it, the suggestion appears after the next batch run, not immediately.

How do you filter by context?

Filter suggestions by user role and permissions so customers never see admin actions like "manage users" or "override limits." The trie stores all suggestions, and a post-filter removes ineligible ones before returning results to the client.

How does the search box interaction work?

On each keystroke, the client sends the current prefix and receives top-K suggestions within 50 to 100 milliseconds. The client debounces keystrokes to avoid flooding the server with requests for every character.

How do you handle multi-language input?

For non-Latin scripts like Hindi or Tamil, the trie indexes Unicode characters. The trie structure works the same way, but the character set is larger. Normalization (lowercasing, accent removal) is applied before insertion and lookup.

What should a senior engineer know?

A senior engineer considers sharding the trie by prefix range for horizontal scale, internationalization for non-Latin scripts, and personalization that blends global popularity with per-user query history. They also monitor suggestion click-through rates to validate ranking quality and detect stale or misleading suggestions.