Design an autocomplete system that, given a prefix typed by the user, returns the top 3 most frequently searched sentences that start with that prefix. The system should support recording new searches and querying for suggestions.
For example, if the history is ["i love you" (5 times), "island" (3 times), "i love coding" (2 times), "ironman" (1 time)], typing "i" should return ["i love you", "island", "i love coding"].
Explain your design and state the time and space complexity for each operation.
How to approach it
- Hint 1
Think about how a trie can store entire sentences and also track their frequency counts.
- Hint 2
Each trie node can store a hash map of all sentences that pass through it along with their frequencies. This precomputes suggestions at each node.
- Hint 3
When the user types a character, traverse one level in the trie and return the top 3 sentences by frequency from that node. On sentence completion, update frequencies along the path.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.