A diff swaps a trade blotter's backing array for a linked list to make middle inserts O(1). What is your review?
answer
- Check which operation the O(1) covers
- How does the code find the row?
- A container swap changes every operation
- Compare a bulk move with a pointer chase
- Ask for a benchmark at real sizes
basics
~20 sReject it as written. The O(1) splice applies only at a node already held; a blotter inserting at a found position still walks O(n), and that walk over scattered nodes measures far worse than the array's contiguous shift of the same length.
solid answer
~50 sI would block it and ask two questions. First: where does the insertion point come from? If the code finds the row by timestamp or by scanning, the walk to that row is O(n) and the splice's O(1) buys nothing — the operation is linear either way, so the diff has not changed the complexity it claims to fix. Second: what does the blotter actually do most of the time? Blotters are read by position and scanned end to end far more often than they are spliced, and both of those get materially worse. Then the measured argument: the array's O(n) is a bulk move of adjacent memory, which hardware streams; the list's O(n) is a chain of loads that cannot be run ahead of, plus a reference and allocation header per row. Same asymptotic row, commonly a 10-100x wall-clock gap on realistic sizes. I would ask for a benchmark on the real access pattern before considering it further.
go deeper
Know that a container swap changes every operation, not just the one in the commit message, and that reaching a position in a linked structure means walking to it. Asking how the insertion point is found is already a good review comment.
Be able to separate locate from splice and show that O(n) locate plus O(1) splice is still O(n). Then list which other operations the swap regresses, with their before-and-after costs.
Demonstrate the measured argument on top of the asymptotic one: estimate the cost of a bulk contiguous move against a chain of dependent loads at a realistic row count, and name the conditions under which you would approve instead.
Own how such decisions get made at all. Set the expectation that container changes justified by performance arrive with a benchmark on production-shaped data, and weigh the maintenance cost of a structure whose fast path depends on every call site carrying stable handles.
## What the diff actually claims The stated justification — "middle inserts become O(1)" — is a half-quotation. In a linked structure the constant-time part is the **splice** at a node you already hold. The full operation is locate plus splice, and a blotter locates rows by something semantic: a timestamp, a sequence number, a position in the display. None of those can be resolved by arithmetic in a linked layout, so the locate is a walk from the head: O(n). O(n) locate + O(1) splice is O(n). The diff has therefore not improved the complexity of the operation it names. That is the first and most important point of the review, and it can be made without any hardware argument at all. ## The workload, not the operation The second point is scope. A container swap changes *every* operation, not the one in the commit message. For a trade blotter the honest inventory usually reads: - render or page a window of rows by position — was O(1) per row, becomes O(n) per lookup; - scan the whole book to total or filter — O(n) both ways, but much slower in practice; - append a fill at the end — O(1) amortised before, O(1) with a tail reference after; roughly a wash; - insert a late-arriving row in the middle — O(n) before, still O(n) after. One row of the table is neutral, one is unchanged, and the rest regress. A change that degrades the dominant operations to speed up a rare one, and does not actually speed it up, is not a performance change; it is a performance regression with a performance-shaped rationale. ## The back-of-envelope a skeptic will want Suppose the blotter holds 100,000 rows and the insertion lands in the middle. - **Array:** move 50,000 adjacent slots one position along. Addresses are perfectly predictable, the hardware moves many bytes per step and prefetches the rest, and the whole run streams out of a handful of memory pages. This is the case memory systems are optimised for; it lands in the tens of microseconds. - **List:** follow 50,000 references. Each node's address is only known once the previous node's memory arrives, so the fetches cannot overlap. Nodes allocated at different times sit on different lines, so a large share of the hops are genuine memory misses at roughly a hundred nanoseconds each. Fifty thousand mostly-missing dependent loads is on the order of milliseconds. Two orders of magnitude, from a table that says both are O(n). The lesson to state out loud is that big-O bounds *growth*, not time: when two candidates share a complexity class, the decision moves entirely to constants, and memory behaviour is where those constants live. Memory footprint reinforces it. Every row acquires one or two references plus whatever the allocator's per-object bookkeeping costs, so a blotter of small rows can grow substantially, and the extra bytes make each cache line carry fewer real rows — the walk gets worse in exactly the case that was already worst. This is not a fringe view: mainstream ecosystems have converged on it, with the default general-purpose sequence in Python, Go, Java and C++ all being a contiguous growable buffer rather than a linked one, and their linked containers reserved for narrow cases. When four independently designed standard libraries make the same call, a diff that reverses it needs evidence. ## What would change my mind Be specific about the conditions under which you would approve, or the review reads as dogma: - the code genuinely **holds** references to the rows it splices at — an iterator or handle carried from a prior step — so no walk happens; - those held references must stay valid while the container is mutated around them; - positional access and full scans are demonstrably rare in the real workload; - and there is a benchmark, on production-shaped sizes and access patterns, showing the win. Absent the first two, the O(1) splice is unreachable and the argument collapses. Present all four, the change is defensible and I would say so. ## How to write the review comment Ask rather than assert, and make the ask cheap to answer: *"How does this code find the row it inserts before? If it scans, the insert is still O(n) and we have traded away O(1) indexing and a much faster scan for it. Can you post a benchmark at ~100k rows on the real access mix?"* That reframes the discussion from a complexity table to evidence, which is where a performance argument belongs — and it leaves the author a path to being right. ## Traps in your own reasoning - Do not argue that linked lists are always wrong; they are not, and an interviewer will probe that. - Do not skip straight to memory behaviour. The locate-walk objection is stronger, simpler, and holds regardless of hardware. - Do not accept "but it is O(1) per the table" without asking which operation the table row covers.
- The author replies that the array's shift is O(n) too, so it is a wash. How do you respond?Agree on the class and move to constants. The array's linear work is a bulk move of adjacent memory that hardware streams and prefetches; the list's is a chain of loads where each address arrives only with the previous node, so the fetches cannot overlap and most of them miss. Same row in the table, commonly two orders of magnitude apart in measured time.
- What would make you approve the change?Evidence that the splice sites are reached by references the code already holds rather than by scanning, that those handles must survive mutation around them, that positional reads and full scans are genuinely rare in the real mix, and a benchmark at production-shaped sizes showing the win. Without the first condition the O(1) splice is simply unreachable.
- How would you keep this review from becoming a dogma argument about linked lists?Convert it into a measurement. State the specific claim being tested — insert latency at the real row count under the real access mix — and ask for numbers on both containers. That gives the author a way to be right, keeps the discussion on the workload, and produces an artefact the team can reuse the next time someone proposes a container swap.
saying these in an interview costs you the question
- Accepts the O(1) claim without asking how the position is found
- Argues only about complexity classes and never about measured time
- Says linked lists are always the wrong choice
- Ignores that the swap also degrades indexing and scanning
- Approves a performance change with no benchmark