Serve Top-k Prefix Suggestions Filtered by Department Within a Tight Memory Budget

A service keeps a static list of suggestions. Each suggestion is a tuple `(ngram: str, department: int, score: int)`. Implement ```python getTopSuggestions(query: str, userDept: int, k: int) ``` which returns the top `k` valid suggestions, highest score first. A suggestion is valid for a request when `query` is a prefix of its `ngram` and its `department` equals `userDept`. The list is large: it already occupies about half of the server's memory. Serve these suggestions as quickly as possible, without blowing up the memory. ### Constraints and Clarifications - The list does not change while the service runs, so it may be preprocessed once at startup. - Return the ngrams of the chosen suggestions, or fewer than `k` of them if fewer are valid. ### Clarifying Questions - How should equal scores be ordered? - Roughly how many suggestions, departments and requests per second are there, and what is a typical `k`? - Can the same ngram appear more than once within one department, and should duplicates be returned? - Is an empty query allowed, meaning "the best `k` for my department"? - Does "without blowing up the memory" mean the index must stay well below the size of the list itself? ### Part 1 — A correct baseline Implement `getTopSuggestions` directly over the list and state its time and extra-memory cost per request. ```hint Keep only k at a time You do not need to sort all matching suggestions to return the best k. ``` #### What This Part Should Cover - Applying both filters, prefix and department, before ranking - Time per request and extra memory per request - A deterministic tie rule ### Part 2 — Fast queries within the memory budget Preprocess the list so that each request is fast, while the extra memory stays a small fraction of the list's own size. Compare your design with at least one alternative. ```hint What can be ordered Think about which part of the filter an ordered structure over the ngrams can resolve, and what each part of that structure would need to remember about scores. ``` #### What This Part Should Cover - An index that resolves the prefix and department filters without scanning the list - Extracting the best `k` without visiting every match - Memory per suggestion for the index, and why it does not copy the strings - Preprocessing and per-query complexity ### What a Strong Answer Covers - Tie rule, duplicates and empty-query behaviour clarified before coding - A correct baseline first, then an index whose cost is justified with numbers - Explicit memory accounting against the stated budget, not only big-O - The latency versus memory trade-off of caching per-prefix results - Edge cases: unknown department, `k` larger than the number of matches, `k = 0` ### Follow-up Questions - The list now changes a few times a day. How do you rebuild or update the index without doubling memory during the rebuild? - How would you cache the hottest prefixes, and what would that cost in memory? - How does your design change if one department holds most of the suggestions?