Katkat
Back

Design a Versioned Key-Value Store

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a data structure that supports storing multiple values for the same key indexed by timestamps, requiring efficient retrieval of the latest value at or before a specific point in time.

Problem Statement

Design a versioned key-value store that supports storing multiple versions of a value for a given key, where each version is associated with a unique timestamp. Your system should support the following operations:

  1. put(key, value, timestamp): Stores the value associated with key at the given timestamp. Assume timestamps are always provided in strictly increasing order for a specific key.
  2. get(key, timestamp): Returns the value associated with the key that was active at the given timestamp. If there is no exact match for the timestamp, return the value associated with the largest timestamp that is less than or equal to the requested timestamp. If no such value exists, return None.

Constraints

  • 1 <= key.length, value.length <= 100
  • 1 <= timestamp <= 10^9
  • put calls are made with strictly increasing timestamps for each key.

Example

kv = VersionedStore()
kv.put("config", "v1", 1)
kv.get("config", 1) # returns "v1"
kv.get("config", 3) # returns "v1"
kv.put("config", "v2", 4)
kv.get("config", 3) # returns "v1"
kv.get("config", 5) # returns "v2"

Considerations

  • How would you structure your data storage to optimize for the get operation?
  • What is the time complexity of your get method? Can you achieve logarithmic time complexity?

Hints

Hint 1

Consider using a hash map where the key maps to a list or array of tuples containing timestamps and their corresponding values.

Hint 2

Since timestamps are inserted in increasing order, the list of versions for any given key will naturally be sorted by time.

Hint 3

Binary search is an efficient way to find the largest timestamp less than or equal to the target within a sorted collection.

Follow-up questions

  • How would you modify the system if timestamps were no longer guaranteed to be inserted in chronological order?
  • What changes would be required to support a `delete(key, timestamp)` operation that removes a specific version?
  • How would you handle potential memory issues if the system stores millions of versions for a single key?