In an eagerly evaluated chain that maps, filters, then maps 10,000 order lines, how many collections get allocated?
answer
- stage at a time, not element at a time
- one new collection per stage
- count what the pipeline allocated, not the source
- traversals equal stages under eager evaluation
- stage order changes the transform call count
basics
~20 sThree — each eager stage fully builds its own collection before the next one starts: 10,000 elements from the first mapping stage, the survivors from the filtering stage, and that many again from the second mapping stage.
solid answer
~40 sThree, one per stage. An eager stage is stage-at-a-time, not element-at-a-time: the first mapping stage traverses all 10,000 order lines and materialises 10,000 shipment lines before the filtering stage reads its first element, the filtering stage materialises a collection sized to the survivors, and the second mapping stage materialises one of that same size. The source collection is a fourth container but the pipeline did not allocate it. So the chain costs three full traversals and two intermediate collections you never asked for and never see. The lever you have without changing anything else is stage order: if the predicate can be evaluated on the unmapped order line, putting the filtering stage first shrinks every collection downstream of it and cuts how many times the transform runs.
code
pseudocode · 7 lines// the chain, written with its intermediates named
a = map(orderLines, toShipmentLine) // 10,000 calls -> 10,000 elements
b = filter(a, isNotCancelled) // 10,000 calls -> k elements
c = map(b, withCarrierCode) // k calls -> k elements
// each line finishes completely before the next line begins:
// three traversals, three new collections, source untouchedgo deeper
Remember that each stage in a chain finishes its whole job and hands a finished collection to the next. Three stages means three new collections, two of which you never name or look at.
Be able to count: which collection each stage traverses, how many times its function is called, and how big the collection it builds is. State what n is before you quote a number.
On a hot path, turn the count into a concrete suggestion — move the predicate ahead of the transform where it can be expressed on the unmapped element, and check whether an intermediate is being retained by a long-lived name.
The trade-off a lead owns is legibility against allocation. A chain that reads as one sentence is worth intermediates almost everywhere, and the places where it is not should be identified by measurement rather than applied as a blanket rule.
## Stage at a time, not element at a time An eager stage does its whole job when it is called. It walks its input from the first element to the last, fills a result collection, and returns it. Nothing about the *next* stage influences it, and nothing is deferred. Chaining three stages therefore means three complete traversals, run one after another, with a fully materialised collection handed between each pair. That is the mental model the question is testing. A candidate who imagines one element flowing through all three stages before the second element starts has the wrong model for eager evaluation, and will mis-predict both memory and the order in which the transform and the predicate are called. ## Counting the allocations, with n = 10,000 1. **First mapping stage.** Calls the transform 10,000 times, allocates a collection of **10,000** shipment lines. One traversal of the source. 2. **Filtering stage.** Calls the predicate 10,000 times — once per element of that intermediate, not per element of the source — and allocates a collection of **k** elements, where k is the number of survivors. One traversal of the first intermediate. 3. **Second mapping stage.** Calls its transform **k** times, allocates a collection of **k** elements. One traversal of the second intermediate. Three collections allocated; three traversals; 10,000 + 10,000 + k function calls. The source collection makes a fourth container in memory, but it existed before the pipeline ran and the pipeline did not allocate it — counting it is the classic off-by-one in this answer. ## What is alive at the same time Allocated is not the same as **retained**. In a chained expression, the first intermediate becomes unreachable as soon as the filtering stage has finished reading it, so peak usage is typically two stages' worth rather than three. What defeats that is naming every intermediate in a variable that outlives the pipeline: a long-lived name keeps its collection reachable for as long as the name is in scope, and then all three really are alive at once. - **Chained**, with no intermediate named: the previous stage's output is droppable once the next stage returns. - **Named step by step** inside a short-lived scope: the same, once the scope ends. - **Named on something long-lived**: every intermediate is retained for the lifetime of that name, which is how a pipeline over a large collection turns into a memory problem that profiles look like a leak. ## The levers this gives you The honest levers are about **what each stage is asked to do**, and stage order is the biggest one: | arrangement | transform calls | first collection built | |---|---|---| | map, then filter | one per source element | one per source element | | filter, then map | one per surviving element | one per surviving element | If a tenth of the lines survive, moving the filtering stage to the front turns 10,000 transform calls into about 1,000 and a 10,000-element intermediate into a 1,000-element one. The result is identical — the same elements, in the same order — **provided the predicate can be expressed on the unmapped element**. If the predicate needs a field only the shipment line has, the filter cannot move, and that constraint is the interesting half of the answer. A second lever is cheapness per element: a predicate that does real work runs once for every element reaching it, so an expensive predicate placed after a stage that has not yet reduced the collection pays that cost at full width. ## Why this is asked at all Because pipelines read as a single declarative sentence, it is easy to reason about them as if the cost were a single pass. The count of allocations is the crispest way to check whether someone has looked underneath. It is also the knowledge that makes a code review useful on a hot path: the reviewer who can say "this chain builds two collections you never look at, and the predicate here can run before the transform" is making a concrete, checkable suggestion, not a stylistic one. Whether a chain like this can be collapsed into a single traversal at all is a question about the **evaluation strategy** the collection is being processed under, not about what mapping and filtering individually promise. Under eager evaluation, the count is three, and it is three every time.
- About a tenth of the lines survive the predicate. How does moving the filtering stage to the front change the work?The first stage then builds roughly 1,000 elements instead of 10,000, and the transform runs about 1,000 times instead of 10,000. The result is identical as long as the predicate can be evaluated on the unmapped order line. If it needs a field only the shipment line carries, the filter cannot move.
- Does the first intermediate collection stay alive while the third stage runs?Not necessarily. Each intermediate is retained only while something still refers to it, so in a chained expression the first becomes unreachable once the filtering stage has read it and peak usage is about two stages' worth. Naming every intermediate on something long-lived is what keeps all three alive.
- How many times is the predicate called, and over which collection?Once per element of the collection handed to it — the first intermediate, so 10,000 times, not once per survivor and not once per source element by coincidence. Knowing which collection a stage traverses is what makes the call counts predictable when stages are reordered.
saying these in an interview costs you the question
- Says an eager chain of three stages allocates only the final collection.
- Thinks the stages interleave element by element without being asked to.
- Claims the intermediate collection is reused and refilled by each stage.
- Assumes reordering the stages cannot change how much work is done.
- Counts the source collection among what the pipeline allocated.