Box·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Box technical phone screen for a software engineer role, one meaty design question that took up most of the time. The problem was interesting but I definitely underestimated how many edge cases were hiding in it.

Questions Asked (1)

Design and implement a single-machine in-memory key-value store that supports transactions, including nested transactions. It should support SET, GET, UNSET, BEGIN, COMMIT, and ROLLBACK operations, where nested BEGINs layer changes on top of each other, ROLLBACK discards only the most recent transaction's changes, and COMMIT flattens everything into the base store.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

I went straight to a stack of hashmaps and felt pretty good about it for the first five minutes.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a design using a stack of transaction layers where each layer is a map of key-value changes. Explain how each operation interacts with the stack, and discuss trade-offs between different implementation strategies.

Pro tip: Mention that you would use a stack of hash maps for active transactions and a separate base store, and that you can optimize reads by checking layers from top to bottom. Also, discuss how to handle edge cases like nested rollbacks and commits.

1. Clarify Requirements and Constraints

Ask about expected operations, concurrency, memory limits, and whether transactions need to be isolated. Confirm that nested transactions are supported and that rollback only affects the most recent transaction.

2. Design Data Structures

Propose using a base store (hash map) for committed data and a stack of transaction layers, each a hash map storing changes. For unset operations, use a sentinel value to mark deletion.

3. Define Operation Semantics

Explain how SET, GET, UNSET, BEGIN, COMMIT, and ROLLBACK work with the stack. For GET, search from top layer down to base; for COMMIT, merge top layer into the next layer or base; for ROLLBACK, pop the top layer.

4. Discuss Trade-offs and Optimizations

Compare approaches: stack of maps vs. single map with versioning. Discuss time/space complexity, and potential optimizations like lazy deletion or copy-on-write.

5. Handle Edge Cases and Testing

Mention edge cases: rollback with no active transaction, commit with no active transaction, nested transactions, and unset followed by set. Suggest unit tests for each operation.

Key Points to Mention

Use a stack of hash maps for transaction layers, with a base store for committed data.
GET searches from the topmost layer down to the base store.
COMMIT merges the top layer into the layer below (or base if only one layer).
ROLLBACK discards the top layer only.
UNSET can be implemented with a sentinel value to indicate deletion.
Time complexity: O(1) for SET/GET/UNSET in the current layer, O(depth) for GET across layers; COMMIT and ROLLBACK are O(size of top layer).

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