Design Search Autocomplete System

HardDesigntrie

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Build the suggestion engine behind a search box. The system starts with historical data: sentences[i] has been typed times[i] times. That count is the sentence's *hotness*. - AutocompleteSystem(sentences, times) loads the history. - input(c) receives the next character the user typed. If c is '#', the current sentence is finished: add 1 to its hotness (adding it with hotness 1 if new), reset the typed text to empty, and return []. Otherwise append c to the typed text and return up to **3** historical sentences that start with the typed text. Suggestions are ordered by hotness, **highest first**. Equal hotness is broken by plain ASCII string order (so a space sorts before any letter and a prefix sorts before its extensions). If fewer than 3 sentences match, return all of them; if none match, return []. A sentence being typed only enters the history when # is pressed.

Examples

Input: ["AutocompleteSystem","input","input","input","input","input"] [[["cat","car","cart","dog"],[3,3,2,1]],["c"],["a"],["r"],["#"],["c"]]
Output: [null,["car","cat","cart"],["car","cat","cart"],["car","cart"],[],["car","cat","cart"]]
`car` and `cat` tie at 3 and `car` is smaller, then `cart` at 2. Typing `car` leaves only `car` and `cart`. Pressing `#` saves `car` (now 4 uses) and returns an empty list.
Input: ["AutocompleteSystem","input","input","input","input"] [[["hi you","hi"],[1,1]],["h"],["x"],["#"],["h"]]
Output: [null,["hi","hi you"],[],[],["hi","hi you","hx"]]
`hi` sorts before `hi you` because it is a prefix of it. No sentence starts with `hx`, but after `#` it is saved and shows up for the next `h`.

Constraints

  • `1 <= sentences.length <= 100`, `sentences.length == times.length`, and sentences are distinct.
  • `1 <= sentences[i].length <= 100`, `1 <= times[i] <= 50`
  • Sentences and typed characters are lowercase English letters or spaces; `c` may also be `'#'`.
  • `'#'` is never typed while the typed text is empty. At most 5000 calls to `input`.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More trie problems