PracHub
QuestionsPremiumLearningGuidesCheatsheetNEW

Quick Overview

This question evaluates understanding of in-memory key–value store semantics, transactional and nested transaction behavior, and practical competencies in hash-based data structures and thread-safety for concurrent access.

  • hard
  • Snowflake
  • Coding & Algorithms
  • Software Engineer

Design transactional in-memory key-value store

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## Problem Design and implement an **in-memory key–value store** that supports basic operations plus **transactions**. ### Core API Implement the following operations: - `get(key) -> value | null` Return the current value for `key`, or `null`/`None` if it does not exist. - `put(key, value)` Set `key` to `value`. - `delete(key)` Remove `key` if it exists. ### Follow-up 1: Transactions (must support nested) Add transactional operations: - `begin()` — starts a new transaction scope (transactions may be nested). - `commit() -> bool` — commits the **current** transaction. - Returns `false` (or throws) if there is no active transaction. - `rollback() -> bool` — rolls back the **current** transaction. - Returns `false` (or throws) if there is no active transaction. After `commit`, changes in the committed transaction become visible in the parent transaction (or globally if committing the outermost transaction). After `rollback`, all changes made since the last `begin()` are undone. **Complexity requirement:** Each operation should run in **O(1)** time on average (constant-time hash operations allowed). You may assume keys and values fit in memory. ### Follow-up 2: Concurrency Extend your design to support **multi-threaded** access: - Multiple threads may call `get/put/delete/begin/commit/rollback` concurrently. - Describe the thread-safety guarantees you provide (e.g., linearizability vs. weaker consistency) and what synchronization approach you would use. ### Notes - Clarify how `delete` interacts with transactions (e.g., deleting a key inside a transaction should be reversible by rollback). - Be prepared to discuss edge cases such as committing/rolling back with no active transaction and nested transactions.

Quick Answer: This question evaluates understanding of in-memory key–value store semantics, transactional and nested transaction behavior, and practical competencies in hash-based data structures and thread-safety for concurrent access.

Part 1: Basic in-memory key-value store

Process a sequence of operations on an initially empty in-memory key-value store. Support put(key, value), get(key), and delete(key). Return the results of all get operations in order. Deleting a missing key should do nothing.

Constraints

  • 0 <= len(operations) <= 200000
  • Keys are strings of length 1 to 100
  • Values are integers and are never None
  • All operations are valid

Examples

Input: [('put', 'a', 1), ('get', 'a'), ('put', 'a', 2), ('get', 'a'), ('delete', 'a'), ('get', 'a')]

Expected Output: [1, 2, None]

Explanation: The value for 'a' is updated from 1 to 2, then deleted.

Input: [('get', 'missing'), ('delete', 'missing'), ('get', 'missing')]

Expected Output: [None, None]

Explanation: Getting a missing key returns None, and deleting a missing key is a no-op.

Input: []

Expected Output: []

Explanation: Edge case: no operations means no outputs.

Input: [('put', 'x', 10), ('put', 'y', 20), ('delete', 'x'), ('get', 'x'), ('get', 'y')]

Expected Output: [None, 20]

Explanation: After deleting 'x', only 'y' remains.

Solution

def solution(operations):
    store = {}
    result = []

    for op in operations:
        cmd = op[0]
        if cmd == 'put':
            _, key, value = op
            store[key] = value
        elif cmd == 'get':
            _, key = op
            result.append(store.get(key, None))
        elif cmd == 'delete':
            _, key = op
            store.pop(key, None)

    return result

Time complexity: O(n) total for n operations. Space complexity: O(u), where u is the number of keys currently stored.

Hints

  1. A Python dict supports average O(1) get, set, and delete.
  2. Only 'get' operations add something to the output list.

Part 2: Transactional key-value store with nested transactions

Implement a single-threaded in-memory key-value store with nested transactions. The store starts empty. Support put, get, delete, begin, commit, and rollback. Writes inside a transaction are visible to later operations immediately, but rollback must undo only the changes made since the matching begin. Nested transactions are allowed. Return the results of all get, commit, and rollback operations in order. If there is no active transaction, commit and rollback must return False.

Constraints

  • 0 <= len(operations) <= 200000
  • Maximum nested transaction depth is at most len(operations)
  • Keys are strings of length 1 to 100
  • Values are integers and are never None
  • All operations are valid

Examples

Input: [('put', 'a', 1), ('begin',), ('put', 'a', 2), ('get', 'a'), ('begin',), ('delete', 'a'), ('get', 'a'), ('rollback',), ('get', 'a'), ('commit',), ('get', 'a')]

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

Explanation: The inner delete is rolled back, so 'a' becomes 2 again. The outer commit keeps that value.

Input: [('commit',), ('rollback',), ('get', 'x')]

Expected Output: [False, False, None]

Explanation: Edge case: there is no active transaction to commit or roll back.

Input: [('put', 'k', 5), ('begin',), ('delete', 'k'), ('get', 'k'), ('rollback',), ('get', 'k')]

Expected Output: [None, True, 5]

Explanation: Deleting inside a transaction is reversible after rollback.

Input: [('put', 'x', 1), ('begin',), ('put', 'x', 2), ('begin',), ('put', 'x', 3), ('commit',), ('get', 'x'), ('rollback',), ('get', 'x')]

Expected Output: [True, 3, True, 1]

Explanation: The inner commit keeps x=3 inside the parent transaction, but rolling back the parent restores x=1.

Input: []

Expected Output: []

Explanation: Edge case: no operations.

Solution

def solution(operations):
    store = {}
    tx_stack = []
    result = []

    for op in operations:
        cmd = op[0]

        if cmd == 'begin':
            tx_stack.append({})

        elif cmd == 'put':
            _, key, value = op
            if tx_stack:
                log = tx_stack[-1]
                if key not in log:
                    log[key] = (key in store, store.get(key))
                store[key] = value
            else:
                store[key] = value

        elif cmd == 'delete':
            _, key = op
            if tx_stack:
                log = tx_stack[-1]
                if key not in log:
                    log[key] = (key in store, store.get(key))
                store.pop(key, None)
            else:
                store.pop(key, None)

        elif cmd == 'get':
            _, key = op
            result.append(store.get(key, None))

        elif cmd == 'commit':
            if not tx_stack:
                result.append(False)
            else:
                log = tx_stack.pop()
                if tx_stack:
                    parent = tx_stack[-1]
                    for key, old_state in log.items():
                        if key not in parent:
                            parent[key] = old_state
                result.append(True)

        elif cmd == 'rollback':
            if not tx_stack:
                result.append(False)
            else:
                log = tx_stack.pop()
                for key, (had_key, old_value) in log.items():
                    if had_key:
                        store[key] = old_value
                    else:
                        store.pop(key, None)
                result.append(True)

    return result

Time complexity: get/put/delete/begin are O(1) average; commit and rollback are O(k), where k is the number of distinct keys changed in the current transaction. Space complexity: O(u + p), where u is the number of keys in the current visible store and p is the total number of keys recorded in active transaction logs.

Hints

  1. When a transaction first changes a key, record what that key looked like before the change.
  2. On nested commit, the current visible state should stay as-is; only the undo information needs to be merged upward.

Part 3: Concurrent transactional key-value store

Simulate a concurrent transactional key-value store under linearizable global-lock semantics. The operations are already listed in the exact atomic order in which they take effect, so your job is to process them in that order. Each thread has its own nested transaction stack. A thread can see its own uncommitted changes, but other threads cannot see them until the outermost commit. If a thread has no active transaction, put and delete update the shared global store immediately. Reads inside a transaction first check that thread's own transaction layers from newest to oldest, then the latest committed global store. This model is not snapshot isolation: if another thread commits later, future reads can observe that new global value unless the current thread has shadowed the key in its own transaction.

Constraints

  • 0 <= len(operations) <= 200000
  • 1 <= number of distinct thread IDs <= 100000
  • Maximum nested transaction depth per thread is at most len(operations)
  • Keys are strings of length 1 to 100
  • Values are integers and are never None
  • All operations are valid and should be processed exactly in the given order

Examples

Input: [('put', 1, 'x', 1), ('begin', 2), ('get', 2, 'x'), ('put', 2, 'x', 5), ('get', 2, 'x'), ('get', 1, 'x'), ('commit', 2), ('get', 1, 'x')]

Expected Output: [1, 5, 1, True, 5]

Explanation: Thread 2 sees its own uncommitted write, while thread 1 does not see it until thread 2 commits.

Input: [('begin', 1), ('put', 1, 'a', 10), ('begin', 1), ('delete', 1, 'a'), ('get', 1, 'a'), ('get', 2, 'a'), ('rollback', 1), ('get', 1, 'a'), ('commit', 1), ('get', 2, 'a')]

Expected Output: [None, None, True, 10, True, 10]

Explanation: The inner delete is visible only to thread 1 and is undone by rollback. After the outer commit, thread 2 can see the value.

Input: [('commit', 3), ('rollback', 3), ('put', 1, 'k', 7), ('delete', 2, 'k'), ('get', 1, 'k')]

Expected Output: [False, False, None]

Explanation: Edge case: thread 3 has no active transaction. Thread 2 deletes 'k' globally because it is not inside a transaction.

Input: [('begin', 1), ('put', 1, 'x', 2), ('begin', 1), ('put', 1, 'x', 3), ('commit', 1), ('get', 1, 'x'), ('get', 2, 'x'), ('rollback', 1), ('get', 1, 'x')]

Expected Output: [True, 3, None, True, None]

Explanation: The child commit merges into thread 1's parent transaction, but thread 2 still cannot see the value until the outermost commit.

Input: [('put', 1, 'v', 1), ('begin', 2), ('get', 2, 'v'), ('delete', 1, 'v'), ('get', 2, 'v')]

Expected Output: [1, None]

Explanation: This shows the model is not snapshot isolation: thread 2 begins before the delete, but a later read still sees the latest global committed state.

Solution

def solution(operations):
    TOMBSTONE = object()
    global_store = {}
    stacks = {}
    result = []

    def read_value(tid, key):
        layers = stacks.get(tid, [])
        for layer in reversed(layers):
            if key in layer:
                return None if layer[key] is TOMBSTONE else layer[key]
        return global_store.get(key, None)

    for op in operations:
        cmd = op[0]

        if cmd == 'begin':
            _, tid = op
            stacks.setdefault(tid, []).append({})

        elif cmd == 'put':
            _, tid, key, value = op
            layers = stacks.get(tid, [])
            if layers:
                layers[-1][key] = value
            else:
                global_store[key] = value

        elif cmd == 'delete':
            _, tid, key = op
            layers = stacks.get(tid, [])
            if layers:
                layers[-1][key] = TOMBSTONE
            else:
                global_store.pop(key, None)

        elif cmd == 'get':
            _, tid, key = op
            result.append(read_value(tid, key))

        elif cmd == 'commit':
            _, tid = op
            layers = stacks.get(tid, [])
            if not layers:
                result.append(False)
            else:
                current = layers.pop()
                if layers:
                    layers[-1].update(current)
                else:
                    for key, value in current.items():
                        if value is TOMBSTONE:
                            global_store.pop(key, None)
                        else:
                            global_store[key] = value
                if not layers:
                    stacks.pop(tid, None)
                result.append(True)

        elif cmd == 'rollback':
            _, tid = op
            layers = stacks.get(tid, [])
            if not layers:
                result.append(False)
            else:
                layers.pop()
                if not layers:
                    stacks.pop(tid, None)
                result.append(True)

    return result

Time complexity: A get is O(d) for transaction depth d of that thread; a commit is O(k) for the number of keys in the committed layer; all other operations are O(1) average. Space complexity: O(u + p), where u is the number of committed keys in the global store and p is the total number of pending key updates across all active thread-local transaction layers.

Hints

  1. Keep one transaction stack per thread ID, plus one shared committed store.
  2. For a read, only the calling thread's own transaction layers matter before you fall back to the shared committed store.
Last updated: Apr 25, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Solve Array Distance and Wiki Navigation - Snowflake (medium)
  • Implement Document Predicate APIs - Snowflake (medium)
  • Find Shortest Wiki Click Path - Snowflake (medium)
  • Schedule prerequisite classes with retakes - Snowflake (easy)
  • Solve three coding rounds - Snowflake (medium)