Search Suggestions System
Recognize the pattern
Brute force idea
If you approach Search Suggestions System in the most literal way possible, you get this: For each prefix, filter and sort all products. Re-filters everything for every keystroke. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
Better approach
A calmer way to see Search Suggestions System is this: Sort products, then build a trie. At each node, store references to up to 3 matching products. As the user types each character, walk one node deeper and return that node's suggestions. build, per character lookup. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Key invariant
The truth you want to protect throughout Search Suggestions System is this: By sorting products lexicographically before building the trie, the first 3 products reaching each node are automatically the lexicographically smallest. No sorting needed at query time. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Watch out for
One easy way to drift off course in Search Suggestions System is this: Storing all matching products at each node — only keep the first 3 to avoid memory waste. Since products are pre-sorted, the first 3 encountered during trie construction are the top 3. The fix is usually to return to the meaning of each move, not just the steps themselves.