← Decagon Interview Insights

Decagon·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate
Jun 2026

Summary

Decagon software engineer interview, part of what looks like a multi-part coding assessment. This section was all about implementing undo/redo on a shopping cart, which sounds manageable until you actually have to think through the edge cases.

Questions Asked (1)

Q1

Implement undo and redo functionality for a shopping cart system, where performing a new operation resets the redo history, and get_total_discount() always reflects the current state.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The basic stack approach for undo/redo clicked pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use two stacks (undo and redo) to track operations, where each operation records enough information to reverse its effect on the cart state. When a new operation is performed, clear the redo stack. Ensure get_total_discount() computes the discount from the current cart state, not from a cached value, so it always reflects the latest state.

Pro tip: Mention that you would encapsulate each operation as a command object with do/undo methods, which makes the system extensible and testable. Also, discuss the trade-off between storing full state snapshots versus deltas, and why deltas are more memory-efficient for a shopping cart.

1. Clarify requirements and constraints

Ask about the types of operations (add item, remove item, apply discount, etc.), whether operations can be grouped, and if there are memory constraints. Confirm that get_total_discount() should be computed on demand.

2. Design the data structures

Propose using two stacks: one for undo and one for redo. Each stack stores operation objects that encapsulate the necessary data to reverse or reapply the operation.

3. Define the operation interface

Create a Command interface with execute() and undo() methods. Each concrete operation (e.g., AddItemCommand) implements these methods to modify the cart state.

4. Implement undo/redo logic

On a new operation, execute it, push it onto the undo stack, and clear the redo stack. For undo, pop from undo stack, call undo(), and push onto redo stack. For redo, pop from redo stack, call execute(), and push back onto undo stack.

5. Ensure get_total_discount() reflects current state

Implement get_total_discount() to calculate the discount based on the current items and applied discounts in the cart, avoiding any cached values that could become stale after undo/redo.

Key Points to Mention

  • Use of two stacks for undo and redo, with redo stack cleared on new operations.
  • Command pattern to encapsulate operations, making undo/redo extensible and maintainable.
  • Trade-off between storing full state snapshots vs. operation deltas (memory vs. simplicity).
  • Ensuring get_total_discount() is computed from current state, not cached, to reflect undo/redo changes.
  • Handling edge cases: undo/redo when stacks are empty, operations that affect multiple items, and concurrency if applicable.
  • Testing strategy: unit tests for each command, integration tests for undo/redo sequences, and verifying discount calculation after each operation.

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