Develop Auto-Complete System for Dish Suggestions
Company: Pinterest
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
Search-as-you-type needs dish suggestions with popularity scores.
##### Question
Build an auto-complete system using the given (string, score) tuples. Given a prefix query, return top suggestions, supporting real-time updates.
##### Hints
Store tokens in a trie with max-heap of top scores at each node; DFS to collect results.
Quick Answer: This question evaluates a candidate's competency in building efficient auto-complete systems, covering prefix-based search, string processing, ranking by popularity, and handling real-time updates and performance trade-offs.
You are given an initial list of (dish, score) pairs and a sequence of operations. Implement an auto-complete system that supports: (1) add(dish, score): insert a new dish or update its score; (2) query(prefix, k): return up to k dish names that start with prefix, ordered by higher score first and, for ties, lexicographically smaller name first. Return a list of results for all query operations in order. Dishes and prefixes consist of lowercase English letters. If a dish appears multiple times in the initial list, the last occurrence determines its initial score.
Constraints
- 0 <= len(init) <= 50000
- 0 <= len(operations) <= 50000
- Dish names and prefixes use lowercase letters 'a'-'z' only
- 1 <= len(dish) <= 60
- 0 <= score <= 1e9
- For any query, 0 <= k <= 1000
- If fewer than k matches exist, return all matches
- Results are ordered by score descending, then name ascending
- Updates take effect immediately for subsequent queries
- If a dish appears multiple times in init, the last score wins
Hints
- Build a trie of dish names; maintain a separate hash map from dish to score for O(1) score updates.
- For query(prefix, k), navigate to the trie node of the prefix, then traverse its subtree to find terminal words.
- Rank candidates by (-score, name) to achieve score-desc, name-asc ordering.
- To optimize, maintain a size-k min-heap during traversal to keep only the best k seen so far.
- Ensure updates only change the score map; insert into the trie only when a new dish name appears.