How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

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.

Input: ([['set', 'a', 'x', '5'], ['set', 'b', 'y', '4'], ['getAtOrBefore', 'b', '4'], ['getAtOrBefore', 'b', '5'], ['set', 'a', 'z', '6'], ['getAtOrBefore', 'a', '5'], ['getAtOrBefore', 'a', '6']],)

Expected Output: ['', 'y', 'x', 'z']

Explanation: The second write observes clock time 4, but the previous assigned wall component is 5, so b=y receives timestamp (5, 1). Therefore b is not visible at wall time 4 but is visible at wall time 5.

Input: ([],)

Expected Output: []

Explanation: There are no operations, so there are no get results.

Input: ([['getLatest', 'missing'], ['getAtOrBefore', 'missing', '0'], ['set', 'n', 'old', '-5'], ['getAtOrBefore', 'n', '-6'], ['getAtOrBefore', 'n', '-5'], ['set', 'n', 'newer', '-10'], ['getAtOrBefore', 'n', '-5'], ['getLatest', 'n']],)

Expected Output: ['', '', '', 'old', 'newer', 'newer']

Explanation: Missing keys return ''. The first negative-time write gets (-5, 0). The later write observes -10, so it gets (-5, 1) and becomes the current value at wall time -5.

Hints

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.
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).

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.