Katkat
Back

Implement a Versioned Key-Value Store

NetflixSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of time-versioned data storage, related data-structure selection, handling of overwrite semantics at equal timestamps, and the ability to reason about correctness and complexity trade-offs.

Design and implement an in-memory versioned key-value store.

Requirements:

  • put(key, value, timestamp): store value for key at the given integer timestamp.
  • get(key, timestamp): return the value for key with the greatest write timestamp less than or equal to timestamp.
  • If no such version exists, return null.
  • A key may be updated many times.
  • If the same key is written multiple times at the same timestamp, the latest write should overwrite the previous value at that timestamp.
  • Discuss the time and space complexity of your implementation.

Example:

put("campaignA", "v1", 10)
put("campaignA", "v2", 20)
get("campaignA", 15) -> "v1"
get("campaignA", 20) -> "v2"
get("campaignA", 5) -> null