Katkat
Back

Implement a Rollback Key-Value Store

TeslaSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a data structure that supports basic key-value operations with an added transactional rollback mechanism using a stack-based approach.

Problem Statement

Design a key-value store that supports standard put(key, value) and get(key) operations, along with a rollback() mechanism. When rollback() is called, the system must revert the state of the store to exactly what it was before the most recent put operation. If there are no operations to roll back, the system should behave gracefully.

Requirements

Implement the following class interface:

class RollbackKVStore:
    def put(self, key: str, value: str) -> None:
        # Associates key with value, updating existing keys.

    def get(self, key: str) -> str | None:
        # Returns the value for key, or None if it doesn't exist.

    def rollback(self) -> None:
        # Reverts the store to the state before the last put operation.

Examples

Example 1:

store = RollbackKVStore()
store.put("a", "1")
store.put("b", "2")
store.rollback() 
print(store.get("b")) # Output: None
print(store.get("a")) # Output: "1"

Example 2:

store = RollbackKVStore()
store.put("a", "1")
store.put("a", "2")
store.rollback()
print(store.get("a")) # Output: "1"

Constraints

  • The store should handle string keys and values.
  • put and get operations should ideally run in average O(1) time.
  • rollback should be efficient, ideally O(1) or O(log N) where N is the number of keys.

Hints

Hint 1

Consider maintaining a history stack of all changes made to the store.

Hint 2

For each `put` operation, store not only the key and the new value, but also the previous value that was associated with that key (if any).

Hint 3

When rolling back, pop the last change from the history stack and restore the previous state of that specific key.

Follow-up questions

  • How would you extend this design to support a `commit()` operation that makes a sequence of `put` calls permanent and non-rollbackable?
  • What changes are required to support `rollback(n)` to revert the last `n` operations?
  • How would you optimize the memory usage if the number of operations is extremely large?