Search Suggestions System (Autocomplete)

📋

Search Suggestions System (Autocomplete)

Edge cases:

</>

IDE

def suggestedProducts(products: List[str], searchWord: str) -> List[List[str]]:public List<List<String>> suggestedProducts(List<String> products, String searchWord)vector<vector<string>> suggestedProducts(vector<string> &products, string searchWord)function suggestedProducts(products, searchWord)

def suggestedProducts(products, searchWord):
    # Write your solution here
    pass

class Solution {
    public List<List<String>> suggestedProducts(List<String> products, String searchWord) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
#include <string>
using namespace std;

vector<vector<string>> suggestedProducts(vector<string> &products, string searchWord) {
    // Write your solution here
    return {};
}

function suggestedProducts(products, searchWord) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [['mouse', 'mousepad'], ['mouse', 'mousepad'], ['mouse', 'mousepad'], ['mouse', 'mousepad'], ['mouse', 'mousepad']]Not sorting products lexicographically before filtering, causing incorrect suggestion order.✅ Sort products array before processing prefixes: products.sort()

Wrong: [[], [], []]Returning empty suggestions prematurely when products exist but prefix filtering is incorrect.✅ Ensure prefix filtering is done correctly for each prefix and suggestions collected accordingly.

Wrong: [['app'], ['app'], ['app']]Not including duplicates or limiting suggestions to fewer than three when more exist.✅ Do not remove duplicates; return up to three suggestions including duplicates.

Wrong: Timeout or no outputBrute force approach checking all products for each prefix causing TLE.✅ Implement trie data structure with precomputed top 3 suggestions per node for efficient queries.

✓

Test Cases

Try testing your solution with empty and minimal inputs to ensure robustness.

Consider tricky cases with duplicates and no matching prefixes to catch subtle bugs.

Think about the time complexity of your approach and how to optimize prefix searches.

t1_01basic

Input{"products":["mobile","mouse","moneypot","monitor","mousepad"],"searchWord":"mouse"}

Expected[["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]

⏱ Performance - must finish in 2000ms

After typing 'm', suggestions are the three lex smallest products starting with 'm'. After 'mo', same. After 'mou', only 'mouse' and 'mousepad' match, so they are suggested, and so on.

💡 Consider sorting products lexicographically to simplify prefix matching.

💡 Use prefix matching for each character typed and collect up to three matches.

💡 Maintain a running prefix and filter products starting with it, stopping after three suggestions.

Why it failed: Failed to produce correct suggestions for each prefix; likely missing lexicographic sorting or incorrect prefix filtering. Fix by sorting products first and filtering by prefix for each character typed.

✓ Correctly returns top 3 lexicographically smallest suggestions for each prefix.

t1_02basic

Input{"products":["apple","app","apricot","banana","bat","batch"],"searchWord":"bat"}

Expected[["banana","bat","batch"],["bat","batch"],["bat","batch"]]

⏱ Performance - must finish in 2000ms

For prefix 'b', suggestions are the three lex smallest products starting with 'b'. For 'ba', 'bat' and 'batch' match. For 'bat', only 'bat' and 'batch' match, so both are suggested.

💡 Sort products to get lex order before filtering.

💡 Check prefix matches for each character typed in searchWord.

💡 Return up to three matches per prefix, even if fewer exist.

Why it failed: Incorrect suggestions for prefixes starting with 'b'; likely not filtering prefixes correctly or not limiting to three suggestions. Fix by filtering products by prefix and limiting output to three items.

✓ Correctly returns top 3 lexicographically smallest suggestions for each prefix.

t2_01edge

Input{"products":[],"searchWord":"abc"}

Expected[[],[],[]]

⏱ Performance - must finish in 2000ms

Empty products array means no suggestions for any prefix of searchWord.

💡 What happens if products list is empty? No suggestions can be made.

💡 Ensure your code handles empty input gracefully without errors.

💡 Return empty lists for each prefix of searchWord when products is empty.

Why it failed: Code crashes or returns non-empty suggestions when products is empty. Fix by adding a check for empty products and returning empty lists accordingly.

✓ Handles empty products input correctly by returning empty suggestions for all prefixes.

t2_02edge

Input{"products":["a"],"searchWord":"a"}

Expected[["a"]]

⏱ Performance - must finish in 2000ms

Single product and single character searchWord; suggestion is the product itself.

💡 Test with minimal input sizes: one product and one character searchWord.

💡 Check that your code returns the product if it matches the prefix.

💡 Ensure no indexing errors occur with single-element inputs.

Why it failed: Fails to return the single product suggestion for single character searchWord. Fix by correctly handling single-element arrays and prefixes.

✓ Correctly returns the single product suggestion for single character searchWord.

t2_03edge

Input{"products":["abc","abcd","abcde"],"searchWord":"abcde"}

Expected[["abc","abcd","abcde"],["abc","abcd","abcde"],["abc","abcd","abcde"],["abcd","abcde"],["abcde"]]

⏱ Performance - must finish in 2000ms

Prefixes exactly match products; suggestions shrink as prefix length increases.

💡 Check behavior when searchWord prefixes exactly match product names.

💡 Suggestions should include all matching products up to three.

💡 As prefix length grows, fewer products match, so suggestions shrink.

Why it failed: Fails to reduce suggestions as prefix length increases or includes non-matching products. Fix by filtering products strictly by current prefix at each step.

✓ Correctly filters suggestions as prefix length increases.

t2_04edge

Input{"products":["aaa","aaa","aaa"],"searchWord":"aa"}

Expected[["aaa","aaa","aaa"],["aaa","aaa","aaa"]]

⏱ Performance - must finish in 2000ms

All products identical; suggestions include duplicates as they appear.

💡 Check if duplicates are preserved in suggestions.

💡 Sorting should keep duplicates and suggestions may include them.

💡 Ensure prefix filtering does not remove duplicates unintentionally.

Why it failed: Code removes duplicates or returns fewer than three suggestions incorrectly. Fix by not deduplicating products and returning up to three matches including duplicates.

✓ Correctly includes duplicates in suggestions as per input.

t3_01corner

Input{"products":["a","aa","aaa","aaaa"],"searchWord":"aaaa"}

Expected[["a","aa","aaa"],["aa","aaa","aaaa"],["aaa","aaaa"],["aaaa"]]

⏱ Performance - must finish in 2000ms

Tests correct handling of duplicates and overlapping prefixes with multiple similar products.

💡 Beware of greedy approaches that pick first three products without sorting.

💡 Sorting lex order is crucial to get correct top 3 suggestions.

💡 Ensure prefix filtering is done at each character, not just once.

Why it failed: Greedy approach fails by not sorting or filtering properly, leading to wrong suggestions. Fix by sorting products lexicographically and filtering by prefix at each step.

✓ Correctly returns lexicographically smallest suggestions for each prefix.

t3_02corner

Input{"products":["dog","deer","deal"],"searchWord":"cat"}

Expected[[],[],[]]

⏱ Performance - must finish in 2000ms

searchWord characters not present in any product; suggestions empty from first character.

💡 Check what happens when no products match the prefix at any step.

💡 Your code should return empty lists once no matches remain.

💡 Avoid continuing to search products after no matches found.

Why it failed: Code returns non-empty suggestions or crashes when no products match prefix. Fix by stopping search and returning empty lists once no matches found.

✓ Correctly returns empty suggestions when no products match prefix.

t3_03corner

Input{"products":["apple","apple","apple","app"],"searchWord":"app"}

Expected[["app","apple","apple"],["app","apple","apple"],["app","apple","apple"]]

⏱ Performance - must finish in 2000ms

Products contain duplicates; suggestions include duplicates as they appear in sorted order.

💡 Check if duplicates in products are handled correctly.

💡 Sorting should keep duplicates and suggestions may include them.

💡 Ensure prefix filtering does not remove duplicates unintentionally.

Why it failed: Code removes duplicates or returns fewer than three suggestions incorrectly. Fix by not deduplicating products and returning up to three matches including duplicates.

✓ Correctly includes duplicates in suggestions as per input.

t4_01performance

Input{"products":["aaaaaaaaaab0","aaaaaaaaaab1","aaaaaaaaaab2","aaaaaaaaaab3","aaaaaaaaaab4","aaaaaaaaaab5","aaaaaaaaaab6","aaaaaaaaaab7","aaaaaaaaaab8","aaaaaaaaaab9","aaaaaaaaaab10","aaaaaaaaaab11","aaaaaaaaaab12","aaaaaaaaaab13","aaaaaaaaaab14","aaaaaaaaaab15","aaaaaaaaaab16","aaaaaaaaaab17","aaaaaaaaaab18","aaaaaaaaaab19","aaaaaaaaaab20","aaaaaaaaaab21","aaaaaaaaaab22","aaaaaaaaaab23","aaaaaaaaaab24","aaaaaaaaaab25","aaaaaaaaaab26","aaaaaaaaaab27","aaaaaaaaaab28","aaaaaaaaaab29","aaaaaaaaaab30","aaaaaaaaaab31","aaaaaaaaaab32","aaaaaaaaaab33","aaaaaaaaaab34","aaaaaaaaaab35","aaaaaaaaaab36","aaaaaaaaaab37","aaaaaaaaaab38","aaaaaaaaaab39","aaaaaaaaaab40","aaaaaaaaaab41","aaaaaaaaaab42","aaaaaaaaaab43","aaaaaaaaaab44","aaaaaaaaaab45","aaaaaaaaaab46","aaaaaaaaaab47","aaaaaaaaaab48","aaaaaaaaaab49","aaaaaaaaaab50","aaaaaaaaaab51","aaaaaaaaaab52","aaaaaaaaaab53","aaaaaaaaaab54","aaaaaaaaaab55","aaaaaaaaaab56","aaaaaaaaaab57","aaaaaaaaaab58","aaaaaaaaaab59","aaaaaaaaaab60","aaaaaaaaaab61","aaaaaaaaaab62","aaaaaaaaaab63","aaaaaaaaaab64","aaaaaaaaaab65","aaaaaaaaaab66","aaaaaaaaaab67","aaaaaaaaaab68","aaaaaaaaaab69","aaaaaaaaaab70","aaaaaaaaaab71","aaaaaaaaaab72","aaaaaaaaaab73","aaaaaaaaaab74","aaaaaaaaaab75","aaaaaaaaaab76","aaaaaaaaaab77","aaaaaaaaaab78","aaaaaaaaaab79","aaaaaaaaaab80","aaaaaaaaaab81","aaaaaaaaaab82","aaaaaaaaaab83","aaaaaaaaaab84","aaaaaaaaaab85","aaaaaaaaaab86","aaaaaaaaaab87","aaaaaaaaaab88","aaaaaaaaaab89","aaaaaaaaaab90","aaaaaaaaaab91","aaaaaaaaaab92","aaaaaaaaaab93","aaaaaaaaaab94","aaaaaaaaaab95","aaaaaaaaaab96","aaaaaaaaaab97","aaaaaaaaaab98","aaaaaaaaaab99"],"searchWord":"aaaaaaaaaab"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 products each length ~11, searchWord length=11; O(n*k + m) expected to complete within 2s.

💡 Naive brute force checking all products for each prefix will time out.

💡 Use a trie to store products and collect top 3 suggestions efficiently.

💡 Precompute suggestions at each trie node to achieve O(m) query time.

Why it failed: TLE due to O(m*n*k) brute force approach. Fix by implementing trie with DFS to collect top 3 suggestions per prefix.

✓ Efficient trie-based solution passes within time limit.

Practice

1. Consider the following Python code snippet implementing the Trie + DFS approach for palindrome pairs. Given the input words = ["bat", "tab", "cat"], what is the final output of palindromePairs(words)?

easy

A. [[0, 1], [1, 0]]

B. [[1, 0], [0, 1]]

C. [[0, 1], [1, 0], [2, 2]]

D. []

Solution

1. Step 1: Trace add_word for "bat" and "tab"

   Words are added reversed: "tab" for "bat", "bat" for "tab". Palindrome suffixes recorded accordingly.

2. Step 2: Trace search for "bat" (index 0)

   Matches "tab" reversed in trie, finds palindrome suffixes leading to pair [0,1]. Similarly for "tab" (index 1) finds [1,0]. "cat" has no pairs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected palindrome pairs [OK]

Hint: Pairs are symmetric for "bat" and "tab" only [OK]

Common Mistakes:

• Confusing order of pairs
• Including self-pairs
• Missing palindrome suffix checks

2. Consider the following buggy Trie insert method. Which line contains the subtle bug that causes search to fail for inserted words?

medium

A. Line where node = self.root is assigned

B. Line where node = node.children[ch] is assigned inside the loop

C. Line where isEnd flag should be set but is missing

D. Line where the if condition checks if ch not in node.children

Solution

1. Step 1: Identify missing isEnd flag set

   After inserting all characters, isEnd must be set true to mark word end. This line is missing.

2. Step 2: Understand impact on search

   Without isEnd=true, search returns false even if path exists, because node.isEnd remains false.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing isEnd assignment causes search failure for inserted words [OK]

Hint: isEnd must be set after inserting entire word [OK]

Common Mistakes:

• Forgetting to mark isEnd after insertion

3. What is the time complexity of the optimal bitwise trie approach to find the maximum XOR of two numbers in an array of size n, assuming 32-bit integers?

medium

A. O(n^2)

B. O(n * log n)

C. O(32^2 * n)

D. O(n * 32)

Solution

1. Step 1: Identify loops in the algorithm

   We insert each of the n numbers into the trie, iterating over 32 bits each time -> O(n * 32).

2. Step 2: Find max XOR by traversing trie for each number

   Again, for each number, we traverse 32 bits -> O(n * 32).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   32 is constant, so complexity is linear in n times 32 bits [OK]

Hint: Each number processed over fixed 32 bits [OK]

Common Mistakes:

• Mistaking complexity as O(n^2) due to pairwise XOR

4. Examine the following buggy code snippet for palindrome pairs using Trie + DFS. Which line contains the subtle bug that causes missing pairs involving empty strings?

medium

A. No special handling for empty string in add_word or search

B. Line checking is_palindrome(word[:len(word)-i]) in add_word

C. Line checking if node.index >= 0 and node.index != index in search

D. Line setting node.index = index after insertion

Solution

1. Step 1: Identify empty string edge case

   Empty string pairs with palindromes require special handling to add pairs involving empty string indices.

2. Step 2: Check code for empty string handling

   Neither add_word nor search explicitly handle empty string cases, causing missing pairs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Empty string handling is a known subtle bug [OK]

Hint: Empty string pairs require explicit checks [OK]

Common Mistakes:

• Assuming palindrome checks cover empty strings
• Missing empty string special case
• Confusing index assignments

5. What is the time complexity of processing Q queries using the optimal StreamChecker approach that builds a trie of reversed words and maintains a stream buffer limited to the maximum word length L? Assume W words with maximum length L. Choose the most accurate complexity.

medium

A. O(Q * W * L)

B. O(Q * L^2)

C. O(Q * L)

D. O(Q + W * L)

Solution

1. Step 1: Identify operations per query

   Each query appends a letter and traverses at most L nodes in the trie (limited by max word length).

2. Step 2: Calculate total complexity

   Building the trie takes O(W * L) once. Each query takes O(L) time. Total is O(Q * L) for queries plus O(W * L) for setup, dominated by O(Q * L) for large Q.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Traversal limited to max word length L per query [OK]

Hint: Traversal limited to max word length L per query [OK]

Common Mistakes:

• Confusing brute force O(Q*W*L) with trie approach
• Assuming quadratic in L
• Ignoring trie build cost