Design a Versioned Datastore with PUT and GET

Problem Statement

You are building a versioned datastore. Implement two APIs:

1. PUT(docId, contents, timestamp) — Save the contents for a given docId at the given timestamp. Multiple PUTs can happen for the same docId with different timestamps (storing versions). PUTs can arrive in any order of timestamp.

2. GET(docId, timestamp) — Return the content of that docId for the version at or just before the given timestamp. If no version exists before the timestamp, return an empty string.

Constraints

• 1 <= docId <= 10^5
• 1 <= timestamp <= 10^9
• Timestamps for PUT can arrive out of order
• At most 10^5 total PUT and GET calls
• GET should be efficient (better than scanning all versions)

Example

PUT(1, "abc", 10)
PUT(2, "bcd", 11)
PUT(1, "cde", 8)
PUT(2, "def", 9)

GET(1, 5)  → ""      (no version of doc 1 exists at or before t=5)
GET(1, 9)  → "cde"   (version at t=8 is the latest before t=9)
GET(2, 15) → "bcd"   (version at t=11 is the latest before t=15)
GET(1, 10) → "abc"   (exact match at t=10)

What the Interviewer Expects

1. Data structure choice — HashMap<docId, sorted structure of (timestamp → content)>. The sorted structure is the key decision.
2. Options for sorted structure:
   • Sorted array + binary search (good if PUTs are infrequent)
   • Self-balancing BST / TreeMap (O(log n) PUT and GET)
   • Skip list (alternative to BST)
3. GET is a "floor" query — find the largest timestamp ≤ given timestamp. Binary search or BST's floorEntry().
4. Handle unordered PUTs — insertions must maintain sorted order by timestamp.
5. Time complexity: PUT: O(log v), GET: O(log v) where v = number of versions for a doc.

Follow-ups

1. What if you need to support DELETE(docId, timestamp)? How does GET behave after a delete?
2. How would you persist this to disk efficiently? (hint: LSM tree, append-only log)
3. What if GET needs to return the content at the exact timestamp only (not floor)? How does that simplify things?
4. How would you handle concurrent PUTs to the same docId in a multi-threaded environment?
5. What if you need to support range queries — "give me all versions of docId between t1 and t2"?