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

What role is this question designed for?

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

Implement a timestamped map | Affirm Coding Question

Implement a timestamped map

Company: Affirm

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an in-memory timestamped map. Support these operations: - `put(key, value, timestamp)`: store `value` for `key` at the given integer `timestamp` - `get(key, timestamp)`: return the value written for `key` at the greatest timestamp less than or equal to `timestamp`; return an empty string if no such value exists Additional notes: - for the same key, writes arrive in strictly increasing timestamp order - keys and values are strings - aim for efficient reads and writes

Quick Answer: This question evaluates a candidate's ability to implement time-indexed key-value storage, covering data structure design, versioning semantics, and algorithmic complexity for efficient reads and writes.

Implement a function that processes operations on an in-memory timestamped map. Each key can have multiple values written at different integer timestamps. Supported operations: - put(key, value, timestamp): store value for key at the given timestamp - get(key, timestamp): return the value written for key at the greatest timestamp less than or equal to timestamp If no such value exists, return an empty string. Important: for the same key, put operations always arrive in strictly increasing timestamp order. Use this to make reads efficient. Your task is to process a list of operations and return the results of all get operations in order.

Constraints

0 <= len(operations) <= 200000
1 <= timestamp <= 1000000000
For the same key, put timestamps are strictly increasing
Keys are non-empty strings
Values are non-empty strings

Examples

Input: ([('put', 'foo', 'bar', 1), ('get', 'foo', 1), ('get', 'foo', 3), ('put', 'foo', 'bar2', 4), ('get', 'foo', 4), ('get', 'foo', 5)],)

Expected Output: ["bar", "bar", "bar2", "bar2"]

Explanation: At time 1 and 3, the latest value for 'foo' is 'bar'. After writing 'bar2' at time 4, queries at 4 and 5 return 'bar2'.

Input: ([('get', 'x', 10), ('put', 'x', 'a', 5), ('get', 'x', 4), ('get', 'x', 5), ('get', 'x', 6)],)

Expected Output: ["", "", "a", "a"]

Explanation: The first query has no prior write. After writing 'a' at time 5, a query at time 4 still has no answer, while queries at 5 and 6 return 'a'.

Input: ([('put', 'love', 'high', 10), ('put', 'love', 'low', 20), ('put', 'hate', 'meh', 15), ('get', 'love', 5), ('get', 'love', 10), ('get', 'love', 15), ('get', 'love', 20), ('get', 'hate', 15), ('get', 'hate', 100)],)

Expected Output: ["", "high", "high", "low", "meh", "meh"]

Explanation: Queries use the latest timestamp not greater than the requested time, independently for each key.

Input: ([],)

Expected Output: []

Explanation: With no operations, there are no get results.

Hints

Store each key's history separately so you can search only within that key's values.
Because timestamps for a key are already sorted, use binary search to find the rightmost timestamp less than or equal to the query time.

Quick Overview

This question evaluates a candidate's ability to implement time-indexed key-value storage, covering data structure design, versioning semantics, and algorithmic complexity for efficient reads and writes.