Katkat
Back

Shopping Cart with Undo and Redo for Add and Remove Operations

DecagonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

A coding exercise to build a shopping cart class whose add and remove operations can be undone and redone. It tests how history entries are represented, how capped removals and deleted lines are reversed exactly, what a new change does to the redo history, and how empty-history cases are handled.

Implement a shopping cart that supports undo and redo.

The cart holds items and their quantities. A user can add items and remove items, undo their most recent changes one at a time, and redo changes they have just undone. Design the class and implement it.

Unless you agree on a different interface with the interviewer, assume these operations:

  • add_item(item_id, quantity) adds quantity units of an item, creating its line if the item is not in the cart yet.
  • remove_item(item_id, quantity) removes units of an item and deletes its line when the quantity reaches zero.
  • undo() reverts the most recent change that has not already been undone.
  • redo() reapplies the most recently undone change.
  • items() returns the current contents as a mapping from item ID to quantity.

Constraints and Clarifications

  • Item IDs are strings and quantities are positive integers.
  • As a starting point the cart tracks only item IDs and their quantities.

Clarifying Questions

  • After an undo, if the user makes a new change, can the undone changes still be redone?
  • If remove_item asks for more units than the cart holds, is that an error, or does it remove the whole line? What should undo restore afterward?
  • Is remove_item without a quantity allowed, meaning "remove the whole line"?
  • What should undo and redo do when there is nothing to undo or redo: nothing, return a flag, or raise an error?
  • Should a failed operation, such as removing an item that is not in the cart, appear in the history?
  • Is the history unbounded, or should only the last N changes be undoable?
  • Do prices, discounts or a cart total need to be tracked, and should undo cover them too?

Hints

Hint 1

Decide what a history entry holds: For each change, decide what you must remember so that it can be reversed exactly and reapplied exactly, including a removal that deletes a whole line.

Hint 2

Trace a branching history: Trace add, add, undo, then a brand-new add. Decide what `redo` should do next, and make your data structures enforce that answer.

Follow-up questions

  • Users can now set an item's quantity directly or apply a coupon. How do you add those operations without changing how undo and redo work?
  • One user action, such as adding a bundle, changes several lines. How do you undo it as a single step?
  • Memory must be capped so that only the last N changes can be undone. Which data structure and eviction rule do you use?
  • The same cart is edited from a phone and a laptop at the same time. What should undo mean then?