skip to content

A routine's only input is a list of entries of an unknown type and it returns a list of that type — what bodies remain possible?

level: seniorimportance: should knowfreq 40%

answer

  1. structure is visible, contents are not
  2. output entries come from the input
  3. the length is the only signal
  4. reorder, drop, duplicate — never compare
  5. a rule from length to positions

basics

~20 s

Only bodies that choose by position. Every output entry must be one the caller supplied, so the body is fixed by the input's length alone — it may reorder, drop or duplicate entries, but never inspect, compare or invent one.

solid answer

~50 s

Since no entry can be examined and no entry can be built, every value in the result has to be one of the values that arrived. What the body *can* see is the structure: how many entries there are and which position each occupies. So a body amounts to a rule that turns a length into a list of positions — for a prize draw over a list of any entry type, the signature says the draw is a function of how many entries were submitted and nothing else. That is a tiny space compared with what the name "draw" suggests, and it is derived from the declaration without opening the body. The bound holds while the body is pure, terminates and cannot ask what the type is; each of those conditions removed widens the space again.

code

pseudocode · 10 lines
pseudocode
// signature: draw(entries: list of T) -> list of T
function draw(entries)
    n = size(entries)
    if n = 0
        return empty_list()
    result = empty_list()
    append(result, entries[n - 1])   // last slot
    append(result, entries[0])       // first slot
    append(result, entries[0])       // same slot again: duplication is free
    return result

go deeper

for a junior

Hold on to the core fact: whatever comes out was already in. A routine that cannot look at an entry has no way to produce an entry nobody handed it.

for a middle

Explain the split between structure and contents — the length and the positions are readable, the entries are not — and show that this is what pins the behaviour down to a choice of slots.

for a senior

Use the bound in review: state what the declaration already proves about a draw, and name the conditions that would void it, such as effects or a body that can ask what the type is.

for a principal

Treat it as a design lever. When a requirement cannot be expressed under the current declaration, that is the signal to widen the input deliberately rather than to quietly grant the body more power.

## The setting Take a prize draw. Entries arrive as a list; the routine returns a list of the winners. Its declaration says: *for any entry type the caller chooses, take a list of that type and give back a list of that type*. The body is written once, before anyone has decided what an entry is, and it is handed no operation for working on one. The question an interviewer is really asking is: **how much have you learned about this routine before reading a line of it?** Considerably more than candidates expect. ## What the body can and cannot see The split is between **structure** and **contents**: - **Visible — the number of entries.** The list itself is a type the body names, so its length is readable. - **Visible — positions.** The body may take the first entry, the last, every second one, whatever it likes by index. - **Visible — the shape of the result it builds.** It decides the output length freely. - **Invisible — what an entry is.** No comparison, no ordering, no equality, no test, no printing, no conversion. - **Invisible — whether two entries are the same.** Equality is an operation on the entry type, and none was granted. - **Unavailable — new entries.** There is no way to fabricate a value of a type the body cannot name. ## Counting what is left Put those together and the space of bodies collapses: 1. Every value in the output was one of the inputs — nothing else of that type exists. 2. Which inputs are chosen cannot depend on what they are — the body cannot tell them apart. 3. So the choice can depend only on the one thing that *is* visible: the length, and the positions it implies. A body is therefore a rule that maps a length *n* to a list of positions drawn from `0 … n-1`, applied to whatever arrived. "Return the last entry, then the first, twice" is such a rule. "Return the entry that looks most like a winner" is not expressible at all. | Proposed output for a list of *n* entries | Possible? | Why | |---|---|---| | The same entries in reverse order | Yes | a rule over positions | | The first entry, repeated three times | Yes | duplication is free; the value is reused | | An empty list, whatever arrived | Yes | dropping everything is a rule over positions | | The entries sorted | No | ordering is an operation on the entry type | | The entries with duplicates removed | No | needs equality between entries | | A list containing an entry nobody submitted | No | such a value cannot be constructed | ## The two mistakes candidates make The first is to say the body may only **reorder**. Dropping and duplicating are equally available, and the output length need not match the input length at all — a body may return twenty entries from a list of three, as long as every one of the twenty is a copy of something that arrived. The second is to conclude that the body is blind to the *input*. It is not: it reads the length and it reads positions. What it cannot read is an entry. Getting that distinction right is the difference between the rule and a slogan. ## Where the count stops holding State the conditions, because they are the interesting half of the answer: - **Effects.** A body permitted to touch the outside world can consult something else to decide which positions to take, and the count is over *results*, not over behaviours. - **Non-termination and failure.** Neither is ruled out by any signature. - **Run-time inspection.** Where the platform lets a body ask what the type argument was — some discard it before execution, some keep it — the body can branch on the answer and the bound is gone. - **A constraint on the entry type.** The moment the declaration narrows the entry type so the body may do something to an entry, the body may use it, and sorting or de-duplication becomes expressible. ## Using it at a whiteboard The practical payoff is that a reviewer can read this declaration and conclude, without the body: the draw cannot favour an entry, cannot depend on entry contents, and behaves identically on two lists of the same length. If the product requires the draw to favour something — a weighting, a seed, a category — that requirement has to enter through an argument, because the current declaration provably cannot express it. The signature has told you the feature is missing before anyone wrote the ticket.

  • Does the signature stop the routine returning more entries than it received?
    No. Duplication costs nothing, because a repeated entry is still an entry that arrived. A body may emit any number of copies of any position, so the output length is unconstrained — what is constrained is that every value in it came from the input.
  • If the routine also takes a count of winners, does the reasoning change?
    Only by widening the input the rule may consult. The choice of positions may now depend on the length and on that number, both of which are visible. Entries themselves remain opaque, so the routine still cannot prefer one entry over another on its merits.
  • What does this tell you about two lists of the same length?
    The routine treats them identically in terms of which slots it takes. It may return different values, because different values were supplied, but the pattern of positions is the same — which makes the behaviour testable with a single representative list per length.

saying these in an interview costs you the question

  • Says the body may only reorder, missing drop and duplicate
  • Thinks the output length must equal the input length
  • Claims the body cannot even see how many entries arrived
  • Says the routine could sort or de-duplicate the entries
  • Assumes two entries can be checked for being the same