Quick Overview

This question evaluates a candidate's grasp of data structures and algorithms needed to implement a temporal key-value store supporting timestamped set/get operations and efficient historical reads, including performance targets like O(log n) per operation.

Design a temporal key-value store with historical reads

Company: Lyft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement a key–value store supporting set(key, value, timestamp) and get(key, timestamp) -> the value at the greatest timestamp ≤ the given timestamp (or empty if none). Optimize for up to 1e5 keys and 1e6 operations; discuss data structures to achieve O(log n) per operation, how you would handle memory growth, and any serialization considerations for persistence.

Quick Answer: This question evaluates a candidate's grasp of data structures and algorithms needed to implement a temporal key-value store supporting timestamped set/get operations and efficient historical reads, including performance targets like O(log n) per operation.

Implement a temporal key-value store that supports two operations: set(key, value, timestamp) and get(key, timestamp). A get must return the value stored for that key at the greatest timestamp less than or equal to the requested timestamp. If no such timestamp exists, return an empty string. Timestamps for the same key may arrive out of order, and calling set on the same key and timestamp should overwrite the old value. For this coding task, process a list of operations and return the answers for all get operations in order. In a follow-up discussion, be prepared to explain how your design scales to 1e5 keys and 1e6 operations, how you would manage memory growth over time, and how you would serialize the data for persistence.

Constraints

  • 0 <= len(operations) <= 10^6
  • There may be up to 10^5 distinct keys
  • Timestamps are integers and may arrive in any order
  • If the same (key, timestamp) is set more than once, the newest value overwrites the previous one

Examples

Input: [('set', 'foo', 'bar', 1), ('get', 'foo', 1), ('get', 'foo', 3), ('set', 'foo', 'bar2', 4), ('get', 'foo', 4), ('get', 'foo', 5)]

Expected Output: ['bar', 'bar', 'bar2', 'bar2']

Explanation: At time 1 and 3, the latest value is 'bar'. After setting timestamp 4, queries at 4 and 5 return 'bar2'.

Input: []

Expected Output: []

Explanation: No operations means there are no get results to return.

Hints

  1. Each get operation is a predecessor query: find the largest stored timestamp <= the requested timestamp for that key.
  2. A hash map gets you to the correct key quickly, but you still need an ordered structure per key. If updates are out of order, think about a balanced BST or treap rather than re-sorting on every insert.

Loading coding console...