Time-Aware Search Autocomplete
Roblox● MediumFULLTIMEPHONE SCREENProblem statement
A search log contains searchQueries[i] searched at integer time searchTimestamps[i]. Answer each prefix request j using only log entries whose timestamp is at most prefixTimestamps[j].
A query matches when it starts with prefixes[j]; the query may equal the prefix. Rank the distinct matching queries by:
- Higher number of eligible log occurrences first.
- For equal counts, smaller earliest eligible search timestamp first.
- For remaining ties, alphabetical order.
Return up to resultCount query strings for each request, in that ranking order. Keep the outer results in the original request input order. Return an empty inner list when no query matches or when resultCount is zero.
Practice input conventions
The two search arrays have equal length, as do the two request arrays. Every log entry counts, including equal word/timestamp pairs. Either timestamp array may be unsorted; equal times are valid. Search words use lowercase English letters and are nonempty. Prefixes use the same alphabet and may be empty, which matches every word. Do not change any input array or normalize text. Empty logs and empty request lists are valid.
This is an as-of-time query, not an all-time autocomplete: later searches can change frequencies and therefore the ranking for a later request with the same prefix.
Function
autocompleteAsOf(searchQueries: String[], searchTimestamps: int[], prefixes: String[], prefixTimestamps: int[], resultCount: int) → List<List<String>>Examples
Example 1
searchQueries = ["apple","app","apple","apply","banana","app","app"]searchTimestamps = [1,2,3,4,5,6,7]prefixes = ["app","app","app","b","c"]prefixTimestamps = [3,6,7,5,10]resultCount = 2return = [["apple","app"],["apple","app"],["app","apple"],["banana"],[]]This is the reported five-request example. At time3 apple has two searches and app has one. At time6 both have two, so apple wins by its earlier first search. At time7 app has three searches and ranks first. The final two requests return banana and no match.
Example 2
searchQueries = ["app","apple","app","apple"]searchTimestamps = [9,1,1,3]prefixes = ["app","app","app","app"]prefixTimestamps = [9,0,3,1]resultCount = 1return = [["app"],[],["apple"],["app"]]Requests stay in the supplied order, not chronological order. At time9 both words have count2 and earliest time1, so app wins alphabetically. Nothing has happened by time0; apple wins by frequency at time3; at time1 the tied counts and earliest times select app.
Example 3
searchQueries = ["zebra","apple","zebra","apple","alpha","alpha"]searchTimestamps = [1,2,3,4,2,4]prefixes = ["","a","z","x"]prefixTimestamps = [4,4,4,4]resultCount = 2return = [["zebra","alpha"],["alpha","apple"],["zebra"],[]]All three words have count2. Zebra ranks first because its earliest search is at time1. Alpha precedes apple after their equal earliest time2. The empty prefix matches all words; each other prefix still filters before ranking.
Constraints
0 <= searchQueries.length = searchTimestamps.length <= 1000.0 <= prefixes.length = prefixTimestamps.length <= 50.- Every search word has length between
1and30; every prefix has length between0and30. All characters are lowercase English letters. 0 <= searchTimestamps[i], prefixTimestamps[j] <= 1000000000.0 <= resultCount <= 20.- Inputs satisfy the parallel-array contract and must remain unchanged.