Time-Based Key-Value Map With Floor and Ceiling Queries
Character.AI● MediumFULLTIMEPHONE SCREENProblem statement
Process operations on a time-based key-value map. SET stores or replaces a value for a key at a timestamp and contributes null to the result. GET contributes the value at the greatest stored timestamp less than or equal to the query timestamp. CEIL contributes the value at the smallest stored timestamp greater than or equal to the query timestamp. A missing answer contributes the empty string.
SET timestamps may arrive out of order. When the same key and timestamp is set again, the latest value replaces the earlier one. Process operations in array order and return one result per operation.
Function
runVersionedMap(operations: String[], keys: String[], values: String[], timestamps: int[]) → String[]Examples
Example 1
operations = ["SET","SET","GET","CEIL"]keys = ["a","a","a","a"]values = ["late","early","",""]timestamps = [10,2,7,7]return = ["null","null","early","late"]The out-of-order writes are sorted by timestamp for both floor and ceiling lookup.
Example 2
operations = ["SET","SET","GET","CEIL","SET","GET"]keys = ["x","x","x","x","x","x"]values = ["old","new","","","replacement",""]timestamps = [5,9,4,6,5,5]return = ["null","null","","new","null","replacement"]Missing floor lookup is empty, ceiling finds timestamp 9, and a repeated timestamp is overwritten.
Constraints
1 <= operations.length <= 100000- All four input arrays have equal length.
- Each operation is
SET,GET, orCEIL. 1 <= timestamps[i] <= 10^9- Keys and SET values are nonempty strings of length at most 100.