Skip to main content

642. Design Search Autocomplete System

hardAsked at Pinterest

Pinterest's search bar autocompletes pins and boards as you type; this LeetCode design problem mirrors the production setup. Build a system that, given a stream of historical queries with hot-counts, returns the top-3 ranked completions for any prefix typed so far. Trie + heap is the canonical answer.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

  • Glassdoor (2026-Q1)— Pinterest search-team onsite reports cite Design Autocomplete as the data-structure design round for search-infra SWEs.
  • LeetCode Pinterest tag (2026-Q1)— Listed as a Pinterest-tagged problem; obvious analog to the Pinterest search-autocomplete product surface.

Problem

Design a search autocomplete system. Given an array of historical sentences and their respective frequencies, support: typing characters one at a time (input(c)) — for each new character, return the top-3 historically most-frequent sentences that have the current input as a prefix, ordered by frequency descending with ASCII ties broken in ascending lexicographic order. When the user types '#', the current input is committed as a new completed sentence (frequency += 1) and the buffer resets.

Constraints

  • n == sentences.length
  • n == times.length
  • 1 <= n <= 100
  • 1 <= sentences[i].length <= 100
  • 1 <= times[i] <= 50
  • c is lowercase English letter, a space, or '#'.
  • Each tested sentence will be a sequence of characters c that end with the character '#'.

Examples

Example 1

Input
AutocompleteSystem(['i love you', 'island', 'ironman', 'i love leetcode'], [5,3,2,2]); input('i'); input(' '); input('a'); input('#');
Output
[['i love you','island','i love leetcode'], ['i love you','i love leetcode'], [], []]

Explanation: After typing 'i', the three most-frequent prefix-matches are returned. After ' ', only the two i-space matches remain. After 'a' there's no match. '#' commits 'i a' as a new completion with count 1.

Approaches

1. Linear scan over all sentences (brute force)

Store sentences in a HashMap<sentence, count>. On every input character, walk every entry, filter by prefix, sort by (count DESC, lex ASC), take top-3.

Time
O(N * L + N log N) per input char where N = sentences and L = avg length
Space
O(N * L)
class AutocompleteSystemBrute {
  constructor(sentences, times) {
    this.counts = new Map();
    for (let i = 0; i < sentences.length; i++) this.counts.set(sentences[i], times[i]);
    this.buffer = '';
  }
  input(c) {
    if (c === '#') {
      this.counts.set(this.buffer, (this.counts.get(this.buffer) || 0) + 1);
      this.buffer = '';
      return [];
    }
    this.buffer += c;
    const matches = [];
    for (const [s, count] of this.counts.entries()) {
      if (s.startsWith(this.buffer)) matches.push([s, count]);
    }
    matches.sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0]));
    return matches.slice(0, 3).map(([s]) => s);
  }
}

Tradeoff: Correct and easy to write. Re-scans the full corpus on every keystroke — fine at LeetCode constraint sizes but no signal at Pinterest. Anchor with this, then move to the trie.

2. Trie + per-node hot-completion cache (optimal)

Build a trie keyed by character. Each node stores the count of any sentence ending at it AND a cached list of (sentence, count) pairs reachable from it. On insert, propagate updates. On input, walk to the prefix node, return the top-3 from its cache.

Time
O(L) per character (constant per keystroke for fixed top-K)
Space
O(N * L)
class TrieNode {
  constructor() {
    this.children = new Map();
    this.counts = new Map(); // sentence -> count for sentences passing through this node
  }
}

class AutocompleteSystem {
  constructor(sentences, times) {
    this.root = new TrieNode();
    this.buffer = '';
    this.cur = this.root;
    this.broken = false;
    for (let i = 0; i < sentences.length; i++) this._insert(sentences[i], times[i]);
  }
  _insert(sentence, count) {
    let node = this.root;
    for (const ch of sentence) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
      node.counts.set(sentence, (node.counts.get(sentence) || 0) + count);
    }
  }
  input(c) {
    if (c === '#') {
      this._insert(this.buffer, 1);
      this.buffer = '';
      this.cur = this.root;
      this.broken = false;
      return [];
    }
    this.buffer += c;
    if (this.broken) return [];
    if (!this.cur.children.has(c)) {
      this.broken = true;
      this.cur = null;
      return [];
    }
    this.cur = this.cur.children.get(c);
    const entries = [...this.cur.counts.entries()];
    entries.sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0]));
    return entries.slice(0, 3).map(([s]) => s);
  }
}

Tradeoff: Per-keystroke cost is bounded by trie depth and top-K. Memory cost: every sentence's counts entry sits on every node along its path, which is O(sentence-length) duplication — production Pinterest mitigates with sharded tries and per-shard top-K materialization.

Pinterest-specific tips

Pinterest search-team interviewers grade four signals: (1) you reach for a trie immediately on a prefix-search problem; (2) you understand the cache-the-top-K-at-each-node tradeoff (we trade memory for keystroke latency); (3) you handle the '#' commit AND the broken-prefix branch where the user types past any match; (4) you mention that production replaces the in-node sort with a maintained top-3 heap on insert. The fourth point is the senior-IC differentiator.

Common mistakes

  • Not handling the broken-prefix branch — once the user has typed a character with no match, every subsequent input returns [] until '#'.
  • Treating the '#' input as just-reset — forgetting to commit the buffer as a new sentence with count 1.
  • Sorting at every keystroke when the spec says top-3 (use a fixed-size heap to amortize).
  • Tie-breaking on count alone — the rubric requires ASCII-ascending tiebreak when counts are equal.

Follow-up questions

An interviewer at Pinterest may pivot to one of these next:

  • Make insert O(L) instead of O(L^2) by maintaining a top-3 heap at each node directly.
  • Add fuzzy / typo-tolerant matching (edit-distance-1 candidates).
  • Distributed autocomplete across N search shards.
  • Personalized autocomplete: re-rank by per-user history.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the trie better than a hash map of sentences?

Hash-map prefix queries are O(N * L) per keystroke. The trie reduces it to O(L) by sharing the prefix walk across all matching completions and pre-computing the top-K per node.

Does Pinterest expect me to implement my own trie?

Yes — there's no built-in trie in JavaScript. Implement it inline with new TrieNode and a Map for children; that's the standard.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Design Search Autocomplete System and other Pinterest interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →