Implement a versioned hash map with snapshot

VersionedHashMap (time-travel key-value store)

Design and implement a data structure VersionedHashMap<K, V> backed by a hash map that supports retrieving the latest value for a key as of a given timestamp, and creating a frozen snapshot at a timestamp.

Requirements

Implement the following methods:

• long put(K key, V value)

  • Store value for key.
  • Return a timestamp representing when this write happened.

• V get(K key)

  • Return the latest value currently associated with key.
  • If key has never been set, return null.

• V get(K key, long timestamp)

  • Return the value associated with key as of timestamp (i.e., the value written with the greatest write-timestamp t such that t <= timestamp).
  • If there is no write for key at or before timestamp, return null.

• Map<K, V> freeze(long timestamp)

  • Return a plain (non-versioned) hash map representing a snapshot of the entire map as of timestamp.
  • The returned map should contain, for each key that existed at or before timestamp, exactly its latest value as of timestamp.

Notes / Assumptions to clarify during implementation

• Timestamps returned by put are comparable and strictly increasing for successive put calls (e.g., an internal counter, or millisecond time if guaranteed monotonic in your environment).
• freeze(timestamp) should not be affected by future put operations.
• Ignore deletion unless you choose to support it (not required).

Example (one possible behavior)

If operations occur at timestamps 1, 2, 3:

• put("a", 10) -> 1
• put("a", 20) -> 2
• put("b", 7) -> 3

Then:

• get("a", 1) == 10
• get("a", 2) == 20
• get("a", 100) == 20
• freeze(2) returns { "a": 20 }
• freeze(3) returns { "a": 20, "b": 7 }

Define any additional constraints (expected time/space complexity, concurrency expectations) if needed.

Implement a Versioned Hash Map with Snapshot

Design and implement a VersionedHashMap (a time-travel key-value store) backed by a hash map. It must support reading the value of a key as of any past timestamp and producing a frozen snapshot of the whole map at a timestamp.

Because this console grades a single entry point, you implement the data structure indirectly: write a function that replays a list of operations against your VersionedHashMap and returns a list with one result per operation.

Operation format

Each operation is a list:

• ["put", key, value] — store value for key. Each successful put is assigned the next strictly-increasing internal timestamp (1, 2, 3, …). Return that assigned timestamp.
• ["get", key] — return the latest value currently associated with key, or null/None if the key was never written.
• ["get", key, timestamp] — return the value written with the greatest write-timestamp t such that t <= timestamp, or null/None if there is no write at or before timestamp.
• ["freeze", timestamp] — return a plain map (dict / object) holding, for every key written at or before timestamp, its latest value as of timestamp. Keys with no write at or before timestamp are omitted. The snapshot must not be affected by future put calls.

Return value

Return a list the same length as operations, where the i-th element is the result of the i-th operation (the assigned timestamp for put, the looked-up value for get, the snapshot map for freeze).

Example

Operations: [["put","a",10], ["put","a",20], ["put","b",7], ["get","a",1], ["get","a",2], ["get","a",100], ["freeze",2], ["freeze",3]]

Result: [1, 2, 3, 10, 20, 20, {"a":20}, {"a":20, "b":7}]

• put calls are assigned timestamps 1, 2, 3.
• get("a",1)=10 (only the first write is <= 1), get("a",2)=20, get("a",100)=20 (latest).
• freeze(2)={"a":20} (b's write at t=3 is in the future), freeze(3)={"a":20,"b":7}.

Constraints

• Timestamps assigned by put are strictly increasing (1, 2, 3, ...), so each key's write history is already sorted by time.
• get(key, timestamp) returns the value of the greatest write-timestamp t with t <= timestamp; if none, returns null/None.
• freeze(timestamp) returns only keys that had at least one write at or before timestamp, each mapped to its latest value as of that timestamp.
• A returned freeze snapshot is a value copy and is unaffected by later put operations.
• Keys are strings; values are integers in these tests (the design generalizes to any hashable key / any value).

Hints

1. Store each key's history as a list of (timestamp, value) pairs. Since put timestamps strictly increase, the list stays sorted automatically — just append.
2. For get(key, timestamp), binary-search the key's timestamps for the rightmost entry with t <= timestamp (e.g. bisect_right(times, timestamp) - 1). A negative index means no write existed yet.
3. freeze(timestamp) is just that same as-of lookup applied to every key; skip keys whose earliest write is after timestamp. Build a fresh map so future puts can't mutate it.
4. Latest-value get(key) is simply the last entry in the key's history (or null if the key is absent).