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 Onsite 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 nested transaction store | Applied Intuition Coding Question

Design a nested transaction store

Company: Applied Intuition

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Implement an in-memory key–value store that supports nested transactions with the operations: SET key value, RETURN key, BEGIN, APPLY (commit current transaction into its parent), and DISCARD (rollback current transaction). Reads and writes should reflect the most recent value visible in the current transactional context. Transactions can be arbitrarily nested. Example sequence: SET X=20; BEGIN; BEGIN; SET X=10; RETURN X; APPLY; DISCARD; RETURN X. The first RETURN should yield 10 and the second 20. Describe the data structures, APIs, and the time/space complexity of each operation, and consider edge cases (e.g., RETURN on unset keys, APPLY/DISCARD with no active transaction).

Quick Answer: This question evaluates understanding of transactional state management, nested transaction semantics, scope resolution, and data-structure design for an in-memory key–value store.

Implement an in-memory key-value store that supports arbitrarily nested transactions. You are given a list of commands and must execute them in order. Commands: - ('SET', key, value): Store an integer value for key in the current transaction if one exists; otherwise store it in the base store. - ('RETURN', key): Read the most recent visible value for key from the current transaction scope. Search from the innermost active transaction outward, then the base store. If the key has never been set, output None. - ('BEGIN',): Start a new empty transaction. - ('APPLY',): Commit the current transaction into its parent context and remove it. If it is the outermost transaction, commit into the base store. If there is no active transaction, output 'NO TRANSACTION'. - ('DISCARD',): Roll back the current transaction and remove it. If there is no active transaction, output 'NO TRANSACTION'. Return a list containing every value produced by RETURN, plus 'NO TRANSACTION' for invalid APPLY or DISCARD operations, in the order they occur. Example: SET X=20; BEGIN; BEGIN; SET X=10; RETURN X; APPLY; DISCARD; RETURN X The outputs are [10, 20].

Constraints

0 <= len(commands) <= 10^4
Keys are non-empty strings of length at most 20
Values are integers in the range [-10^9, 10^9]
Transactions may be nested arbitrarily within the command list

Examples

Input: [('SET', 'X', 20), ('BEGIN',), ('BEGIN',), ('SET', 'X', 10), ('RETURN', 'X'), ('APPLY',), ('DISCARD',), ('RETURN', 'X')]

Expected Output: [10, 20]

Explanation: The inner transaction changes X to 10, so the first RETURN sees 10. APPLY merges that change into its parent transaction. DISCARD then rolls back the parent transaction, so the base value 20 is visible again.

Input: [('RETURN', 'A'), ('APPLY',), ('DISCARD',)]

Expected Output: [None, 'NO TRANSACTION', 'NO TRANSACTION']

Explanation: A was never set, so RETURN gives None. There is no active transaction for APPLY or DISCARD, so both produce 'NO TRANSACTION'.

Input: [('BEGIN',), ('SET', 'A', 5), ('BEGIN',), ('SET', 'A', 7), ('APPLY',), ('RETURN', 'A'), ('APPLY',), ('RETURN', 'A')]

Expected Output: [7, 7]

Explanation: The inner transaction sets A to 7 and APPLY merges it into the outer transaction. The next RETURN sees 7. Applying the outer transaction commits 7 to the base store, so the final RETURN is also 7.

Input: [('SET', 'A', 1), ('BEGIN',), ('SET', 'B', 2), ('BEGIN',), ('RETURN', 'A'), ('RETURN', 'B'), ('RETURN', 'C'), ('DISCARD',), ('RETURN', 'B')]

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

Explanation: Inside the nested transaction, A is found in the base store and B is found in the parent transaction. C is unset, so it returns None. Discarding only the inner transaction keeps B=2 visible from the outer transaction.

Input: []

Expected Output: []

Explanation: No commands means no outputs.

Solution

def solution(commands):
    base = {}
    tx_stack = []
    outputs = []

    for cmd in commands:
        op = cmd[0]

        if op == 'SET':
            _, key, value = cmd
            if tx_stack:
                tx_stack[-1][key] = value
            else:
                base[key] = value

        elif op == 'RETURN':
            _, key = cmd
            for layer in reversed(tx_stack):
                if key in layer:
                    outputs.append(layer[key])
                    break
            else:
                outputs.append(base.get(key))

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

        elif op == 'APPLY':
            if not tx_stack:
                outputs.append('NO TRANSACTION')
            else:
                top = tx_stack.pop()
                if tx_stack:
                    tx_stack[-1].update(top)
                else:
                    base.update(top)

        elif op == 'DISCARD':
            if not tx_stack:
                outputs.append('NO TRANSACTION')
            else:
                tx_stack.pop()

        else:
            raise ValueError(f'Unknown operation: {op}')

    return outputs

Time complexity: Per operation: SET/BEGIN/DISCARD are O(1), RETURN is O(d) where d is the current transaction depth, and APPLY is O(k) where k is the number of keys written in the current transaction.. Space complexity: O(n + u), where n is the number of keys stored in the base store and u is the total number of uncommitted key assignments across active transactions..

Hints

Think of each BEGIN as pushing a new write layer onto a stack.
For RETURN, check the newest transaction first and work outward until you find the key.

Quick Overview

This question evaluates understanding of transactional state management, nested transaction semantics, scope resolution, and data-structure design for an in-memory key–value store.