Closest-Timestamp Key-Value Queries
Learn this problem
GoogleFULLTIMEPHONE SCREENProblem statement
You receive timestamped key-value entries through parallel arrays. Entry i stores entryValues[i] for entryKeys[i] at entryTimes[i]. For each individual key, its timestamps appear in strictly increasing order, although entries for different keys may be interleaved.
For every pair (queryKeys[i], queryTimes[i]), return the value stored for that key at the timestamp closest to the query time. If the closest timestamps on the two sides are equally far away, choose the earlier timestamp. Return the empty string when the key has no stored entry.
Function
closestValues(entryKeys: String[], entryTimes: int[], entryValues: String[], queryKeys: String[], queryTimes: int[]) → String[]Examples
Example 1
entryKeys = ["a","b","a","a","b"]entryTimes = [1,2,5,9,8]entryValues = ["one","bee2","five","nine","bee8"]queryKeys = ["a","a","b","c"]queryTimes = [7,3,6,4]return = ["five","one","bee8",""]For key a, time 7 ties between 5 and 9, so time 5 wins. Time 3 is closer to 1 than 5. For key b, time 8 is closer than 2. Key c is absent.
Example 2
entryKeys = ["x","x"]entryTimes = [10,20]entryValues = ["old","new"]queryKeys = ["x","x"]queryTimes = [5,25]return = ["old","new"]A query before all entries chooses the first timestamp, and a query after all entries chooses the last timestamp.
Constraints
0 <= entryKeys.length <= 200000entryKeys.length == entryTimes.length == entryValues.length1 <= queryKeys.length == queryTimes.length <= 200000- Keys and values contain
1to40printable ASCII characters. 0 <= entryTimes[i], queryTimes[i] <= 1000000000.- For each key, entry timestamps are strictly increasing in encounter order.