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.