Design Search Autocomplete

Java — TrieNode with HashMap children and frequency counter

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

public class TrieNode {

    // Character children — HashMap chosen over array[26] to
    // support spaces, digits, and non-ASCII characters.
    final Map<Character, TrieNode> children = new HashMap<>();

    // Frequency of this exact query string ending at this node.
    // 0 means this node is only an intermediate prefix, not a complete query.
    int frequency = 0;

    // Pre-computed top-K suggestions rooted at this node.
    // Populated during the offline build phase (see TopK section).
    // Null until build is complete.
    TopKList topK = null;
}

public class Trie {

    private final TrieNode root = new TrieNode();

    /** Insert or increment a query. O(L) where L = query.length(). */
    public void insert(String query, int count) {
        TrieNode node = root;
        for (char c : query.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.frequency += count;
    }

    /**
     * Traverse to the node representing the given prefix. O(L).
     * Returns null if the prefix does not exist in the trie.
     */
    public TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) return null;
        }
        return node;
    }
}

Java — Post-order DFS building top-K list at every Trie node using a min-heap

import java.util.*;

public class Suggestion implements Comparable<Suggestion> {
    final String query;
    final int frequency;

    Suggestion(String query, int frequency) {
        this.query = query;
        this.frequency = frequency;
    }

    // Natural order: ascending frequency (min at top of min-heap)
    @Override
    public int compareTo(Suggestion other) {
        return Integer.compare(this.frequency, other.frequency);
    }
}

public class TrieBuilder {

    private static final int TOP_K = 5;

    /**
     * Post-order DFS: builds top-K list for every node.
     * Returns the top-K list for the subtree rooted at this node.
     */
    public List<Suggestion> buildTopK(TrieNode node, String currentPrefix) {
        // Min-heap of size K — evicts lowest-frequency entries
        PriorityQueue<Suggestion> heap = new PriorityQueue<>(TOP_K + 1);

        // Include this node itself if it is a complete query
        if (node.frequency > 0) {
            heap.offer(new Suggestion(currentPrefix, node.frequency));
        }

        // Recurse into children and merge their top-K lists
        for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
            List<Suggestion> childTopK =
                buildTopK(entry.getValue(), currentPrefix + entry.getKey());

            for (Suggestion s : childTopK) {
                heap.offer(s);
                if (heap.size() > TOP_K) {
                    heap.poll(); // evict minimum-frequency entry
                }
            }
        }

        // Convert heap to sorted descending list
        List<Suggestion> result = new ArrayList<>(heap);
        result.sort((a, b) -> Integer.compare(b.frequency, a.frequency));

        // Cache the result on the node for O(1) lookup later
        node.topK = result;
        return result;
    }
}

Java — Redis Sorted Set cache: top-K lookup, populate, and frequency increment

import redis.clients.jedis.Jedis;
import redis.clients.jedis.resps.Tuple;
import java.util.List;
import java.util.Set;

public class RedisAutocompleteCache {

    private static final int TOP_K = 5;
    private static final long TTL_SECONDS = 3600; // 1 hour for low-traffic prefixes

    private final Jedis jedis;

    public RedisAutocompleteCache(Jedis jedis) {
        this.jedis = jedis;
    }

    /**
     * Retrieve top-K suggestions for a prefix.
     * Returns an empty list on cache miss (caller must fall back to Trie).
     * O(log N + K) where N = members in the sorted set.
     */
    public List<String> getTopK(String prefix) {
        String key = "ac:" + prefix.toLowerCase();
        // ZREVRANGE returns members ordered highest score first
        List<String> results = jedis.zrevrange(key, 0, TOP_K - 1);
        return results; // empty list = cache miss
    }

    /**
     * Populate (or refresh) the cache for a prefix with a full top-K list.
     * Called by the offline aggregation job after each rebuild cycle.
     */
    public void populate(String prefix, List<Suggestion> topK) {
        String key = "ac:" + prefix.toLowerCase();
        jedis.del(key);
        for (Suggestion s : topK) {
            jedis.zadd(key, s.frequency, s.query);
        }
        jedis.expire(key, TTL_SECONDS);
    }

    /**
     * Increment the frequency of a query for all its prefixes.
     * Called by the near-real-time Flink pipeline for trending queries.
     * O(L × log N) where L = query length.
     */
    public void incrementFrequency(String query, long delta) {
        for (int i = 1; i <= query.length(); i++) {
            String prefix = query.substring(0, i).toLowerCase();
            String key = "ac:" + prefix;
            jedis.zincrby(key, delta, query);
        }
    }
}

Java — Non-blocking query logger with in-memory buffer and async Kafka flush

import org.apache.kafka.clients.producer.*;
import java.util.Properties;
import java.util.concurrent.*;

public class QueryLogger {

    private static final int BUFFER_SIZE = 10_000;
    private static final long FLUSH_INTERVAL_MS = 100;

    private final KafkaProducer<String, String> producer;
    private final BlockingQueue<String> buffer = new ArrayBlockingQueue<>(BUFFER_SIZE);

    public QueryLogger(Properties kafkaProps) {
        this.producer = new KafkaProducer<>(kafkaProps);
        startFlushThread();
    }

    /**
     * Non-blocking log of a submitted query.
     * Drops silently if the buffer is full — acceptable: we prefer low latency
     * over 100% capture accuracy for autocomplete frequency data.
     */
    public void log(String query) {
        buffer.offer(normalize(query)); // offer = non-blocking, returns false if full
    }

    /** Background flush: drains the buffer to Kafka every FLUSH_INTERVAL_MS. */
    private void startFlushThread() {
        Executors.newSingleThreadScheduledExecutor().scheduleAtFixedRate(() -> {
            String query;
            while ((query = buffer.poll()) != null) {
                producer.send(
                    new ProducerRecord<>("search-queries", query, query),
                    (meta, ex) -> { if (ex != null) ex.printStackTrace(); }
                );
            }
        }, 0, FLUSH_INTERVAL_MS, TimeUnit.MILLISECONDS);
    }

    /** Normalize: lowercase, trim whitespace, collapse multiple spaces. */
    private String normalize(String query) {
        return query.toLowerCase().trim().replaceAll("\\s+", " ");
    }
}

Java — LRU prefix result cache and shard router for horizontal scaling

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

/**
 * Thread-safe in-memory prefix cache for a single Trie shard.
 * Used inside the Trie Service to avoid re-traversing the trie for
 * hot prefixes within a short time window.
 */
public class PrefixResultCache {

    private static final int MAX_ENTRIES = 50_000;
    private static final long TTL_MS = 300_000; // 5 minutes

    // LRU cache: prefix → (result list, expiry timestamp)
    private final Map<String, CacheEntry> store =
        Collections.synchronizedMap(new LinkedHashMap<>(MAX_ENTRIES, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, CacheEntry> eldest) {
                return size() > MAX_ENTRIES;
            }
        });

    public Optional<List<String>> get(String prefix) {
        CacheEntry entry = store.get(prefix);
        if (entry == null || System.currentTimeMillis() > entry.expiryMs) {
            store.remove(prefix);
            return Optional.empty();
        }
        return Optional.of(entry.results);
    }

    public void put(String prefix, List<String> results) {
        store.put(prefix, new CacheEntry(results, System.currentTimeMillis() + TTL_MS));
    }

    private record CacheEntry(List<String> results, long expiryMs) {}
}

/**
 * Shard router: maps prefix to the correct Redis shard node.
 * Shards by first two characters of the prefix.
 */
public class PrefixShardRouter {

    private final Map<String, RedisAutocompleteCache> shards;

    public PrefixShardRouter(Map<String, RedisAutocompleteCache> shards) {
        this.shards = shards;
    }

    public RedisAutocompleteCache route(String prefix) {
        String key = prefix.length() >= 2
            ? prefix.substring(0, 2).toLowerCase()
            : prefix.substring(0, 1).toLowerCase() + "_";
        // Default to a catch-all shard if the exact bucket isn't present
        return shards.getOrDefault(key, shards.get("default"));
    }
}