Q1 - MongoDB Point-in-Time Versioned Store (~3 Parts)

In the distributed core of MongoDB, a single document can be written many times. Yet the database can still answer a powerful question: "What was the value of this key as of a particular moment in time?" This is the foundation of point-in-time reads, reads that see a consistent snapshot of the data, even while new writes are streaming in.

Your task is to build a simplified version of this engine: a versioned key/value store. Every write is stamped with a timestamp, and every read is also parameterized by a timestamp, returning the value the key held at that point in its history.

Part 1: Point-in-Time Reads (~10 minutes)

Implement a VersionedStore supporting two operations:

• set(key, value, timestamp), records that key held value starting at time timestamp.
• get(key, timestamp), returns the value associated with the version whose timestamp is the largest one less than or equal to the query timestamp. If no such version exists (the key was never written at or before that time), return null / None.

Operations:
set("user:1", "Alice", 5)
set("user:1", "Alphonse", 12)

get("user:1", 5)    -> "Alice"
get("user:1", 9)    -> "Alice"      # newest version at or before t=9 is the one at t=5
get("user:1", 12)   -> "Alphonse"
get("user:1", 100)  -> "Alphonse"   # the latest version persists into the future
get("user:1", 3)    -> null         # no version existed at or before t=3
get("user:2", 5)    -> null         # key never written

Solution - Part 1

The key insight: store, per key, a list of (timestamp, value) versions ordered by time. Because timestamps for a key are strictly increasing, every set is a simple append, the list stays sorted for free.

For get, we need the rightmost version whose timestamp is ≤ the query time. A sorted list plus this "find the last element ≤ target" requirement is the textbook setup for binary search.

class VersionedStore:
    def __init__(self):
        # key -> list of (timestamp, value), kept sorted by timestamp
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        # Timestamps per key strictly increase, so append keeps it sorted.
        self.store.setdefault(key, []).append((timestamp, value))

    def get(self, key: str, timestamp: int):
        versions = self.store.get(key)
        if not versions:
            return None

        # Binary search for the rightmost version with version_ts <= timestamp.
        lo, hi, result = 0, len(versions) - 1, None
        while lo <= hi:
            mid = (lo + hi) // 2
            if versions[mid][0] <= timestamp:
                result = versions[mid][1]   # candidate; keep searching to the right
                lo = mid + 1
            else:
                hi = mid - 1
        return result

Complexity Analysis

• set: O(1) amortized, a single append to the key's version list.
• get: O(log n), where n is the number of versions for that key (binary search).
• Space: O(m), where m is the total number of writes across all keys, every version is retained.

Part 2: Deletes and Tombstones (~15 minutes)

Now the interviewer adds a delete(key, timestamp) operation, and this is where the problem stops being a standard exercise and starts behaving like a real database.

The naive instinct is to remove the key's data. Resist it. If you physically delete the history, you destroy the ability to answer point-in-time reads from before the deletion. A read at an earlier timestamp must still see the value that was live back then.

The correct model, the one MongoDB and virtually every log-structured database use, is a tombstone: a delete is just another version, a marker that says "as of this timestamp, the key is gone." Reads then resolve against tombstones like any other version.

So get(key, timestamp) now works like this:

• Find the newest version with timestamp ≤ the query time (same binary search as Part 1).
• If there is no such version → return null.
• If that version is a tombstone → the key was deleted as of that time → return null.
• Otherwise → return its value.

Operations:
set("user:1", "Alice", 5)
delete("user:1", 10)
set("user:1", "Bob", 15)

get("user:1", 3)    -> null      # nothing existed yet at t=3
get("user:1", 7)    -> "Alice"   # newest version at or before t=7 is set@5
get("user:1", 12)   -> null      # newest version at or before t=12 is the tombstone@10
get("user:1", 20)   -> "Bob"     # the key was "resurrected" by set@15

Visualizing the Version Timeline

The magic of this model is that the same key answers different values depending on when you ask, and a delete in the future never erases the past:

  key = "user:1"

        t=5                 t=10                t=15
   ┌───────────┐       ┌───────────┐       ┌───────────┐
   │   SET     │       │  DELETE   │       │   SET     │
   │  "Alice"  │       │ (tombstone)│      │   "Bob"   │
   └───────────┘       └───────────┘       └───────────┘
 ──────●─────────────────────●───────────────────●──────────────▶  time
       │                     │                    │
   get(7)="Alice"       get(12)=null         get(20)="Bob"
   get(3)=null          (deleted as of t=10) (resurrected at t=15)

Solution - Part 2

We extend each version with a boolean deleted flag. set appends a normal version; delete appends a tombstone (a version with deleted = true and no meaningful value). The get binary search is unchanged. We simply inspect the deleted flag on the winning version before returning.

class VersionedStore:
    def __init__(self):
        # key -> list of (timestamp, value, deleted), sorted by timestamp
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store.setdefault(key, []).append((timestamp, value, False))

    def delete(self, key: str, timestamp: int) -> None:
        # A delete is a tombstone version, NOT a physical removal.
        self.store.setdefault(key, []).append((timestamp, None, True))

    def get(self, key: str, timestamp: int):
        versions = self.store.get(key)
        if not versions:
            return None

        lo, hi, found = 0, len(versions) - 1, None
        while lo <= hi:
            mid = (lo + hi) // 2
            if versions[mid][0] <= timestamp:
                found = versions[mid]   # candidate; keep searching to the right
                lo = mid + 1
            else:
                hi = mid - 1

        # No version, or the winning version is a tombstone.
        if found is None or found[2]:
            return None
        return found[1]

Complexity Analysis

• set / delete: O(1) amortized, both are appends; a delete is just a tombstone version.
• get: O(log n), the binary search is unchanged; the tombstone check is O(1).
• Space: O(m), tombstones count as versions, so deleting does not reclaim space (real engines reclaim it later via background compaction).

Part 3: Concurrent Access (~25 minutes)

Here comes the part MongoDB is famous for. The interviewer leans in: "Good. Now imagine many threads are hitting this store at the same time, multiple writers calling set/delete, and many readers calling get. Make it thread-safe."

This is the single most common MongoDB extension, and it separates candidates who use data structures from those who understand what happens underneath them. The danger: two threads appending to the same key's list simultaneously can corrupt it (lost writes, resized-array races, partially-constructed objects). A reader binary-searching a list while another thread mutates it can read garbage or crash.

The clean, correct answer is a read–write lock:

• set and delete take the write lock (exclusive, only one writer, and no readers, at a time).
• get takes the read lock (shared, many readers may proceed in parallel).

This is the right call because this workload, like most database workloads, is read-heavy. A plain mutex would needlessly serialize readers; a read–write lock lets them run concurrently and only blocks them while a writer is mid-append.

Threads (any interleaving):
  Thread A: set("config", "v1", 1)
  Thread B: set("config", "v2", 2)
  Thread C: get("config", 1)   -> "v1"   (never a crash, never a torn read)
  Thread D: get("config", 2)   -> "v2"
  Thread E: get("config", 5)   -> "v2"

Writers are serialized with each other; readers run concurrently
and always observe a consistent version list.

Solution - Part 3

We wrap the Part 2 logic in a read–write lock. The algorithm is identical, only the synchronization is new. Below are the languages where true OS-thread parallelism applies; see the note afterward on JavaScript/TypeScript.

import threading

class VersionedStore:
    def __init__(self):
        self.store = {}
        # Python's stdlib has no read-write lock, and the GIL already serializes
        # bytecode, but it does NOT make compound append+read sequences atomic.
        # A single mutex is the correct, simple guarantee here.
        self._lock = threading.Lock()

    def set(self, key: str, value: str, timestamp: int) -> None:
        with self._lock:
            self.store.setdefault(key, []).append((timestamp, value, False))

    def delete(self, key: str, timestamp: int) -> None:
        with self._lock:
            self.store.setdefault(key, []).append((timestamp, None, True))

    def get(self, key: str, timestamp: int):
        with self._lock:
            versions = self.store.get(key)
            if not versions:
                return None
            lo, hi, found = 0, len(versions) - 1, None
            while lo <= hi:
                mid = (lo + hi) // 2
                if versions[mid][0] <= timestamp:
                    found = versions[mid]
                    lo = mid + 1
                else:
                    hi = mid - 1
            if found is None or found[2]:
                return None
            return found[1]

Complexity Analysis

• set / delete: O(1) amortized work, plus exclusive lock acquisition.
• get: O(log n) work under a shared lock, multiple readers proceed concurrently.
• Contention: writers briefly block everyone; in a read-heavy workload the read–write lock keeps reader throughput high. A finer-grained design uses one lock per key so writes to different keys never contend.

Final Notes

Here's the real-talk on why MongoDB reaches for this question and how to shine on it:

1. You're rebuilding MongoDB's storage engine in miniature. Point-in-time reads, immutable versions, tombstones, snapshot isolation, these aren't interview contrivances. They are the literal mechanics of WiredTiger (MongoDB's storage engine) and the oplog. When you connect your solution back to "this is how a snapshot read at an older cluster time works," you stop sounding like a candidate grinding LeetCode and start sounding like a future MongoDB engineer. Interviewers notice that instantly.

2. The tombstone is the "aha" they're waiting for. Many candidates physically delete data in Part 2 and silently break point-in-time reads from before the deletion. The ones who pause and say "a delete should be a version, not a removal, or I'll lose history" have demonstrated database intuition that's hard to fake. That single decision is often the difference between a "hire" and a "leaning hire."

3. Concurrency is where MongoDB interviews live. As we covered on the prep guide, the "now make it thread-safe" follow-up shows up more at MongoDB than almost anywhere else. Don't just slap on a mutex, articulate the read-heavy → read–write lock reasoning, mention per-key locking to reduce contention, and land the immutability/MVCC insight that explains why reads don't fundamentally need to block writes. That progression (correct → concurrent → lock-free-in-principle) is what a senior answer walks through out loud.

4. Make it run, and test the boundaries. Remember MongoDB uses a real compiler (Coderpad), your code is expected to execute. Before you call it done, walk these edge cases out loud and verify them: a get before any write, a get exactly on a version's timestamp, a get between two versions, a key that is set → deleted → set again, and a get far in the future. These are precisely the cases the interviewer's hidden tests will hit.

The bottom line: this problem looks like "Time-Based Key-Value Store" at first glance, but MongoDB pushes it well past the textbook version into deletes, snapshots, and concurrency, the exact terrain their engineers walk every day. Nail the systems reasoning, not just the binary search, and you'll stand out.