Design transactional in-memory key-value store

Q: Design transactional in-memory key-value store

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.

Q: 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.

Q: What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snowflake.

Q: What role is this question designed for?

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

Question

Design transactional in-memory key-value store

PracHub · Accepted Answer

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

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

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.

Quick Overview

Solution

Hints

Part 2: Transactional key-value store with nested transactions

Constraints

Examples

Solution

Hints

Part 3: Concurrent transactional key-value store

Constraints

Examples

Solution

Hints

Quick Overview