Order, Duplicates, Size
Three questions flip the representation on their own: does order mean something, must each thing appear once, and what bounds how large it gets. Each has a case where the cart's answer changes and the array stops fitting.
The situation, the reflex, and why it stalls
Every lesson starts where being stuck starts: someone has a problem, and the first move that comes to mind feels like progress.
The cart is an array and it works. Which three changes to the requirements would make that the wrong choice, and how do you notice them arriving?
The representation is chosen and the code is written. Now the requirements move: the design team wants the cart sorted by price, a merge at login means two carts overlap, and someone mentions a B2B customer who orders four hundred distinct lines. I can feel that some of these matter for the structure and some do not, but I cannot say which, so I either rewrite everything or nothing.
Rewrite at the first change. Sorting the cart by price feels like a new structure — a sorted map, perhaps — and moving to it feels like taking the requirement seriously. Or the opposite reflex: the array works, so every change gets absorbed as a workaround, a sort here and a dedupe there, and the structure is never revisited at all.
The sort-by-price requirement produces a sorted structure, and the display order turns out to be a render-time concern: the cart is still added to in insertion order and shown sorted. A stored sort was chosen for a computed order, and now every add has to keep the structure sorted for no reader that needs it.
- The sort-by-price requirement produces a sorted structure, and the display order turns out to be a render-time concern: the cart is still added to in insertion order and shown sorted. A stored sort was chosen for a computed order, and now every add has to keep the structure sorted for no reader that needs it.
- The merge at login produces duplicate entries — Laptop from the anonymous cart and Laptop from the saved one — and the array's "one entry per product" rule, which lived in addItem's find, is bypassed because merge concatenated the lists. The rule was a line of code, and the new operation did not call the line.
- The four-hundred-line B2B cart is dismissed as an edge case, and it is — until the scan in addItem runs on every keystroke of a quantity field and the form lags. The size bound moved from "a shopper" to "a purchasing department" and nothing recorded that the array rested on the old bound.
- With no record of which question the structure answered, every requirement change is a fresh argument about arrays versus maps, and the outcome depends on who is in the room rather than on which of the three questions actually moved.
The move
Precisely enough to apply it to a problem you have never seen — not a slogan.
- Keep the three questions as the written assumptions the representation rests on. "Insertion order matters; each product appears once; bounded by one shopper." When a requirement arrives, ask which of the three it moves. Most move none; the ones that do are the ones that can flip the structure.
- For order, separate stored order from computed order. A cart shown sorted by price is stored in insertion order and sorted on render; a cart where the user drags items into an order they chose stores that order. Only stored order constrains the structure, and it prefers an array or an ordered map.
- For duplicates, ask whether the uniqueness rule is enforced by the structure or by a line of code, and whether every operation — including new ones like merge — goes through that line. If a new operation can create a duplicate, either route it through addItem or make the rule structural with a map or a set of keys (From Invariant to Validation).
- For size, ask what bounds it and whether the bound changed. "A shopper" and "a purchasing department" are different bounds, and the annotation on the scan said which one the array assumed. When the bound moves, measure at the new bound; if the scan shows up, the switch condition has tripped and the map was written down for this moment.
Order: stored or computed?
Most order requirements are display requirements, and display order is computed. The decision below is the one to make before any structure is named; its first two options keep the array and its last one is the only one that constrains the structure at all.
The cost column is where the reflex goes wrong: a stored sort keeps the structure sorted on every add for a reader that would have sorted at render anyway.
Is this order stored, computed, or owned by the user?
when The order is a function of the items and data the cart already derives (catalog price, name) and the user does not rearrange it.
cost A sort on every display, O(n log n) on a handful of items — invisible; the structure stays an array in insertion order.
when The user expects the cart to read the way they filled it; this is the default and the array gives it for free.
cost Nothing beyond the array; a map gives it only where the language promises, which is an assumption to write down.
when The order is state the user changes and expects to survive; it is a field, not a function.
cost A position on each entry or an ordered structure; every insert and move must keep it consistent, and it must persist with the cart — the one case where order constrains the representation.
Duplicates: a rule the structure keeps, or a line every path must call
The rule "one entry per product" is where the array and the map differ most in kind, not in cost. Below it is written the way the concept writes every rule — in words, as a validation, and as the code — and the code shows why a new operation can break it: the check is a line in addItem, and merge does not go through addItem unless someone makes it.
The alternative encoding — a map, a set of keys beside the array, a unique constraint in the table — moves the rule out of the line and into the structure. Choose it when the number of paths that create entries makes the line unreliable.
rule A product appears at most once in a cart; adding it again increases the quantity of the existing entry.
↓ becomes validation Before creating an entry, look for an existing one with the same product id and increase it instead. Every operation that can create an entry — add, merge, restore from storage — must do this, or the structure must make a second key impossible.
-- in the array: a line each path must call
existing = find(cart.items, productId)
if existing: existing.quantity += quantity
else: append(cart.items, { productId, quantity })
-- merge must go through it, or it creates the duplicate
function merge(target, source):
for each entry in source.items:
addItem(target, entry.productId, entry.quantity)
-- or make the rule structural: Map<ProductId, CartItem>, or UNIQUE (cart_id, product_id)The cases where the cart's answer flips
The table is the module's honest half. Each row is a real requirement, the question it moves, what it looks like when the array is kept without noticing, and the response — which is sometimes "keep the array" and sometimes not.
Read the symptom column as the thing you would notice in production if the classification step were skipped. None of them are exotic; each is a cart requirement that arrives in the first year of a store.
| Trigger | Symptom | Cause | Response |
|---|---|---|---|
| Design asks for the cart sorted by price. | A sorted structure is introduced; every add re-sorts; the JSON boundary now needs a conversion the array never did. | Order was read as stored when it was computed — the price is derived from the catalog anyway. | Keep the array; sort at render by the derived price. Store an order only when the user owns it. |
| Anonymous cart merges into the saved cart at login (V4). | Laptop appears twice after login; changeQuantity does not know which entry to change. | Merge concatenated the arrays; the uniqueness rule was a line in addItem that merge did not call. | Route merge through addItem per entry with a written rule for overlapping quantities — or make uniqueness structural server-side with the unique constraint. |
| A B2B customer orders four hundred distinct lines. | Nothing, after measuring: the scan is still a few microseconds per add. | The bound moved from a shopper to a department, but the new n is still small. | Keep the array; update the annotation's bound; the switch condition has not tripped. |
| Carts are imported from a supplier feed with tens of thousands of lines. | An import that scans per line is quadratic; the form lags on every quantity keystroke. | The bound moved to "a feed" — unbounded from the cart's point of view — and the O(n) scan is now real. | The switch condition tripped: a map keyed by product id inside the cart, with the JSON conversion and order assumption written down; or rows with an index, if the cart already lives server-side. |
| The cart is restored from browser storage after a product was removed from the catalog. | total throws; a duplicate can appear if the stored cart and the session cart are concatenated. | A path that creates entries — restore — bypassed both the catalog check and the uniqueness line. | Restore through addItem so every rule runs; drop or flag unknown products at restore, not at total. |
The implementation ladder
Concept, examples, pseudocode, code, tests, production — for the concept this lesson is about. Code is the fourth tab, not the first.
Shopping Cart = A temporary collection of products the user intends to purchase, held between browsing and checkout.
- Does a cart have identity? Yes, weakly. Two carts with the same items are still two carts, because each belongs to someone and will become a different order. It needs an id once it leaves memory; in memory the variable is the identity.
- Who owns it? A shopper — a logged-in user or an anonymous session. The owner is part of the state because "my cart" has to be findable again.
- How long does it exist? From the first add until checkout or abandonment. Whether it survives a reload, a closed browser or a login is not a property of the concept; it is a persistence decision made later, and each answer changes where the cart lives.
- Should it survive reload? Usually yes for a store, usually no for a demo. V1 in memory says no; V2 browser storage says yes on one device; V3 server storage says yes everywhere the user is logged in.
- Should it survive login? Only if an anonymous cart and a logged-in cart are merged — a rule that does not exist in V1 and appears as a modification later.
- itemscollection of CartItemkeepThe cart is its items; without them nothing else means anything.
- items[].productIdidkeepThe reference to what is being bought. The catalog owns the product; the cart only points at it.
- items[].quantityinteger > 0keepTwo laptops is one entry with quantity 2, not two entries — the rule "one entry per product" needs a quantity to hold.
- owneruser id or session iddependsSo the cart can be found again by the person it belongs to.
- items[].productNamestringderiveIt would be convenient to render the cart without a catalog lookup.
- items[].pricemoneydependsThe total needs a price per item.
- totalmoneydropEvery screen shows the total.
- currencycodedependsPrices need a currency to be added.
- createdAttimestampdropAbandoned carts might be expired or emailed about.
- update Add item — the updated cart
- delete Remove item — the updated cart
- update Change quantity — the updated cart
- read View items — the list of entries — product id and quantity — for rendering
- domain Calculate total — the sum of price × quantity over the entries
- delete Clear cart — the empty cart
- • Every quantity is greater than zero.
- • One logical entry per product.
- • The total is never negative.
- • An unknown product cannot be added.
- • Quantity cannot exceed available stock — if inventory is enforced here.
How to do it
Most important first.
- Write the three answers next to the representation as assumptions, in the assumption register's form: what is assumed, why, and what would change if it were false (The Assumption Register).
- When a requirement arrives, classify it before designing for it: does it change the order the user sees or the order that is stored? Does it add an operation that can create an entry without going through the uniqueness check? Does it change what bounds the size?
- For an order change, try computing it at render first. A sort on a handful of items at display time is the simpler thing; store an order only when the user owns it (Derived vs Stored).
- For a duplicates change, trace every path that creates an entry — add, merge, restore from storage — and check that each keeps the rule. If the list is long, make the rule structural; a rule with many enforcers is a rule with a bug waiting.
- For a size change, re-measure at the new bound with the experiment from Why This Data Structure?; the answer is a number, and the number decides.
Worked on a concrete problem
The move has to produce something. This is what it produced.
- Sort by price. Which question moved? Order — but the order the user sees, not the order stored. The cart still fills in insertion order; the render sorts by the catalog's price, which the cart derives anyway. Structure unchanged; a
sortat render, annotated O(n log n) on a handful of items. The switch would come only if the user chose the order themselves, which is stored order. - Merge at login (the concept's V4). Which question moved? Duplicates — a new operation creates entries. The rule "one entry per product" lived in addItem's find; merge must either call addItem per entry of the anonymous cart, so the quantities combine, or the structure must make the rule impossible to break. The concept keeps the array and routes merge through addItem, with a written merge rule for overlapping products; a server-side store keyed by product would have made the same rule structural.
- The four-hundred-line B2B cart. Which question moved? Size — the bound moved from a shopper to a department. The annotation on the scan said "invisible at cart size; measure before switching". Measure: four hundred entries, an add on every quantity keystroke — still a handful of microseconds in the browser, still invisible; the array survives. It would not survive a cart merged from a supplier's feed with tens of thousands of lines, and the switch condition names that case.
How you know it worked
What now exists that did not before, and what question you can now ask.
- The three answers are written beside the representation as assumptions, and a new requirement is classified against them before anything is designed.
- Order questions are answered with "stored or computed?" before any structure is named, and most of them end in a sort at render.
- Every operation that creates an entry is known, and each either goes through the uniqueness check or the check is structural — so merge cannot create a duplicate by accident.
- A size change produces a measurement at the new bound, and the measurement — not the requirement's wording — decides whether the switch condition has tripped.
The questions you can now ask
The field this whole domain exists for. After this lesson, these are the questions to put to an unfamiliar problem.
- ?Which of the three — order, duplicates, size — does this requirement actually move?
- ?Is this order something the user sees, or something the structure must store?
- ?Which operations can create an entry, and does each one keep the uniqueness rule — or should the structure keep it for them?
- ?What bounds the size now, and is that a different bound from the one the representation assumed?
- ?Did the switch condition trip, according to a measurement rather than a sentence?
What can go wrong
- Every requirement is classified as a structure change. Sorting by price becomes a sorted map, a "recently added" badge becomes a timestamp on the structure; the three questions are meant to filter requirements out, and a filter that passes everything is a rewrite policy.
- The three answers are written once and never re-read, so the merge operation is added by someone who did not know the uniqueness rule was a line in addItem. The assumptions are a register only if new operations are checked against them.
- Size is re-measured with the wrong n. Four hundred lines in one cart is a different n from four hundred thousand carts on a server, and the measurement that answers one says nothing about the other.
- The move stops at the structure. Duplicates after a merge are also a domain question — what quantity does the merged Laptop have? — and the representation cannot answer it; the merge rule can (Understanding Is Demonstrated by Modification).
- Classifying requirements against three written assumptions is overhead on every change; on a concept whose requirements never move, it is a register nobody reads.
- Computing order at render keeps the structure simple and pays a sort on every display; for a very large or very frequently displayed collection, the stored order the reflex reached for was cheaper.
- Making uniqueness structural with a map trades the array's free order and JSON for a guarantee that a line of code could also give — and the trade is only worth it when the number of paths that create entries is large enough that the line will be missed.
- "So requirements about order always mean a sorted structure." Almost never in application code; they mean a sort at render unless the user owns the order. The sorted structure is for order that is queried by range and changes often, which is the search index's problem, not the cart's.
- "Duplicates are prevented by the array's find, so they cannot happen." They cannot happen through addItem. Every other path that creates an entry — merge, restore from browser storage, a bulk import — has to be checked, and the concept's stale-storage failure mode is one that bypassed it.
- "Size is about how many users we will have." Size is about n for a specific operation on a specific collection. The number of users bounds the server's collection of carts; it does not bound one cart, and the array inside a cart is unaffected by a million shoppers.
Where this applies
Problem-solving advice is stated as universal far more often than it is. These labels say what each method is specific to — and where CONTESTED appears, the note gives the strongest form of the opposing view.
- GENERALOrder, duplicates and size are the three questions for any collection; a queue asks them too (FIFO is stored order, a job may not run twice, the backlog is unbounded) and answers them differently, which is why a queue is not an array.
- STAGE-SPECIFICIn V0–V2 the cart is the only writer and the three answers can live in code; from V3, when the browser, a merge and a restore can all create entries, duplicates move from a line of code to a unique constraint, because the number of writers changed and not the rule.
- ILLUSTRATIVEThe four-hundred-line B2B cart, the supplier feed with tens of thousands of lines and the microseconds in the browser are invented for the shape of the argument; the measurement at the new bound is the real answer and has to be taken.
Where the depth lives
This domain asks the question and hands the answer off by name.