Software Engineer · Full Journey · System Design

Rippling — Software Engineer ✅ Passed

Level: Senior-Level

Round: Full Journey · Type: System Design · Difficulty: 7/10 · Duration: 180 min · Interviewer: Unfriendly

Topics: Data Structures, Transactions, In-Memory Key-Value Store, HashMap, Nested Transactions, Concurrency, Write-Ahead Log, LRU Cache, Mutex

Location: San Francisco Bay Area

Interview date: 2025-12-27

Summary

Design Key-Value Store

Round 1: Basic Key-Value Store

Question: Implement a simple in-memory key-value store with set, get, and delete operations.

---

Round 2: Adding Basic Transactions

Question: Add transaction support to the key-value store, including begin, commit, and rollback operations.

---

Round 3: Nested Transactions

Question: Extend the transaction support to handle nested transactions, where a transaction can be started inside another one.

Details

The challenge was to build an in-memory key-value store that supports standard CRUD operations and transactions. The goal was to ensure accuracy, data management, and scalability to handle nested transactions.

Part 1: Basic Store

I needed to implement set, get, and delete methods. The solution involved using a standard dictionary (HashMap) for fast operations. The time complexity for each operation is O(1), and the overall space complexity is O(n), where n is the number of keys.

` class Database: def init(self): self._store: dict[str, str] = {}

def set(self, key: str, value: str) -> None:
    """Save a value for a key."""
    self._store[key] = value

def get(self, key: str) -> str | None:
    """Find the value for a key. Return None if not found."""
    return self._store.get(key)

def delete(self, key: str) -> bool:
    """Remove a key. Return True if it was there, False if not."""
    if key in self._store:
        del self._store[key]
        return True
    return False

`

Part 2: Basic Transactions

I had to add begin(), commit(), and rollback() methods to support transactions. The key was to use a separate temporary map for tracking changes within a transaction. The time complexity for begin and rollback is O(1). The time complexity for commit is O(t), where t is the number of keys changed in the transaction. The space complexity for each of these operations is O(1). The time complexity for set, get, and delete remains O(1).

` class Database: # A unique marker to represent deleted keys _DELETED = object()

def __init__(self):
    self._store: dict[str, str] = {}
    self._transaction: dict[str, str | object] | None = None

def set(self, key: str, value: str) -> None:
    """Set key to value."""
    if self._transaction is not None:
        self._transaction[key] = value
    else:
        self._store[key] = value

def get(self, key: str) -> str | None:
    """Get value for key. Returns None if key doesn't exist."""
    if self._transaction is not None:
        if key in self._transaction:
            value = self._transaction[key]
            # Check if this key was marked as deleted
            if value is self._DELETED:
                return None
            return value
    # Look in the main store if not in transaction
    return self._store.get(key)

def delete(self, key: str) -> bool:
    """Delete key. Returns True if key existed, False otherwise."""
    # Check if key exists (looking at both transaction and main store)
    exists = self.get(key) is not None

    if self._transaction is not None:
        # Mark as deleted in the transaction
        self._transaction[key] = self._DELETED
    else:
        if key in self._store:
            del self._store[key]

    return exists

def begin(self) -> None:
    """Start a new transaction."""
    self._transaction = {}

def commit(self) -> None:
    """Save changes from the transaction."""
    if self._transaction is None:
        raise RuntimeError("No active transaction")

    # Move all changes to the main store
    for key, value in self._transaction.items():
        if value is self._DELETED:
            self._store.pop(key, None)
        else:
            self._store[key] = value

    self._transaction = None

def rollback(self) -> None:
    """Cancel the current transaction."""
    if self._transaction is None:
        raise RuntimeError("No active transaction")

    # Just throw away the transaction map
    self._transaction = None

`

Part 3: Nested Transactions

This required handling a stack of transactions. Each transaction layer would hold changes, and committing would merge changes into the parent transaction. The time complexity for begin and rollback is O(1). The time complexity for commit is O(t), where t is the number of keys changed in the transaction. The time complexity for get is O(d), where d is the depth of the stack (how many nested transactions there are). The time complexity for set and delete remains O(1). A follow-up question could be how to handle commit being called without begin, deleting missing keys, resurrecting keys, deep nesting, and calling begin then immediately commit.

` class Database: _DELETED = object()

def __init__(self):
    self._store: dict[str, str] = {}
    self._transaction_stack: list[dict[str, str | object]] = []

def _current_transaction(self) -> dict[str, str | object] | None:
    """Get the current (top) transaction layer, or None."""
    return self._transaction_stack[-1] if self._transaction_stack else None

def set(self, key: str, value: str) -> None:
    """Set key to value in the current transaction or global store."""
    current = self._current_transaction()
    if current is not None:
        current[key] = value
    else:
        self._store[key] = value

def get(self, key: str) -> str | None:
    """
    Find value by looking from the top transaction down to the store.
    """
    # Search stack from top (newest) to bottom (oldest)
    for transaction in reversed(self._transaction_stack):
        if key in transaction:
            value = transaction[key]
            if value is self._DELETED:
                return None
            return value

    # Look in the main store last
    return self._store.get(key)

def delete(self, key: str) -> bool:
    """Delete key in the current transaction."""
    exists = self.get(key) is not None

    current = self._current_transaction()
    if current is not None:
        current[key] = self._DELETED
    else:
        if key in self._store:
            del self._store[key]

    return exists

def begin(self) -> None:
    """Start a new nested transaction."""
    self._transaction_stack.append({})

def commit(self) -> None:
    """
    Commit the current transaction.
    - If nested: merge changes into the parent.
    - If outermost: save changes to global store.
    """
    if not self._transaction_stack:
        raise RuntimeError("No active transaction")

    current = self._transaction_stack.pop()

    if self._transaction_stack:
        # Merge into the parent transaction
        parent = self._transaction_stack[-1]
        for key, value in current.items():
            parent[key] = value
    else:
        # Save to the main store
        for key, value in current.items():
            if value is self._DELETED:
                self._store.pop(key, None)
            else:
                self._store[key] = value

def rollback(self) -> None:
    """Cancel the current transaction."""
    if not self._transaction_stack:
        raise RuntimeError("No active transaction")

    # Simply remove the top layer
    self._transaction_stack.pop()

`