Quick Overview

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.

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.

Overview: 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

  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.

Loading coding console...

Show the approach

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.