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 Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Applied Intuition.

What role is this question designed for?

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

Design a transactional in-memory key–value store | Applied Intuition Coding Question

Quick Overview

This question evaluates understanding of transactional state management, nested transaction semantics, scope shadowing, and efficient data-structure design for an in-memory key–value store, assessing competency in correctness, consistency, and algorithmic complexity under nested BEGIN/ROLLBACK/COMMIT operations.

Design a transactional in-memory key–value store

Company: Applied Intuition

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Implement an in-memory key–value store that supports transactions. The system must process these commands: ( 1) SET key value — assign or overwrite a key; ( 2) GET key — print the current value or NULL if absent; ( 3) BEGIN — start a new transaction block; ( 4) ROLLBACK — revert all changes made in the most recent open transaction; ( 5) COMMIT — persist all open transactions so they can no longer be rolled back. Requirements: support arbitrarily nested transactions; allow multiple reassignments of the same key within the same or nested transactions, ensuring reads always see the most recent value within the active transactional context; handle shadowing of values across nested scopes; and ensure ROLLBACK restores prior values correctly. Define the core data structures (e.g., a main map plus a stack of change logs or another efficient scheme), describe the algorithms for each command, and explain the trade-offs between iterative stack-based management and a recursive approach. Specify time and space complexities for each operation, and handle edge cases such as ROLLBACK or COMMIT when no transaction is active and GET on a missing key. Provide a brief example interaction demonstrating correctness across nested BEGIN/ROLLBACK/COMMIT operations.

Quick Answer: This question evaluates understanding of transactional state management, nested transaction semantics, scope shadowing, and efficient data-structure design for an in-memory key–value store, assessing competency in correctness, consistency, and algorithmic complexity under nested BEGIN/ROLLBACK/COMMIT operations.

Implement an in-memory key-value store that processes a list of commands. The store must support arbitrarily nested transactions. Commands: - SET key value: assign or overwrite a key with the given value. - GET key: return the current visible value for the key, or "NULL" if the key does not exist. - BEGIN: start a new transaction block. - ROLLBACK: undo all changes made in the most recent open transaction. - COMMIT: make all currently open transactions permanent so they can no longer be rolled back. Your function should return a list of outputs produced by commands that generate output: - each GET contributes one string result; - ROLLBACK and COMMIT contribute "NO TRANSACTION" if no transaction is active; - successful SET, BEGIN, ROLLBACK, and COMMIT produce no output. Requirements: - Reads must always see the most recent value in the active transactional context. - Multiple reassignments of the same key in the same transaction must roll back correctly. - Nested transactions must correctly shadow parent values. - After COMMIT, all open transactions are persisted at once. Recommended design: use one main map for the current visible state, plus a stack of change logs. Each change log records the original value of a key the first time that key is modified in that transaction. This iterative stack-based approach avoids copying the whole store on BEGIN and is safer than a recursive design for deep nesting because it avoids recursion depth limits. Example interaction: SET a 10 BEGIN SET a 20 BEGIN SET a 30 GET a -> 30 ROLLBACK GET a -> 20 COMMIT GET a -> 20

Constraints

0 <= len(commands) <= 200000
Each command is valid and uses one of the five supported operations
Keys and values contain no spaces
Average-case hash map operations may be assumed to be O(1)

Examples

Input: (["SET a 10", "GET a", "GET b"],)

Expected Output: ["10", "NULL"]

Explanation: Key a is stored with value 10. Key b was never set, so GET b returns NULL.

Input: (["SET a 10", "BEGIN", "SET a 20", "BEGIN", "SET b 30", "GET a", "GET b", "ROLLBACK", "GET b", "GET a", "COMMIT", "ROLLBACK", "GET a"],)

Expected Output: ["20", "30", "NULL", "20", "NO TRANSACTION", "20"]

Explanation: The inner transaction adds b=30 and is rolled back, so b disappears. The outer transaction keeps a=20. COMMIT makes that permanent, so a later ROLLBACK fails with NO TRANSACTION.

Input: (["SET x 1", "BEGIN", "SET x 2", "SET x 3", "BEGIN", "SET x 4", "GET x", "ROLLBACK", "GET x", "ROLLBACK", "GET x"],)

Expected Output: ["4", "3", "1"]

Explanation: Within the outer transaction, x changes from 1 to 2 to 3. The inner transaction temporarily changes x to 4, then rolls back to 3. Rolling back the outer transaction restores x to its original value 1.

Input: (["GET z", "ROLLBACK", "COMMIT"],)

Expected Output: ["NULL", "NO TRANSACTION", "NO TRANSACTION"]

Explanation: GET on a missing key returns NULL. With no active transaction, both ROLLBACK and COMMIT return NO TRANSACTION.

Input: ([],)

Expected Output: []

Explanation: An empty command list produces no output.

Solution

def solution(commands):
    store = {}
    tx_stack = []
    outputs = []
    MISSING = object()

    for command in commands:
        parts = command.split()
        op = parts[0]

        if op == "SET":
            key, value = parts[1], parts[2]
            if tx_stack and key not in tx_stack[-1]:
                tx_stack[-1][key] = store.get(key, MISSING)
            store[key] = value

        elif op == "GET":
            key = parts[1]
            outputs.append(store.get(key, "NULL"))

        elif op == "BEGIN":
            tx_stack.append({})

        elif op == "ROLLBACK":
            if not tx_stack:
                outputs.append("NO TRANSACTION")
            else:
                changes = tx_stack.pop()
                for key, old_value in changes.items():
                    if old_value is MISSING:
                        store.pop(key, None)
                    else:
                        store[key] = old_value

        elif op == "COMMIT":
            if not tx_stack:
                outputs.append("NO TRANSACTION")
            else:
                tx_stack.clear()

    return outputs

Time complexity: O(n) total for n commands on average; SET, GET, BEGIN, and COMMIT are O(1) average, while ROLLBACK is O(k) where k is the number of distinct keys changed in the most recent transaction.. Space complexity: O(m + c), where m is the number of keys currently stored and c is the total number of first-change log entries across all open transactions..

Hints

Do not copy the entire database on every BEGIN. Store only what changes in each transaction.
When a key is set multiple times in the same transaction, log its previous value only the first time it changes in that transaction.

Quick Overview