# Design a Space-Efficient Versioned Recipe Shopping Cart Design an in-memory shopping cart for a cooking app. Each recipe has an ID and a list of ingredient quantities. The cart supports `add_recipe`, `remove_recipe`, and `get_total_discounts`; ingredient quantities are aggregated across all recipes before a supplied discount-policy function is evaluated. Every successful cart mutation creates a new integer version. `get_version` returns the current version. Calling `checkout(v)` restores version `v` as the current cart and permanently discards all later versions. ### Constraints & Assumptions - Version 0 is the empty cart. - Recipe IDs are unique within the cart; define behavior for duplicate add and absent remove. - The discount policy is deterministic and depends only on aggregate ingredient quantities. - Checkout accepts only an existing version from the current history. - Storing a full copy of the cart for every version is considered too expensive. ### Clarifying Questions to Ask - Must reads at arbitrary historical versions be supported, or only checkout to a version? - How many operations and recipes should fit in memory? - May a previously discarded version number ever be reused? - Is thread safety required? ### Part 1: Current Cart and Discounts Define the data structures and invariants used to add and remove recipes and compute aggregate ingredient counts and discounts. #### What This Part Should Cover - Recipe membership plus incrementally maintained ingredient totals. - Atomic validation and mutation for add/remove operations. - Clear separation between cart state and the injected discount policy. ### Part 2: Versions and Checkout Design a space-efficient history based on operations rather than complete snapshots, and explain how checkout restores a selected version and discards its future. #### What This Part Should Cover - An append-only operation prefix for the live timeline. - Replay or inverse operations to reconstruct the target state. - Truncation semantics and version identity after branching. - Time and space complexity, including optional checkpoints. ### What a Strong Answer Covers - Correct current-state invariants for recipes, aggregate ingredients, and discounts. - Versions tied to successful mutations, with explicit invalid-operation behavior. - A history representation substantially smaller than full snapshots for ordinary mutations. - Safe checkout, future truncation, tests, and honest replay-versus-memory trade-offs. ### Follow-up Questions - How would periodic checkpoints change checkout complexity? - How would you make checkout atomic if the cart were persisted? - How would collaborative cart edits change the version model?