Search Suggestions System

You're building the autocomplete box for a store. You have an array of distinct lowercase product names products and the word a shopper is typing, searchWord.

After the shopper types each character, show up to three product names that start with everything typed so far. If more than three products match, show the three that come first in alphabetical (lexicographic) order.

Return an array with one entry per character of searchWord. Entry i is the list of suggestions after the first i + 1 characters have been typed, in alphabetical order. If nothing matches, that entry is an empty list.

Once the products are sorted, every product that starts with a given prefix sits in one contiguous block, and that block begins exactly where the prefix itself would be inserted. So the three suggestions for a prefix are just the first three names at or after that insertion point, as long as they still start with the prefix.

That turns each keystroke into one binary search instead of a scan over every product. A trie gives the same answer by walking one node per character, but sorting plus binary search needs far less code and is what most interviewers expect first.

def suggested_products(products: list[str], search_word: str) -> list[list[str]]:
    products = sorted(products)
    result = []
    lo = 0
    prefix = ""
    for ch in search_word:
        prefix += ch
        lo = bisect.bisect_left(products, prefix, lo)
        result.append([p for p in products[lo:lo + 3] if p.startswith(prefix)])
    return result

function suggestedProducts(products, searchWord) {
  const sorted = [...products].sort();
  const result = [];
  let lo = 0;
  let prefix = '';
  for (const ch of searchWord) {
    prefix += ch;
    let left = lo;
    let right = sorted.length;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (sorted[mid] < prefix) left = mid + 1;
      else right = mid;
    }
    lo = left;
    result.push(
      sorted.slice(lo, lo + 3).filter((p) => p.startsWith(prefix))
    );
  }
  return result;
}

Say the key fact first: "after sorting, all names with the same prefix are adjacent, and the block starts at the prefix's insertion point." Once that lands, binary search is the obvious tool and the code is short.

Interviewers often ask about a trie because this looks like an autocomplete problem. It's worth explaining the trade-off: a trie answers each keystroke in O(1) after a heavier build, which matters when the catalog is fixed and queries are many, while the sorted array is simpler and lighter on memory.