Design a Search Autocomplete

Difficulty: Intermediate

Question

Design a search autocomplete system like Google's search suggestions. How would you handle real-time suggestions for billions of queries?

Answer

Autocomplete provides real-time search suggestions as the user types. It must be fast (< 100ms), relevant, and personalized.

Core components: 1. Data Collection: Aggregate search queries with frequency counts 2. Trie/Prefix Index: Efficiently look up suggestions by prefix 3. Ranking Service: Order suggestions by popularity, recency, personalization 4. Caching Layer: Cache popular prefixes in Redis 5. Client: Debounced input with dropdown UI

Scale considerations: - Billions of unique queries require distributed storage - Trie is rebuilt periodically from aggregated query logs - Top-K results per prefix are pre-computed and cached - Personalization layer adds user-specific suggestions on top

Code examples

Trie-Based Autocomplete

// Trie data structure for prefix lookup
class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
    this.frequency = 0;
    this.topSuggestions = [];  // Pre-computed top-K
  }
}

class AutocompleteTrie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word, frequency) {
    let node = this.root;
    for (const char of word.toLowerCase()) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
      // Update top suggestions at each prefix node
      this.updateTopK(node, word, frequency);
    }
    node.isEnd = true;
    node.frequency = frequency;
  }

  updateTopK(node, word, frequency, k = 10) {
    const existing = node.topSuggestions.find(s => s.word === word);
    if (existing) {
      existing.frequency = frequency;
    } else {
      node.topSuggestions.push({ word, frequency });
    }
    node.topSuggestions.sort((a, b) => b.frequency - a.frequency);
    node.topSuggestions = node.topSuggestions.slice(0, k);
  }

  search(prefix) {
    let node = this.root;
    for (const char of prefix.toLowerCase()) {
      if (!node.children[char]) return [];
      node = node.children[char];
    }
    return node.topSuggestions;
  }
}

Each trie node stores pre-computed top-K suggestions, so lookups are O(prefix length) regardless of how many total suggestions exist. The trie is rebuilt periodically from query logs.

Redis-Based Autocomplete at Scale

// Redis sorted set approach (production-friendly)

// Build index from query logs
async function buildAutocompleteIndex(queryLogs) {
  for (const { query, count } of queryLogs) {
    const normalized = query.toLowerCase().trim();

    // Add all prefixes to sorted sets
    for (let i = 1; i <= normalized.length; i++) {
      const prefix = normalized.substring(0, i);
      await redis.zincrby(
        `autocomplete:${prefix}`,
        count,
        normalized
      );
    }
  }

  // Trim to top 10 per prefix and set TTL
  // (done in batch job)
}

// Query autocomplete
async function getSuggestions(prefix, limit = 10) {
  const cacheKey = `autocomplete:${prefix.toLowerCase()}`;

  // Get top suggestions by score (descending)
  const suggestions = await redis.zrevrange(
    cacheKey, 0, limit - 1, 'WITHSCORES'
  );

  return suggestions.map(([query, score]) => ({
    query,
    score: parseFloat(score)
  }));
}

// API endpoint
app.get('/api/autocomplete', async (req, res) => {
  const { q } = req.query;
  if (!q || q.length < 2) return res.json([]);

  const suggestions = await getSuggestions(q);
  res.json(suggestions);
});

Redis sorted sets provide O(log N) insertion and O(log N + K) retrieval of top-K results. This approach is simpler to deploy and scale than an in-memory trie, and handles updates more gracefully.

Client-Side Debouncing

// React autocomplete component
function SearchBar() {
  const [query, setQuery] = useState('');
  const [suggestions, setSuggestions] = useState([]);

  // Debounce API calls (wait 200ms after last keystroke)
  const fetchSuggestions = useMemo(
    () => debounce(async (q) => {
      if (q.length < 2) {
        setSuggestions([]);
        return;
      }
      const res = await fetch(`/api/autocomplete?q=${encodeURIComponent(q)}`);
      const data = await res.json();
      setSuggestions(data);
    }, 200),
    []
  );

  const handleChange = (e) => {
    setQuery(e.target.value);
    fetchSuggestions(e.target.value);
  };

  return (
    <div>
      <input value={query} onChange={handleChange} />
      {suggestions.map(s => (
        <div key={s.query} onClick={() => setQuery(s.query)}>
          {highlightMatch(s.query, query)}
        </div>
      ))}
    </div>
  );
}

// Debounce utility
function debounce(fn, delay) {
  let timer;
  return (...args) => {
    clearTimeout(timer);
    timer = setTimeout(() => fn(...args), delay);
  };
}

// Highlight matching prefix in suggestion
function highlightMatch(suggestion, query) {
  const index = suggestion.toLowerCase().indexOf(query.toLowerCase());
  if (index === -1) return suggestion;
  return (
    <span>
      {suggestion.slice(0, index)}
      <strong>{suggestion.slice(index, index + query.length)}</strong>
      {suggestion.slice(index + query.length)}
    </span>
  );
}

Debouncing reduces API calls by waiting until the user pauses typing. Only requests for prefixes with 2+ characters are sent. Highlighting the matched prefix improves the visual experience.

Key points

Concepts covered

Trie, Prefix Tree, Debouncing, Ranking, Redis