Develop Auto-Complete System for Dish Suggestions

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.

Auto-Complete with Real-Time Updates

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

Examples

Example 1

Input: init = [("taco", 5), ("tart", 8), ("tea", 7)]\noperations = [["query", "ta", 2], ["add", "taco", 9], ["query", "ta", 3], ["add", "tag", 6], ["query", "ta", 3]]
Output: [["tart", "taco"], ["taco", "tart"], ["taco", "tart", "tag"]]

Explanation: Initially, for prefix "ta", the matches are tart(8), taco(5) -> ["tart", "taco"]. After updating taco to 9, top 3 for "ta" are taco(9), tart(8) -> ["taco", "tart"]. After adding tag(6), top 3 are taco(9), tart(8), tag(6) -> ["taco", "tart", "tag"].

Example 2

Input: init = [("app", 5), ("apple", 10), ("apricot", 10), ("app", 10)]\noperations = [["query", "ap", 2], ["add", "apricot", 11], ["query", "ap", 3], ["query", "b", 5], ["query", "ap", 0]]
Output: [["app", "apple"], ["apricot", "app", "apple"], [], []]

Explanation: Last occurrence in init sets app to 10. Query "ap", k=2 returns the two lexicographically smallest among equal scores: ["app", "apple"]. After apricot is updated to 11, top 3 are ["apricot", "app", "apple"]. No matches for prefix "b". k=0 returns an empty list.

Hints

1. Build a trie of dish names; maintain a separate hash map from dish to score for O(1) score updates.
2. For query(prefix, k), navigate to the trie node of the prefix, then traverse its subtree to find terminal words.
3. Rank candidates by (-score, name) to achieve score-desc, name-asc ordering.
4. To optimize, maintain a size-k min-heap during traversal to keep only the best k seen so far.
5. Ensure updates only change the score map; insert into the trie only when a new dish name appears.

Approach

Maintain a trie of dish names for fast prefix navigation and a hash map from dish to score for O(1) updates. Initialization inserts unique dishes (last score wins) into the trie. For add(dish, score), update the score map and only insert into the trie if the dish is new. For query(prefix, k), traverse the trie to the node matching the prefix; if it exists, perform a DFS to collect terminal words in that subtree. Build candidate pairs (score, word), sort by (-score, word), and return the first k names. This approach ensures correct ordering and immediate reflection of updates.

• Time complexity: Initialization: O(S) where S is total length of unique dish names. add: O(L) for new dish (L = length), O(1) for score update of existing dish. query: O(P + M log M), where P is prefix length and M is the number of matching dishes under the prefix.
• Space complexity: O(S + N), where S is total characters stored in the trie and N is the number of unique dishes for the score map.