Key-value stores commonly combine expiration with optimistic concurrency. TTL removes stale data automatically, while version-based compare-and-set prevents a client from overwriting a value that changed after it was read.
Design a stateful VersionedKeyValueStore class:
int put(String key, String value, int ttl, int now) writes unconditionally and returns the new version.String get(String key, int now) returns the live value or "MISSING".int version(String key, int now) returns the live version or -1.boolean compareAndSet(String key, int expectedVersion, String value, int ttl, int now) updates only a live matching version.boolean remove(String key, int expectedVersion, int now) deletes only a live matching version.
Time is supplied explicitly. A positive TTL expires at now + ttl; the entry is absent when an operation runs at exactly that time. ttl = 0 means no expiration.
Versions are monotonic per key. Successful put, compareAndSet, and remove operations advance the remembered version. Expiration and deletion remove the live entry but do not erase version history, preventing an old version number from being reused.
Example 1:
Input:
Output:
Explanation: Version 1 expires at time 110. Recreating the key uses version 2 because expiration does not reset its version history.
Example 2:
Input:
Output:
Explanation: The first CAS has the wrong version. The second creates version 2, which expires at time 8.
Constraints
1 <= key.length, value.length <= 50- Values never equal
"MISSING". 0 <= ttl <= 10^90 <= now <= 10^9, and now values are non-decreasing within one store instance.- Expiration times fit in signed 64-bit integers.
- At most
10^5 public calls are made to one object.
Build a Versioned TTL Key-Value Storehard