Quick Overview

This question evaluates understanding of time-versioned key-value stores, monotonic timestamp assignment, clock skew handling, concurrent writes, appropriate data structures, and time/space complexity analysis.

Design time-versioned KV without timestamp argument

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design a time-versioned key-value store that does not accept a timestamp argument on writes. Support set(key, value) which stores the value with an internally assigned, monotonically increasing timestamp, getLatest(key) which returns the most recent value, and getAtOrBefore(key, wallTime) which returns the value that was current at or before the given wall-clock time. Describe your data structures, how you ensure monotonicity despite clock issues, and the time/space complexity of operations.

Quick Answer: This question evaluates understanding of time-versioned key-value stores, monotonic timestamp assignment, clock skew handling, concurrent writes, appropriate data structures, and time/space complexity analysis.

Implement a simulator for a time-versioned key-value store. The public write API is set(key, value), which does not accept a timestamp from the caller. For deterministic testing, each set operation in the input trace includes the system clock reading observed internally by the store at that moment; this clock reading may repeat or move backwards and must not be used directly as the version timestamp. Assign each write a strictly increasing hybrid logical timestamp (wall, counter): if this is the first write, or the observed clock time is greater than the previous assigned wall component, assign (clockTime, 0); otherwise assign (previousWall, previousCounter + 1). The timestamp order is lexicographic. Support getLatest(key), returning the most recent value written for key, and getAtOrBefore(key, wallTime), returning the value for key with the greatest assigned timestamp whose wall component is at most wallTime. If no such value exists, return the empty string.

Constraints

  • 0 <= len(operations) <= 200000
  • key and value are non-empty strings; value is never the empty string
  • clockTime and wallTime fit in a signed 64-bit integer
  • The system clock readings on set operations may be equal to or less than earlier readings
  • Only set operations create new versions; get operations do not change the store timestamp

Examples

Input: ([['set', 'a', 'v1', '10'], ['getLatest', 'a'], ['getAtOrBefore', 'a', '10'], ['set', 'a', 'v2', '20'], ['getAtOrBefore', 'a', '15'], ['getAtOrBefore', 'a', '20'], ['getLatest', 'a']],)

Expected Output: ['v1', 'v1', 'v1', 'v2', 'v2']

Explanation: The writes receive timestamps (10, 0) and (20, 0). Queries at wall time 15 still see v1, while wall time 20 sees v2.

Input: ([['set', 'k', 'a', '100'], ['set', 'k', 'b', '100'], ['set', 'k', 'c', '99'], ['getAtOrBefore', 'k', '99'], ['getAtOrBefore', 'k', '100'], ['getAtOrBefore', 'k', '101'], ['getLatest', 'k']],)

Expected Output: ['', 'c', 'c', 'c']

Explanation: The clock repeats and then moves backwards, so assigned timestamps are (100, 0), (100, 1), and (100, 2). Nothing exists at wall time 99, and c is the latest version at wall time 100 or later.

Hints

  1. Keep every key's versions in timestamp order. Since global assigned timestamps are increasing as operations are processed, each key's history can be appended to directly.
  2. To handle repeated or backwards clock readings, combine the wall-clock component with a logical counter, then binary search for the upper bound (wallTime, infinity).

Loading coding console...