Katkat
Back

Implement a Stateful Search Autocomplete Session

PinterestMachine Learning Engineer · Technical Screen
HardMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

Design an interactive autocomplete system that tracks query frequencies, returns the top 3 ranking prefix matches per keystroke, and commits completed queries to dynamic history.

Problem Statement

Implement an autocomplete system for search queries that provides real-time query suggestions as a user types and updates historical sentence frequencies upon search completion.

Implement the AutocompleteSystem class:

  • AutocompleteSystem(sentences: list[str], times: list[int]): Initializes the system with historical sentences and their corresponding search frequencies times.
  • input(c: str) -> list[str]: Processes a single input character c from a continuous user typing session:
    • If c != '#': Append c to the current session's query buffer. Return the top 3 historical sentences that have the current buffer as a prefix. Rank sentences first by frequency in descending order; if frequencies are equal, rank them in lexicographical order (ASCII ascending). If fewer than 3 matches exist, return all matching sentences.
    • If c == '#': Marks the end of the query. If the current buffer is non-empty, record this sentence into history (incrementing its count by 1 if it already exists, or setting its count to 1 if new). Reset the session buffer to empty, and return an empty list [].

Example

autocomplete = AutocompleteSystem(
    ["pin", "pinterest", "pinecone", "pine"],
    [5, 3, 2, 2]
)

# User types 'p'
autocomplete.input('p')
# Returns: ["pin", "pinterest", "pine"]
# Explanation: "pine" and "pinecone" both have frequency 2, but "pine" is lexicographically smaller.

# User types 'i'
autocomplete.input('i')
# Returns: ["pin", "pinterest", "pine"]

# User types 'n'
autocomplete.input('n')
# Returns: ["pin", "pinterest", "pine"]

# User types 'e'
autocomplete.input('e')
# Returns: ["pinterest", "pine", "pinecone"]
# Explanation: "pin" no longer matches prefix "pine".

# User commits the search
autocomplete.input('#')
# Returns: []
# Query "pine" frequency is now updated from 2 to 3.

# New search session, user types 'p'
autocomplete.input('p')
# Returns: ["pin", "pine", "pinterest"]
# Explanation: "pine" and "pinterest" both have frequency 3, but "pine" < "pinterest" lexicographically.

Constraints

  • n == sentences.length == times.length, where 1 <= n <= 2000
  • 1 <= times[i] <= 100
  • 1 <= sentences[i].length <= 100
  • c is either a lowercase English letter 'a'-'z', a space ' ', or the delimiter '#'.
  • At most 20,000 calls will be made to input.

Hints

Hint 1

A Trie combined with a hash map mapping full sentences to their total frequencies allows efficient prefix navigation.

Hint 2

Keep a pointer to the current Trie node during typing so each keystroke takes O(1) step down the tree rather than re-traversing from root.

Hint 3

When updating a newly completed sentence on '#', ensure your data structures update without needing to reconstruct the entire Trie from scratch.

Follow-up questions

  • How would you optimize `input()` latency if the prefix has millions of matches and full traversal to collect top candidates is too slow?
  • How would you extend this design to incorporate recency (e.g., exponential time decay on counts) instead of unbounded historical frequency?
  • How would you adapt the prefix matching logic to tolerate typos (e.g., 1 edit distance)?