Search Suggestions System

Search Suggestions System

What is this problem about?

The Search Suggestions System interview question simulates a product search autocomplete feature. Given a list of product names and a search string typed character by character, return a list of up to 3 lexicographically smallest product suggestions after each character is typed. Only products that share a prefix with the typed string should appear. This combines prefix search with sorted retrieval.

Why is this asked in interviews?

Amazon, Google, Bloomberg, Adobe, Snap, Salesforce, and many others ask this problem because autocomplete is a real-world product feature present in every search bar. It evaluates whether candidates can use a Trie or binary search to efficiently find prefix matches, and how to limit results to the top 3. It tests string processing, sorted order maintenance, and the distinction between trie-based and sort-then-binary-search approaches.

Algorithmic pattern used

Two clean approaches: binary search on sorted array, and Trie. Binary search approach: sort the products array. For each prefix (each character typed), use binary search to find the leftmost product starting with the current prefix. Then collect up to 3 consecutive products from that position that still match the prefix. Trie approach: build a Trie where each node stores up to 3 lexicographically smallest words passing through it. For each prefix, traverse the Trie and return the stored suggestions.

Example explanation

Products: ["mobile", "mouse", "moneypot", "monitor", "mousepad"], searchWord = "mouse".

Sorted: ["mobile", "moneypot", "monitor", "mouse", "mousepad"].

• After "m": all 5 start with "m" → top 3: ["mobile", "moneypot", "monitor"].
• After "mo": ["mobile", "moneypot", "monitor"] → top 3: same.
• After "mou": ["mouse", "mousepad"] → ["mouse", "mousepad"].
• After "mous": ["mouse", "mousepad"].
• After "mouse": ["mouse", "mousepad"].

Common mistakes candidates make

• Not sorting products before binary search — the sorted order is required for both the prefix boundary search and lexicographic result ordering.
• Using startswith() in a linear scan for each prefix — O(n×m) is too slow; binary search gives O(m log n) for prefix boundaries.
• Off-by-one in the binary search range when collecting the next 3 matches.
• In the Trie approach, not limiting stored suggestions to 3 per node during insertion.

Interview preparation tip

For the Search Suggestions System coding problem, the Trie and binary search string interview pattern are both valid. For interviews at Amazon and Snap, the binary search approach is faster to implement: sort once, then bisect_left for each prefix. The Trie approach demonstrates architectural thinking preferred for system design follow-ups. Know both — interviewers at Deliveroo and J.P. Morgan may ask you to compare the two approaches for different scales of product lists.