Katkat
Back

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

GleanSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Return the top k suggestions whose ngram starts with a query and whose department matches the user, from a static list that already fills half of the server's memory. Tests prefix indexing, top-k extraction without scanning all matches, and explicit memory accounting against latency.

A service keeps a static list of suggestions. Each suggestion is a tuple (ngram: str, department: int, score: int). Implement

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.

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.

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

Hints

Hint 1

Keep only k at a time: You do not need to sort all matching suggestions to return the best k.

Hint 2

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.

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?