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 Technical Screen rounds at Tesla.

What role is this question designed for?

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

Implement a Rollback Key-Value Store

Company: Tesla

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Design and implement an in-memory key-value store that supports rollback. The store should support at least the following operations: - `set(key, value)`: Store or overwrite the value for `key`. - `get(key)`: Return the current value for `key`, or `null`/`None` if the key does not exist. - `delete(key)`: Remove `key` from the store if it exists. - `rollback()`: Undo the most recent mutating operation, restoring the store to its previous state. Clarify edge cases and implement reasonable behavior for them, including: - Rolling back after a `set` that overwrote an existing value. - Rolling back after a `set` that created a new key. - Rolling back after a `delete`. - Calling `rollback()` when there is no operation to undo. Optimize for clean API design and efficient time and space complexity.

Quick Answer: This question evaluates competency in designing data structures and state-management mechanisms, focusing on rollback/undo semantics, versioning, and efficient history tracking.

You are given a sequence of operations to perform on an in-memory key-value store. The store supports four operations: - set(key, value): store or overwrite the value for key - get(key): return the current value for key, or None if the key does not exist - delete(key): remove key if it exists - rollback(): undo the most recent mutating operation Rules and edge cases: - Every set operation is considered a mutation and must be undoable. - Rolling back a set that created a new key should remove that key. - Rolling back a set that overwrote an existing value should restore the previous value. - Rolling back a delete should restore the deleted key and its old value. - Deleting a key that does not exist is a no-op and should not create rollback history. - If rollback() is called when there is no mutation to undo, it should return False. Implement the store by processing all operations in order. Return a list containing the outputs of every get and rollback operation, in the same order they appear. - For get, append the value or None. - For rollback, append True if an operation was undone, otherwise False.

Constraints

0 <= len(operations) <= 200000
Each key is a string of length 1 to 50
Each value is an integer in the range [-10^9, 10^9]
Average O(1) dictionary operations may be assumed

Examples

Input: [("set", "a", 1), ("get", "a"), ("rollback",), ("get", "a")]

Expected Output: [1, True, None]

Explanation: The key 'a' is created with value 1. get returns 1. rollback undoes that set, so 'a' is removed. The final get returns None.

Input: [("set", "a", 1), ("set", "a", 2), ("get", "a"), ("rollback",), ("get", "a"), ("rollback",), ("get", "a")]

Expected Output: [2, True, 1, True, None]

Explanation: The second set overwrites 'a' from 1 to 2. The first rollback restores 1. The second rollback removes 'a' entirely because the original set created it.

Input: [("set", "x", 5), ("delete", "x"), ("get", "x"), ("rollback",), ("get", "x")]

Expected Output: [None, True, 5]

Explanation: After deleting 'x', get returns None. rollback restores the deleted key with value 5.

Input: [("delete", "missing"), ("rollback",), ("set", "k", 7), ("delete", "missing"), ("rollback",), ("get", "k")]

Expected Output: [False, True, None]

Explanation: Deleting a missing key does nothing, so the first rollback has nothing to undo and returns False. After setting 'k', the later delete of 'missing' is still a no-op, so rollback undoes the set of 'k'.

Input: [("set", "a", -1), ("set", "b", 2), ("set", "a", 3), ("delete", "b"), ("get", "a"), ("get", "b"), ("rollback",), ("rollback",), ("get", "a"), ("get", "b")]

Expected Output: [3, None, True, True, -1, 2]

Explanation: Before rollback, 'a' is 3 and 'b' has been deleted. The first rollback restores 'b' = 2. The second rollback undoes the overwrite of 'a', restoring it to -1.

Input: []

Expected Output: []

Explanation: No operations produce no outputs.

Hints

Instead of copying the entire store before each change, record only the information needed to undo the last mutation.
A stack is a natural fit because rollback always undoes the most recent mutating operation.

Quick Overview

This question evaluates competency in designing data structures and state-management mechanisms, focusing on rollback/undo semantics, versioning, and efficient history tracking.