Quick Overview

Generate up to three lexicographically smallest product suggestions for every prefix of a search word, with efficient handling once a prefix has no matches.

Generate Prefix-Based Product Suggestions

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem Given distinct lowercase product names and a lowercase search word, return suggestions after each typed character. For every non-empty prefix, return up to three lexicographically smallest products that start with that prefix. ### Function Contract Implement `suggested_products(products, search_word) -> list[list[str]]`. ### Constraints - `1 <= len(products) <= 50000` and each product length is between 1 and 100. - `1 <= len(search_word) <= 100`. - All strings contain only lowercase English letters. - Products are distinct; the input order does not determine suggestion order. ### Examples - Products `["mobile","mouse","moneypot","monitor","mousepad"]` and search word `"mouse"` produce the standard prefix lists beginning with `["mobile","moneypot","monitor"]` for `m` and `mo`. - Once a prefix has no matches, that and all longer prefix lists are empty. ```hint Limit work per trie node If using a trie, each node needs only its three smallest suggestions, not every product below it. ``` ```hint Sorted ranges also work After sorting products, maintain the lower and upper indices whose strings still match the current prefix. ``` ### Edge Cases - Fewer than three matches are returned without padding. - A product equal to the current prefix is a valid suggestion. - The first character may have no matching product.

Overview: Generate up to three lexicographically smallest product suggestions for every prefix of a search word, with efficient handling once a prefix has no matches.

Read the full Citadel Software Engineer interview experience this question came from

Given distinct lowercase product names and a lowercase search word, return one suggestion list after every typed character. For each nonempty prefix of the search word, return up to three lexicographically smallest products that start with that prefix. Input order does not determine suggestion order. If fewer than three products match, return all matches without padding; a product equal to the prefix is a match. Once a prefix has no matches, it and all longer prefix lists are empty.

Constraints

  • 1 <= len(products) <= 50000.
  • Every product has length from 1 through 100, and product names are distinct.
  • 1 <= len(search_word) <= 100.
  • All product names and the search word contain only lowercase English letters.
  • Return at most three suggestions for every nonempty search prefix.

Examples

Input: (['mobile', 'mouse', 'moneypot', 'monitor', 'mousepad'], 'mouse')

Expected Output: [['mobile', 'moneypot', 'monitor'], ['mobile', 'moneypot', 'monitor'], ['mouse', 'mousepad'], ['mouse', 'mousepad'], ['mouse', 'mousepad']]

Explanation: This is the source example; each successive prefix narrows the sorted matching range.

Input: (['apple', 'banana'], 'cat')

Expected Output: [[], [], []]

Explanation: No product matches the first prefix, so all longer prefix results are empty.

Hints

  1. Sorting makes every prefix's matches a contiguous range.
  2. Binary-search the range boundaries, then take only its first three entries.

Loading coding console...

Show the approach

Approach

Sort a copy of the product names. For each growing search prefix, binary-search the first product not less than the prefix and the first product not less than prefix followed by '{'. Because all names contain only lowercase letters and '{' follows 'z', that half-open range contains exactly the products starting with the prefix. The first at most three entries in the sorted range are the required lexicographically smallest suggestions. The original products array is not modified.

Time complexity:
O(p log p + L log p), excluding string-comparison cost, where p is the number of products and L is the search-word length.
Space complexity:
O(p + L) beyond the returned suggestions for the sorted copy and growing prefix.