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.