Search Suggestions System

MediumStringsbinary search

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are building autocomplete. You have a list of distinct product names products and a searchWord that the user types one character at a time. After each typed character (so for each prefix of searchWord of length 1 through searchWord.length), suggest up to **three** products that start with that prefix. If more than three match, choose the three that come first in lexicographical order. Return a list with one entry per typed character, where each entry is the suggestions for that prefix sorted lexicographically (an empty list if nothing matches).

Examples

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Prefixes "m" and "mo" match all five, so the three smallest are shown; from "mou" onward only mouse and mousepad match.
Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]
No product starts with "t", so every entry is empty.

Constraints

  • 1 <= products.length <= 1000
  • 1 <= products[i].length <= 3000
  • 1 <= sum(products[i].length) <= 2 * 10^4
  • all products are distinct
  • 1 <= searchWord.length <= 1000
  • all strings consist of lowercase English letters

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More binary search problems