Search Autocomplete from a Timestamped Query Log, Ranked by Count with Tie-Breaks
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are building autocomplete for a search bar. You are given a log of past searches, each with the time it happened, and a list of autocomplete requests, each with the prefix the user has typed so far and the time it was typed. For each request, return up to `result_count` suggestions taken from the past searches.
### Function Signature
```python
def autocomplete(search_queries: list[str], search_timestamps: list[int], prefixes: list[str], prefix_timestamps: list[int], result_count: int) -> list[list[str]]:
```
- `search_queries[i]` is a query a user searched, and `search_timestamps[i]` is when it was searched.
- `prefixes[j]` is what the user had typed in autocomplete request `j`, and `prefix_timestamps[j]` is when it was typed.
- `result_count` is the maximum number of suggestions to return per request.
### Rules
- For request `j`, consider only the log entries that were searched at or before `prefix_timestamps[j]` and whose query starts with `prefixes[j]`. A query equal to the prefix counts.
- Each log entry is one search. Group the considered entries by query string and rank the distinct queries by:
1. search count, highest first;
2. the time the query was first searched (its smallest timestamp), earliest first, if counts tie;
3. alphabetical order, if both still tie. Queries contain only lowercase letters, so this is ordinary string order, in which a query comes before any longer query that starts with it (`"app"` before `"apple"`).
- The suggestions for request `j` are the first `result_count` queries of that ranking, or all of them if fewer match. A query appears at most once in a request's list.
- Return one list per request, in the same order as `prefixes`. If nothing matches, that request's list is empty.
- Requests only read the log: typing a prefix is not a search. Each request is answered independently, and requests need not be in time order.
- The log need not be sorted by time, and several entries can share a timestamp.
### Constraints
- `1 <= len(search_queries) == len(search_timestamps) <= 1000`
- `1 <= len(prefixes) == len(prefix_timestamps) <= 1000`
- Every query and every prefix has 1 to 20 characters, all lowercase English letters `a` to `z`
- `0 <= search_timestamps[i], prefix_timestamps[j] <= 10^9`
- `1 <= result_count <= 100`
### Examples
**Example 1**
```text
Input: search_queries = ["apple", "app", "apple", "apply", "banana", "app", "app"]
search_timestamps = [1, 2, 3, 4, 5, 6, 7]
prefixes = ["app", "app", "app", "b", "c"]
prefix_timestamps = [3, 6, 7, 5, 10]
result_count = 2
Output: [["apple", "app"], ["apple", "app"], ["app", "apple"], ["banana"], []]
```
- `"app"` at time 3: `"apple"` was searched 2 times and `"app"` 1 time.
- `"app"` at time 6: `"apple"` and `"app"` were each searched 2 times. `"apple"` was first searched earlier (time 1 against time 2), so it ranks first. `"apply"` was searched once and is cut off by `result_count`.
- `"app"` at time 7: `"app"` now has 3 searches, so it moves ahead of `"apple"`.
- `"b"` at time 5: only `"banana"` matches; its search at time 5 counts because the time bound is inclusive.
- `"c"` at time 10: nothing matches, so the list is empty.
**Example 2**
```text
Input: search_queries = ["cart", "cat", "car", "cat", "car"]
search_timestamps = [4, 2, 2, 8, 8]
prefixes = ["ca", "car", "ca"]
prefix_timestamps = [8, 8, 3]
result_count = 3
Output: [["car", "cat", "cart"], ["car", "cart"], ["car", "cat"]]
```
At time 8, `"car"` and `"cat"` each have 2 searches and were both first searched at time 2, so alphabetical order puts `"car"` first; `"cart"` has 1 search. For the prefix `"car"`, the query `"car"` itself matches and `"cat"` does not. At time 3, only the two searches at time 2 count, one each for `"cat"` and `"car"`, tied on count and on first search time.
**Example 3**
```text
Input: search_queries = ["go", "golf", "golf", "golf"]
search_timestamps = [1, 3, 4, 5]
prefixes = ["go", "go", "gol"]
prefix_timestamps = [3, 5, 2]
result_count = 1
Output: [["go"], ["golf"], []]
```
At time 3, `"go"` and `"golf"` each have one search, and `"go"` was searched first. By time 5, `"golf"` has 3 searches. At time 2, `"golf"` has not been searched yet, and `"go"` does not start with `"gol"`.
Overview: A search autocomplete problem: given a timestamped log of past searches and a list of typed prefixes with request times, return up to a fixed number of suggestions per request. It tests filtering by time and prefix, counting repeated queries, and a three-level ranking by search count, first search time and alphabetical order.
Read the full Roblox Software Engineer interview experience this question came from
You are building autocomplete for a search bar. You are given a log of past searches, each with the time it happened, and a list of autocomplete requests, each with the prefix the user has typed so far and the time it was typed. For each request, return up to `result_count` suggestions taken from the past searches.
Implement `autocomplete(search_queries, search_timestamps, prefixes, prefix_timestamps, result_count)`:
- `search_queries[i]` is a query a user searched, and `search_timestamps[i]` is when it was searched.
- `prefixes[j]` is what the user had typed in autocomplete request `j`, and `prefix_timestamps[j]` is when it was typed.
- `result_count` is the maximum number of suggestions to return per request.
### Rules
- For request `j`, consider only the log entries that were searched at or before `prefix_timestamps[j]` (the time bound is inclusive) and whose query starts with `prefixes[j]`. A query equal to the prefix counts.
- Each log entry is one search. Group the considered entries by query string and rank the distinct queries by:
1. search count, highest first;
2. if counts tie, the time the query was first searched (its smallest timestamp), earliest first;
3. if both still tie, alphabetical order. Queries contain only lowercase letters, so this is ordinary string order, in which a query comes before any longer query that starts with it (`"app"` before `"apple"`).
- The suggestions for request `j` are the first `result_count` queries of that ranking, or all of them if fewer match. A query appears at most once in a request's list.
- Return one list per request, in the same order as `prefixes`. If nothing matches, that request's list is empty.
- Requests only read the log: typing a prefix is not a search. Each request is answered independently, and requests need not be in time order.
- The log need not be sorted by time, and several entries can share a timestamp.
### Constraints
- `1 <= len(search_queries) == len(search_timestamps) <= 1000`
- `1 <= len(prefixes) == len(prefix_timestamps) <= 1000`
- Every query and every prefix has 1 to 20 characters, all lowercase English letters `a` to `z`
- `0 <= search_timestamps[i], prefix_timestamps[j] <= 10^9`
- `1 <= result_count <= 100`
No value can exceed 2^31 - 1: timestamps are at most 10^9 and a search count is at most 1000, so a 32-bit `int` is enough in Java and C++.
### Example 1
```text
Input: search_queries = ["apple", "app", "apple", "apply", "banana", "app", "app"]
search_timestamps = [1, 2, 3, 4, 5, 6, 7]
prefixes = ["app", "app", "app", "b", "c"]
prefix_timestamps = [3, 6, 7, 5, 10]
result_count = 2
Output: [["apple", "app"], ["apple", "app"], ["app", "apple"], ["banana"], []]
```
- `"app"` at time 3: `"apple"` was searched 2 times and `"app"` 1 time.
- `"app"` at time 6: `"apple"` and `"app"` were each searched 2 times. `"apple"` was first searched earlier (time 1 against time 2), so it ranks first. `"apply"` was searched once and is cut off by `result_count`.
- `"app"` at time 7: `"app"` now has 3 searches, so it moves ahead of `"apple"`.
- `"b"` at time 5: only `"banana"` matches; its search at time 5 counts because the time bound is inclusive.
- `"c"` at time 10: nothing matches, so the list is empty.
### Example 2
```text
Input: search_queries = ["cart", "cat", "car", "cat", "car"]
search_timestamps = [4, 2, 2, 8, 8]
prefixes = ["ca", "car", "ca"]
prefix_timestamps = [8, 8, 3]
result_count = 3
Output: [["car", "cat", "cart"], ["car", "cart"], ["car", "cat"]]
```
At time 8, `"car"` and `"cat"` each have 2 searches and were both first searched at time 2, so alphabetical order puts `"car"` first; `"cart"` has 1 search. For the prefix `"car"`, the query `"car"` itself matches and `"cat"` does not. At time 3, only the two searches at time 2 count, one each for `"cat"` and `"car"`, tied on count and on first search time.
Constraints
- 1 <= len(search_queries) == len(search_timestamps) <= 1000
- 1 <= len(prefixes) == len(prefix_timestamps) <= 1000
- Every query and every prefix has 1 to 20 characters, all lowercase English letters a to z
- 0 <= search_timestamps[i], prefix_timestamps[j] <= 10^9
- 1 <= result_count <= 100
Examples
Input: (['apple', 'app', 'apple', 'apply', 'banana', 'app', 'app'], [1, 2, 3, 4, 5, 6, 7], ['app', 'app', 'app', 'b', 'c'], [3, 6, 7, 5, 10], 2)
Expected Output: [['apple', 'app'], ['apple', 'app'], ['app', 'apple'], ['banana'], []]
Explanation: Source Example 1: count ranking, earliest-first-search tie-break, inclusive time bound at 5, and an unmatched prefix.
Input: (['cart', 'cat', 'car', 'cat', 'car'], [4, 2, 2, 8, 8], ['ca', 'car', 'ca'], [8, 8, 3], 3)
Expected Output: [['car', 'cat', 'cart'], ['car', 'cart'], ['car', 'cat']]
Explanation: Source Example 2: count and first-search ties fall back to string order; the query equal to the prefix 'car' matches.
Hints
- A log entry counts for a request only if its query starts with the typed prefix and its time is less than or equal to the request time; a query equal to the prefix counts too.
- For each matching query, two numbers over the counted entries decide its rank: how many entries there are and the smallest timestamp among them. The query text itself breaks any remaining tie.
- Requests never add searches to the log, so each request is answered from the original log alone, whatever order the requests arrive in.