Design: Search Autocomplete

         root
        /    \
       a      b
      / \      \
    ap   ar    be
    |    |      |
  app   art   best

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    List<String> topK = new ArrayList<>(); // top 5 suggestions for this prefix
}

class Autocomplete {
    private TrieNode root = new TrieNode();

    public List<String> getSuggestions(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) return List.of();
            node = node.children.get(c);
        }
        return node.topK; // pre-cached top K for this prefix
    }

    // Rebuild trie periodically from frequency data
    void buildTrie(Map<String, Long> queryFrequencies) {
        for (Map.Entry<String, Long> entry : queryFrequencies.entrySet()) {
            insert(entry.getKey(), entry.getValue());
        }
    }
}

Data Collection:
  User searches → Kafka → Aggregation Service → Query Frequency Store (Cassandra)
                   every 1 hour:
                        ↓
                 [Trie Builder Job] → serialized trie → S3
                        ↓ (every 1 hour)
                 [Autocomplete Servers] load new trie into memory

Query Path:
  User types "app" → [API Gateway] → [Autocomplete Server (trie in RAM)] → [Redis Cache] → top 5

80/20 rule: 20% of prefixes account for 80% of traffic
→ Cache top prefixes in Redis

// Cache key: "ac:{prefix}"
// TTL: 1 hour (matches trie rebuild frequency)

Base suggestions: global top-K (from trie)
Personalized: blend with user's search history
  e.g., "apple" → global top = [apple, apple store, applebee's]
                 → for a developer: [apple, apple developer, apple swift]