Design time-based key-value store
Company: Navan
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Quick Answer: This question evaluates competency in designing time-indexed in-memory key-value stores, including handling ordered timestamps and achieving efficient lookups through suitable data structures and algorithms.
Constraints
- Set timestamps for the same key are non-decreasing
Examples
Input: ((('set', 'room', 'A', 10), ('set', 'room', 'B', 20), ('get', 'room', 5), ('get', 'room', 10), ('get', 'room', 15), ('get', 'room', 25)),)
Expected Output: ['', 'A', 'A', 'B']
Explanation: Prompt example.
Input: ((('get', 'x', 1),),)
Expected Output: ['']
Explanation: Missing key.
Input: ((('set', 'k', 'a', 1), ('set', 'k', 'b', 1), ('get', 'k', 1)),)
Expected Output: ['b']
Explanation: Same timestamp returns latest inserted by tuple order/value semantics.
Hints
- Store sorted timestamp/value pairs per key and binary-search on get.