How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Lead Bank.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Lead Bank during technical interviews.

Implement a versioned hash map with snapshot

Quick Overview

This question evaluates understanding of versioned hash maps, time-travel key-value stores, temporal retrieval semantics, and snapshot creation, testing algorithms and data-structure design in the Coding & Algorithms domain and emphasizing practical implementation with conceptual reasoning about correctness and timestamp semantics.

Company: Lead Bank

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## 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.

Quick Answer: This question evaluates understanding of versioned hash maps, time-travel key-value stores, temporal retrieval semantics, and snapshot creation, testing algorithms and data-structure design in the Coding & Algorithms domain and emphasizing practical implementation with conceptual reasoning about correctness and timestamp semantics.

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).

Examples

Input: ([['put', 'a', 10], ['put', 'a', 20], ['put', 'b', 7], ['get', 'a', 1], ['get', 'a', 2], ['get', 'a', 100], ['freeze', 2], ['freeze', 3]],)

Expected Output: [1, 2, 3, 10, 20, 20, {'a': 20}, {'a': 20, 'b': 7}]

Explanation: The three puts take timestamps 1,2,3. get('a',1)=10 (only the t=1 write is <= 1); get('a',2)=20; get('a',100)=20 (latest). freeze(2)={'a':20} because b's write happens at t=3 (in the future relative to 2); freeze(3) includes both keys.

Input: ([['get', 'x'], ['get', 'x', 5], ['freeze', 10]],)

Expected Output: [None, None, {}]

Explanation: No puts have happened, so every read on an unknown key returns None and the snapshot of an empty store is an empty map.

Input: ([['put', 'k', 1], ['get', 'k'], ['get', 'k', 0], ['freeze', 0], ['freeze', 1]],)

Expected Output: [1, 1, None, {}, {'k': 1}]

Explanation: The put gets timestamp 1. Latest get('k')=1. get('k',0)=None because the only write is at t=1 > 0. freeze(0) is empty (nothing written at or before 0); freeze(1) captures k=1.

Input: ([['put', 'a', -5], ['put', 'a', -10], ['put', 'a', 0], ['get', 'a'], ['get', 'a', 1], ['get', 'a', 2]],)

Expected Output: [1, 2, 3, 0, -5, -10]

Explanation: Three writes to 'a' at t=1,2,3 with values -5,-10,0. Latest get('a')=0. get('a',1)=-5 (as of t=1) and get('a',2)=-10 (as of t=2) confirm overwrites and negative values are handled.

Input: ([],)

Expected Output: []

Explanation: An empty operation list yields an empty result list — the boundary case.

Hints

Store each key's history as a list of (timestamp, value) pairs. Since put timestamps strictly increase, the list stays sorted automatically — just append.
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.
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.
Latest-value get(key) is simply the last entry in the key's history (or null if the key is absent).

Quick Overview