Roblox Coding Interview: Design Autocomplete System (Trie)

You will implement an interactive autocomplete/typeahead system that processes input one character at a time and returns up to k=3 historical sentences matching the current prefix.

Core task: build a class (e.g., AutocompleteSystem) initialized with a list of historical sentences and usage counts. As you receive non-terminating characters you must append them to the current prefix and return up to three suggestions sorted first by frequency (highest first) and then lexicographically for ties. When you receive '#', treat the current prefix as a completed sentence: add it to history or increment its count and reset the input prefix.

Flow / stages:

• Stage 1: implement query behavior for incremental input and prefix lookup (character-by-character API).
• Stage 2: persist updates when '#' is received so future queries reflect new frequencies.

Skill signals the interviewer expects:

• Data structures: Trie for efficient prefix search, and a min/max-heap or priority queue for top-k ranking.
• Correct tie-breaking (lexicographic) and stable ordering.
• Complexity reasoning: time/space trade-offs for insertion, search, and maintaining top-k priorities.

Practical tips: discuss how you store counts at trie nodes, how to collect candidate sentences efficiently, memory vs. speed trade-offs, and how to scale suggestions for large corpora.