Versioned Hash Map with Snapshot

Design and implement a data structure, VersionedHashMap<K, V>, that extends the functionality of a standard hash map to support time-travel queries and snapshot creation.

Requirements

Implement the following methods:

• long put(K key, V value)

  • Stores the given value for the specified key.
  • Returns a timestamp representing the exact moment this write operation occurred.

• V get(K key)

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

• V get(K key, long timestamp)

  • Retrieves the value associated with key as of the given timestamp.
  • This means returning the value from the write operation with the greatest write-timestamp t such that t <= timestamp.
  • If no write for key occurred at or before timestamp, returns null.

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

  • Generates and returns a plain (non-versioned) Map<K, V> that represents a snapshot of the entire VersionedHashMap's state as of the specified timestamp.
  • For each key that existed at or before timestamp, the returned map should contain its latest value as of that timestamp.

Notes and Assumptions

• Timestamps returned by put are guaranteed to be comparable and strictly increasing for successive put calls. This could be an internal counter or a monotonic millisecond timestamp.
• A freeze(timestamp) operation should produce a snapshot that is immutable with respect to future put operations; subsequent writes should not alter previously frozen snapshots.
• Deletion functionality is not a core requirement. You may choose to support it if it naturally fits your design, but it's not mandatory.

Example

Consider the following sequence of operations and their resulting timestamps:

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

Based on these operations:

• get("a", 1) should return 10.
• get("a", 2) should return 20.
• get("a", 100) should return 20 (as 20 is the latest value up to timestamp 100).
• freeze(2) should return { "a": 20 }.
• freeze(3) should return { "a": 20, "b": 7 }.

Additional Considerations

Be prepared to discuss any additional constraints, such as expected time and space complexity for operations, and concurrency expectations, if applicable to your design.