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.

Implement transactional key–value store | Applied Intuition Coding Question

Implement transactional key–value store

Company: Applied Intuition

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Design and implement an in-memory key–value store that supports transactions and nested transactional blocks. Your system must process a stream of commands and print results where applicable. Required commands and behavior: ( 1) SET <key> <value>: Assign value to key in the current context; the assignment should shadow any prior value of the same key in outer contexts. ( 2) GET <key>: Print the current value for key, or NULL if the key has no value in any active context. ( 3) BEGIN: Start a new transactional block; changes after this belong to the new inner transaction. ( 4) ROLLBACK: Discard all changes made in the most recent active transaction and revert to the parent context; if no active transaction exists, print NO TRANSACTION. ( 5) COMMIT: Merge all open transactions into the base state and end all transactions; if no active transaction exists, print NO TRANSACTION. Requirements: Support arbitrarily nested transactions; ensure that reads respect the most recent assignment within the active stack of contexts; handle reassignments of keys that existed before a transaction as well as keys introduced inside a transaction; define and justify the time/space complexity of each command for up to tens of thousands of operations. Provide a brief discussion comparing an explicit stack-based approach versus a recursive approach to represent nested transactions, and justify your implementation choice. Include a few example interactions demonstrating BEGIN/SET/GET/ROLLBACK/COMMIT behavior and edge cases (e.g., GET on unknown key, ROLLBACK/COMMIT with no open transaction).

Quick Answer: This question evaluates transactional state management, nested-scope semantics, and mutable key–value data structures, testing competencies in data structures, algorithms, and complexity analysis within the Coding & Algorithms domain.

Design an in-memory key-value store that processes a stream of commands. The store supports arbitrarily nested transactions. Commands: - SET <key> <value>: Assign the value to the key in the current context. - 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 active transaction. If there is no active transaction, return NO TRANSACTION. - COMMIT: Make all changes in all open transactions permanent and close every transaction. If there is no active transaction, return NO TRANSACTION. A value set inside an inner transaction must shadow values from outer transactions or the base store. Reads must always see the most recent visible assignment. For this problem, implement the store using an explicit stack-based transaction system. Compared with a recursive representation of nested transactions, an explicit stack avoids recursion-depth limits, keeps BEGIN/ROLLBACK/COMMIT iterative, and is simpler to reason about for tens of thousands of operations. Instead of printing results, return them as a list of strings in the order they would have been printed. Only GET, invalid ROLLBACK, and invalid COMMIT produce output. Assume keys and values are non-empty strings without spaces.

Constraints

1 <= len(commands) <= 50000
Keys and values are single tokens with no spaces
Transaction nesting can be arbitrarily deep within the command count limit
All commands are valid and use one of: SET, GET, BEGIN, ROLLBACK, COMMIT

Examples

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

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

Explanation: The first GET sees no value. After SET commands, GET returns the latest visible value.

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

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

Explanation: Inside the transaction, a is updated to 30. After rollback, it returns to the outer value 10.

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

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

Explanation: The inner rollback removes b, but a=20 from the outer transaction remains. COMMIT makes a=20 permanent.

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

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

Explanation: Both transaction operations are invalid with no active transaction, and x was never set.

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

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

Explanation: The inner rollback restores x from 4 back to 3. The outer rollback then restores the original base value 1.

Hints

Keep one dictionary for the currently visible values so GET can be answered in O(1) average time.
For each transaction, record a key's old value only the first time that key is changed inside that transaction.

Quick Overview

This question evaluates transactional state management, nested-scope semantics, and mutable key–value data structures, testing competencies in data structures, algorithms, and complexity analysis within the Coding & Algorithms domain.