87. Design Time Versioned Key Value Store

Design Time Versioned Key Value Store
You are asked to design and implement an in-memory time versioned data store. The store maintains key-value pairs across time. Each write creates a new version for that key, associated with a timestamp.

The store must support:
  • Writing a value for a key at the current timestamp.
  • Reading the latest value for a key.
  • Reading a historical value for a key as of a given timestamp.
  • Reading a value for a key by an explicit version number.

All data must be stored in-memory (no database).

Key Definitions

  • Key: a string identifier used to group versions (e.g., "price").
  • Value: a string payload stored for a key (e.g., "100").
  • Timestamp: number of seconds elapsed since 1 Jan 1970.
  • Version: a 0-based integer index per key. Every successful write increments the key's version by 1.

Method Signatures

boolean put(String key, String value, long currentTimestamp)

Stores the given value for key at the store's current timestamp. Each successful call creates a new version for that key. First put is version 0.
  • Returns true if the write is stored successfully.
  • Returns false if key or value is null or blank.
  • currentTimestamp will always be a positive integer and monotonically increasing .
  • If there are multiple writes for the same key at the same timestamp then they will be versioned in the order in which they occurred.

String get(String key)

Returns the latest value stored for key.
  • Returns the latest stored value if present.
  • Returns an empty string "" if the key has no stored value.

String get(String key, long timestamp)

Returns the value for key as of the provided timestamp.
  • If there exists at least one write for the key with writeTimestamp ≤ timestamp, return the value from the write with the maximum such writeTimestamp.
  • Returns an empty string "" if:
    • the key has no stored value, or
    • timestamp is earlier than the first write for that key.

String getByVersion(String key, int version)

Returns the value for key at the given version (0-based).
  • Returns the stored value for that exact version if it exists.
  • Returns an empty string "" if:
    • the key has no stored value, or
    • version is out of range (e.g., version < 0 or version > currentVersion).

List<String> listVersionTimestamps(String key)

Returns all verions and their timestamps for the stored versions of key in increasing order.
  • Each row is formatted as "version,timestamp" e.g. "2,28738734"
  • Returns an empty list if the key has no stored value.

Constraints

  • 1 ≤ key.length() ≤ 100
  • 0 ≤ value.length() ≤ 100
  • get(key, timestamp) must be efficient for many versions (binary search on timestamps is expected).
  • All operations must be in-memory; no external persistence is allowed.

Examples

In the examples below, we pass explicit currentTimestamp values to put. For readability, we also demonstrate version history using listVersionTimestamps(key), which returns rows formatted as "version,timestamp".

Example 1: Basic latest value + invalid write

  • put(key="a", value="v1", currentTimestamp=100) → true
  • get(key="a") → "v1"
  • put(key="a", value=" ", currentTimestamp=101) → false (blank value is rejected; no new version is created)
  • get(key="a") → "v1" (still the latest stored value)
  • get(key="missing") → ""

Example 2: Multiple versions + getByVersion + listVersionTimestamps

  • put(key="a", value="v1", currentTimestamp=100) → true (creates version 0)
  • put(key="a", value="v2", currentTimestamp=105) → true (creates version 1)
  • put(key="a", value="v3", currentTimestamp=110) → true (creates version 2)
  • listVersionTimestamps(key="a") → ["0,100", "1,105", "2,110"]
  • getByVersion(key="a", version=0) → "v1"
  • getByVersion(key="a", version=1) → "v2"
  • getByVersion(key="a", version=2) → "v3"
  • getByVersion(key="a", version=3) → "" (out of range)
  • getByVersion(key="a", version=-1) → "" (out of range)

Example 3: As-of timestamp queries

  • put(key="k", value="one", currentTimestamp=10) → true (version 0 at timestamp 10)
  • put(key="k", value="two", currentTimestamp=20) → true (version 1 at timestamp 20)
  • put(key="k", value="three", currentTimestamp=30) → true (version 2 at timestamp 30)
  • get(key="k", timestamp=10) → "one"
  • get(key="k", timestamp=19) → "one" (latest write where writeTimestamp ≤ 19 is at 10)
  • get(key="k", timestamp=20) → "two"
  • get(key="k", timestamp=25) → "two" (latest write where writeTimestamp ≤ 25 is at 20)
  • get(key="k", timestamp=30) → "three"
  • get(key="k", timestamp=9) → "" (timestamp is earlier than the first write for that key)

Example 4: Independent versioning per key

  • put(key="a", value="a1", currentTimestamp=100) → true (key a version 0)
  • put(key="b", value="b1", currentTimestamp=101) → true (key b version 0)
  • put(key="a", value="a2", currentTimestamp=110) → true (key a version 1)
  • get(key="a") → "a2" (latest value for key a)
  • listVersionTimestamps(key="a") → ["0,100", "1,110"]
  • listVersionTimestamps(key="b") → ["0,101"]
  • getByVersion(key="b", version=0) → "b1"
  • getByVersion(key="b", version=1) → "" (out of range for key b)




Please use Laptop/Desktop or any other large screen to add/edit code.