Skip to content

Versioned Shopping Cart

Published 3 October 2026

A phone-screen question in two parts. Part 1 is a cart with ingredient-level bulk discounts. Part 2 adds versioning, and the follow-up that matters is space: how do you keep every version without copying the whole cart each time?

Problem statement

Phone Screen 1 — Versioned Shopping Cart

You are building a shopping cart for a cooking application. Users add recipes to the cart, and each recipe contains a list of ingredients. When an ingredient appears across multiple recipes, its combined quantity may qualify for a bulk discount.

The first part required operations conceptually similar to:

add_recipe(recipe)
remove_recipe(recipe)
get_total_discounts()

The system should update the cart as recipes are added or removed and calculate the applicable ingredient-level discounts.

Part 2 — Cart Versions and Checkout

The second part introduced versioning. Every operation that modifies the cart creates a new version of its state.

For example:

Version 0: {}
add RecipeX
Version 1: {RecipeX}
add RecipeY
Version 2: {RecipeX, RecipeY}

The system then adds:

get_version(version)
checkout(version)

get_version() should allow a previous cart state to be accessed by version. checkout(version) makes the selected historical version the active checkout point and discards every version created after it.

Using the example above checkout(1) would retain the state containing only RecipeX, while Version 2 would no longer remain part of the valid version history. A major follow-up was space efficiency. The interviewer did not want every complete cart snapshot duplicated for every version, so the discussion focused on how version history could be represented without copying the entire cart after each operation.

Pinning down the vague parts

The prompt leaves several things open. These are the questions to ask in the first couple of minutes, with the answers I'm assuming:

  • What does a discount look like? Each ingredient has bulk tiers such as "500 g of flour or more: 50¢ off; 1,000 g or more: $1.50 off". The highest tier the combined quantity reaches applies. Money is integer cents, never floats.
  • Can a recipe be added twice? Yes. The cart holds counts, so two lasagnes double every ingredient.
  • What does removing a recipe that isn't there do? It raises KeyError and creates no version. Only successful changes get a version number.
  • Is a recipe identified by name? Yes, and reusing a name with different ingredients is an error. Otherwise "remove lasagne" would be ambiguous.
  • After checkout(1), what number does the next change get? Version 2. The old version 2 is gone, so the number is free again.

Part 1: discounts without recomputing everything

The naive get_total_discounts() sums every ingredient across every recipe, then looks up every ingredient's tier: O(cart size) per call.

Instead, keep the combined quantity of each ingredient and a running total. Adding or removing a recipe touches only that recipe's ingredients. For each one, take off its old discount, change the quantity, and add the new discount:

from bisect import bisect_right
from collections import Counter
from dataclasses import dataclass


@dataclass(frozen=True)
class Recipe:
    name: str
    ingredients: tuple  # ((ingredient, quantity), ...)


class Discounts:
    """Bulk tiers per ingredient. The highest tier the combined quantity reaches applies."""

    def __init__(self, tiers):
        # {ingredient: [(min_quantity, discount_cents), ...]}
        self.tiers = {name: sorted(t) for name, t in tiers.items()}

    def for_quantity(self, ingredient, quantity):
        tiers = self.tiers.get(ingredient, [])
        i = bisect_right(tiers, (quantity, float("inf"))) - 1
        return tiers[i][1] if i >= 0 else 0


class Cart:
    def __init__(self, discounts):
        self.discounts = discounts
        self.recipes = Counter()     # recipe name -> copies in the cart
        self.quantities = Counter()  # ingredient -> combined quantity
        self.total_discount = 0

    def apply(self, recipe, sign):
        """Add (sign=+1) or remove (sign=-1) one copy of a recipe."""
        self.recipes[recipe.name] += sign
        if not self.recipes[recipe.name]:
            del self.recipes[recipe.name]
        for ingredient, quantity in recipe.ingredients:
            before = self.discounts.for_quantity(ingredient, self.quantities[ingredient])
            self.quantities[ingredient] += sign * quantity
            if not self.quantities[ingredient]:
                del self.quantities[ingredient]
            after = self.discounts.for_quantity(ingredient, self.quantities[ingredient])
            self.total_discount += after - before

    def copy(self):
        c = Cart(self.discounts)
        c.recipes = self.recipes.copy()
        c.quantities = self.quantities.copy()
        c.total_discount = self.total_discount
        return c

add_recipe and remove_recipe cost O(I), where I is the number of ingredients in the recipe, and get_total_discounts() is O(1). Each tier lookup is a binary search over that ingredient's tiers, which is a handful of entries.

Part 2: versions

There are four standard ways to store a history of states. They trade space against how fast you can read an old version:

Approach Space for V versions get_version(v)
Full snapshot per version O(V × cart) O(1) lookup, O(cart) to copy it out
Log of changes only O(V) O(v): replay from version 0
Log plus a snapshot every K versions O(V + V/K × cart) O(cart + K)
Persistent data structure O(V × log cart) O(1)

The full snapshot is what the interviewer ruled out. A pure log is the opposite extreme: tiny, but reading version 9,000 replays 9,000 changes.

The log plus checkpoints sits in between and is easy to explain in an interview. A change is tiny: (+1, "lasagne"). Store one per version, and a full copy of the cart every K versions. To read version v, start from the nearest checkpoint at or below it and replay at most K − 1 changes. The current version is kept fully built, so the common operations never replay anything.

class VersionedCart:
    def __init__(self, discounts, checkpoint_every=32):
        self.discounts = discounts
        self.k = checkpoint_every
        self.catalog = {}                       # recipe name -> Recipe
        self.ops = []                           # ops[v - 1] is the change that made version v
        self.checkpoints = {0: Cart(discounts)} # version -> full cart, every k versions
        self.head = Cart(discounts)             # the current version, kept materialized

    @property
    def version(self):
        return len(self.ops)

    def add_recipe(self, recipe):
        self._change(recipe, +1)

    def remove_recipe(self, recipe):
        if not self.head.recipes[recipe.name]:
            raise KeyError(f"{recipe.name} is not in the cart")
        self._change(recipe, -1)

    def get_total_discounts(self):
        return self.head.total_discount

    def get_version(self, v):
        if not 0 <= v <= self.version:
            raise IndexError(f"no version {v}")
        base = v - v % self.k
        cart = self.checkpoints[base].copy()
        for sign, name in self.ops[base:v]:
            cart.apply(self.catalog[name], sign)
        return cart

    def checkout(self, v):
        self.head = self.get_version(v)
        del self.ops[v:]
        for c in [c for c in self.checkpoints if c > v]:
            del self.checkpoints[c]

    def _change(self, recipe, sign):
        known = self.catalog.setdefault(recipe.name, recipe)
        if known != recipe:
            raise ValueError(f"{recipe.name} already exists with different ingredients")
        self.head.apply(recipe, sign)
        self.ops.append((sign, recipe.name))
        if self.version % self.k == 0:
            self.checkpoints[self.version] = self.head.copy()

checkout(v) rebuilds version v, makes it the head, and drops the changes and checkpoints after it, which is exactly what "discards every version created after it" asks for. get_version returns a copy, so a caller can't change history by mutating what they got back.

Operation Cost
add_recipe / remove_recipe O(I), plus an O(cart) checkpoint copy every K changes
get_total_discounts O(1)
get_version(v) O(cart + K × I)
checkout(v) O(cart + K × I), plus the discarded versions

How much space does it actually save?

I ran 10,000 changes, 60% adds and 40% removes, over 5,000 recipes of 5 ingredients each. The cart ends with 2,082 recipes (1,690 distinct). Memory is measured with tracemalloc.

Storage Memory Average get_version
Full snapshot per version 315.0 MiB —
Checkpoint every version (K = 1) 316.4 MiB 0.01 ms
Checkpoint every 32 versions 11.7 MiB 0.05 ms
Checkpoint every 256 versions 2.2 MiB 0.31 ms
Log only, no checkpoints 0.7 MiB 11.66 ms

K = 1 is the full-snapshot design, and it costs the same. K = 32 cuts memory by 27× for a version read that's still well under a millisecond. The pure log is the smallest but makes reads 1,000× slower than K = 1. K is the dial between the two.

Is it correct?

I checked it against a brute force that stores a full snapshot per version and recomputes discounts from scratch. Across 1,500 random runs of 120 operations each, with adds, removes (including removing recipes that aren't there), get_version and checkout mixed in, and K ranging from 1 to 32, the two agree on every version and every discount total. The tier lookup is also checked against a linear scan.

The persistent alternative

Since the follow-up is about space, it's worth naming the textbook answer: a persistent map. Every change copies only the path from the root to the changed entry and shares the rest with the previous version. A change costs O(log n) new nodes, and every version is available in O(1) with nothing to replay. That's how Clojure's maps and Git's trees work.

Python has no persistent map built in. pyrsistent provides one, and writing a path-copying tree from scratch isn't something to attempt in a phone screen. Mention it and explain why it works, then build the checkpoint version.

Critique

  • checkout throws away the redo history, permanently. That's what the prompt asks for, and it matches an editor's undo: make a new change after undoing and redo is gone. Product-wise, a user who checks out an old version by accident can't get back. Keeping versions as a tree, the way Git keeps branches, avoids that at the cost of never freeing anything.
  • Rebuilding for checkout is wasteful when v is close to the head. Every change has an exact inverse (add and remove undo each other), so checking out one version back could undo one change from the head instead of rebuilding from a checkpoint. Pick whichever is fewer steps: undo head − v changes, or replay v mod K.
  • K is fixed. A cart with three recipes doesn't need checkpoints at all; a huge cart makes each one expensive. A better rule is to checkpoint when the changes since the last checkpoint add up to some fraction of the cart's size, so both costs stay proportional.
  • A checkpoint is a full copy. With K = 32 the checkpoints are still almost all of the 11.7 MiB. A persistent map would share structure between checkpoints too.
  • The discount model is a guess. Real bulk pricing might be per unit, percentage based, or depend on the ingredient's price. The incremental update still works for any rule where an ingredient's discount depends only on its own combined quantity. A rule like "buy flour and butter together" breaks that, because one change can affect another ingredient's discount.
  • Everything lives in one process. A real cart service would store the change log in a database. The log-plus-checkpoint layout carries over well: it's event sourcing with snapshots, the same shape used for order histories and bank ledgers.