Applied intuition·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026

Summary

Applied Intuition coding round, one meaty design-and-implement question about a transactional key-value store. The problem sounds manageable until you get into nested transactions and the edge cases start piling up.

Questions Asked (1)

Build an in-memory key-value store that supports nested transactions with SET, RETURN (read), BEGIN, APPLY (commit to parent), and DISCARD (rollback). Reads and writes should reflect the most recent value in the current transaction context. Walk through your data structures, API design, time/space complexity, and edge cases like reading an unset key or calling APPLY with no active transaction.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

My first instinct was a stack of hashmaps, one per transaction layer, and reads walk up the stack until they find the key.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and defining the API, then propose a stack of hash maps where each transaction layer holds its own writes and reads fall through to parent layers. Walk through operations with complexity analysis, and explicitly cover edge cases like unset keys and invalid APPLY/DISCARD calls.

Pro tip: Emphasize that reads must check the current transaction first, then fall through to parents, and that APPLY merges changes into the parent without copying the entire store—this shows you understand both correctness and efficiency.

1. Clarify requirements and API

Confirm operations (SET, RETURN, BEGIN, APPLY, DISCARD), expected behavior for edge cases, and whether RETURN should indicate missing keys. Define method signatures and error handling.

2. Design data structures

Propose a stack of hash maps (one per active transaction) plus a base map for the committed state. Each transaction layer stores only its own writes; reads traverse from top to bottom.

3. Walk through operations

Explain how SET writes to the top layer, RETURN searches layers top-down, BEGIN pushes a new empty map, APPLY merges the top map into the one below and pops, and DISCARD simply pops.

4. Analyze complexity and trade-offs

State time complexity: O(1) for SET, O(depth) for RETURN, O(size of top layer) for APPLY, O(1) for BEGIN/DISCARD. Space is O(total distinct keys written across active transactions). Discuss alternatives like copy-on-write or persistent maps.

5. Cover edge cases and error handling

Address reading an unset key (return null/error), APPLY/DISCARD with no active transaction (throw error or no-op), nested transactions, and overwriting keys in parent layers.

Key Points to Mention

Stack of hash maps for transaction layers, with reads falling through to parents
SET writes only to the current transaction layer; RETURN checks current then parents
APPLY merges the top layer into the parent and pops; DISCARD pops without merging
Time complexity: O(1) SET, O(depth) RETURN, O(size of top layer) APPLY
Edge cases: reading unset key, APPLY/DISCARD with no active transaction, nested transactions
Trade-offs: memory vs. speed, alternative designs like copy-on-write or persistent data structures

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.