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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Netflix.

What role is this question designed for?

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

Implement a Versioned Key-Value Store | Netflix Coding Question

Implement a Versioned Key-Value Store

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Design and implement an in-memory versioned key-value store. Requirements: - `put(key, value, timestamp)`: store `value` for `key` at the given integer `timestamp`. - `get(key, timestamp)`: return the value for `key` with the greatest write timestamp less than or equal to `timestamp`. - If no such version exists, return `null`. - A key may be updated many times. - If the same key is written multiple times at the same timestamp, the latest write should overwrite the previous value at that timestamp. - Discuss the time and space complexity of your implementation. Example: ```text put("campaignA", "v1", 10) put("campaignA", "v2", 20) get("campaignA", 15) -> "v1" get("campaignA", 20) -> "v2" get("campaignA", 5) -> null ```

Quick Answer: This question evaluates understanding of time-versioned data storage, related data-structure selection, handling of overwrite semantics at equal timestamps, and the ability to reason about correctness and complexity trade-offs.

Design and implement an in-memory versioned key-value store. Process a sequence of operations of two types: - put(key, value, timestamp): store value for key at the given integer timestamp. - get(key, timestamp): return the value for key with the greatest write timestamp less than or equal to timestamp. If no such version exists, return None (this represents null in Python). A key may be updated many times. If the same key is written multiple times at the same timestamp, the latest write overwrites the previous value at that timestamp. For this coding problem, implement a function that receives all operations in batch form and returns the results of every get operation in order.

Constraints

0 <= n <= 20000, where n is the number of operations
len(actions) == len(keys) == len(values) == len(timestamps)
actions[i] is either "put" or "get"
timestamps[i] are integers in the range [-10^9, 10^9]
Keys and stored values are strings

Examples

Input: (['put', 'put', 'get', 'get', 'get'], ['campaignA', 'campaignA', 'campaignA', 'campaignA', 'campaignA'], ['v1', 'v2', '', '', ''], [10, 20, 15, 20, 5])

Expected Output: ['v1', 'v2', None]

Explanation: campaignA has versions at timestamps 10 and 20. Query 15 returns v1, query 20 returns v2, and query 5 has no earlier version.

Input: (['put', 'put', 'get', 'get'], ['k', 'k', 'k', 'k'], ['a', 'b', '', ''], [5, 5, 5, 6])

Expected Output: ['b', 'b']

Explanation: The second put overwrites the value for key k at the same timestamp 5. Both gets return the latest value b for timestamp 5.

Input: (['put', 'put', 'put', 'get', 'get', 'get', 'get', 'get'], ['k', 'k', 'x', 'k', 'k', 'k', 'x', 'missing'], ['late', 'early', 'x1', '', '', '', '', ''], [10, 3, 7, 4, 9, 10, 8, 1])

Expected Output: ['early', 'early', 'late', 'x1', None]

Explanation: Versions for k are inserted out of order but should still be searchable by timestamp. Queries return the greatest timestamp not exceeding each request.

Input: ([], [], [], [])

Expected Output: []

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

Input: (['put', 'put', 'get', 'get', 'get', 'get'], ['a', 'a', 'a', 'a', 'a', 'a'], ['neg', 'zero', '', '', '', ''], [-2, 0, -3, -2, -1, 0])

Expected Output: [None, 'neg', 'neg', 'zero']

Explanation: Negative timestamps are valid. The query at -3 has no matching version, while later queries return the closest earlier version.

Hints

Store the version history for each key separately using a hash map.
If each key keeps its timestamps sorted, you can use binary search to find the latest timestamp less than or equal to a query time.

Quick Overview

This question evaluates understanding of time-versioned data storage, related data-structure selection, handling of overwrite semantics at equal timestamps, and the ability to reason about correctness and complexity trade-offs.