Shopping Cart with Undo and Redo for Add and Remove Operations

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. ```hint 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 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. ``` ### 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? ### What a Strong Answer Covers - A deliberate choice of history representation (reversible change records or full snapshots) and its memory cost - Exact reversal of every change, including a removal that deletes a line and a removal capped at the quantity present - Correct redo behavior, including what a new change does to changes that were undone - Defined behavior for invalid operations and for undo or redo with an empty history - Constant time per operation, or a justified alternative, and tests that compare random operation sequences against a simple reference model ### 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?