skip to content

If two identifier-remapping stages run in sequence and the combined mapping is injective, what does that prove about each stage?

level: seniorimportance: nice to knowfreq 24%

answer

  1. which stage does the joint test exercise
  2. the second stage sees only the first stage image
  3. injective composition forces the first stage
  4. surjective composition forces the second
  5. inverses undo in reverse order

basics

~20 s

Only the first stage must be injective. The second may collide freely outside the first stage's image, because the composition never exercises it there — which is a live defect the moment anything else feeds the second stage directly.

solid answer

~50 s

Composition transmits these properties asymmetrically, and the direction matters. If the end-to-end mapping `g(f(x))` is injective, then **`f` is injective**: two old identifiers colliding under `f` would still collide after `g`. But `g` need only be injective **on the image of `f`** — on the identifiers the first stage actually produces. Anywhere else it may map many inputs to one, and the end-to-end test will never notice. The dual statement runs the other way: if the composition is surjective then **`g`** is surjective, while `f` need not be. Both properties do compose in the easy direction: injective after injective is injective, surjective after surjective is surjective, and two bijections compose to a bijection whose inverse applies the stage inverses in **reverse order**. The practical bite is a two-hop migration validated only end to end: the day a second producer writes into the middle stage directly, the untested collisions become real.

go deeper

for a junior

Note the easy direction first: if neither stage ever merges two distinct identifiers, the pair of them cannot merge two either. The harder direction is what the question is really after.

for a middle

Explain why an injective composition pins the first stage but leaves the second constrained only on the identifiers the first stage produces, and give an example of a second stage that collides outside that range.

for a senior

Show the operational consequence: a green end-to-end test hiding an untested assumption, the moment a second producer or a widened first stage makes it reachable, and where you would enforce uniqueness to catch it.

for a principal

Decide whether the interim identifier space is a private implementation detail or a published contract, and who is permitted to write into it, since that choice is what makes the hidden assumption safe or fatal.

## Two stages, four claims Write the two-hop remap as `h(x) = g(f(x))`: the first stage `f` sends old identifiers to interim ones, the second stage `g` sends interim identifiers to final ones. Four claims are worth keeping straight, and interviewers on this material reliably probe the two that run backwards. | Claim | Holds? | Why | |---|---|---| | `f`, `g` injective implies `h` injective | Yes | Distinct inputs stay distinct through the first stage, then through the second | | `h` injective implies `f` injective | Yes | If `f` collided on two inputs, `g` would receive one value and `h` would collide too | | `h` injective implies `g` injective | **No** | `g` is only exercised on the image of `f`; elsewhere it may collide freely | | `h` surjective implies `g` surjective | Yes | Every final identifier is produced by `h`, so it is produced by `g` on some input | The dual of the third row is the one people also miss: `h` surjective does **not** make `f` surjective, since the second stage may reach the rest of the target on its own. ## Why the failure hides An end-to-end validation only ever feeds `g` the identifiers that `f` produced. That is a restricted slice of `g`'s domain, so the test is checking a property of `g` restricted to that slice — nothing more. This is exactly the shape of the bug: - A **truncating or normalising** second stage may be injective on the well-spaced interim identifiers the first stage emits, and collide immediately on inputs that are close together. - A second stage keyed on only **part** of the interim identifier is injective as long as the first stage varies that part, and collapses the moment something varies only the rest. - A second stage that is injective on a **narrow range** passes while the first stage stays inside that range, and breaks silently when the first stage's output grows. In each case the joint test is green and the second stage carries an untested assumption about who is allowed to call it. ## When the assumption goes live The hazard is organisational as much as mathematical. The second stage looks like a reusable component, so sooner or later something else uses it: 1. A new producer writes into the interim store directly, bypassing the first stage. 2. A backfill replays historical records whose interim identifiers were formed by a different rule. 3. The first stage is replaced or widened, and its new output range leaves the region where the second stage happened to be injective. From that moment collisions are real, and they surface in the final store rather than at the stage that caused them, which makes them expensive to trace. ## Inverses compose in reverse If both stages are bijections then `h` is a bijection too, and its inverse undoes the stages in the **opposite order**: undo `g` first, then `f`. The order reverses for the same reason that unpacking reverses packing — you must remove the last thing applied before you can reach the first. Getting this backwards is a common slip when someone is building a back-translation path over a multi-hop migration, and it fails in a way that looks like data corruption rather than like an ordering mistake, because the wrong inverse still returns plausible identifiers. ## What to say, and what to do - State the direction precisely: the composition being injective constrains **the first stage** fully, and the second stage **only on the first stage's image**. - Say what would make the second stage safe unconditionally: injectivity over its whole declared domain, established by argument or enforced by a uniqueness constraint where its outputs land. - Test each stage against its own contract, not only the pipeline against its ends. A pipeline test is the composition, and by the table above the composition simply cannot see the second stage's collisions. - Treat the interim identifier space as a published contract if anything other than the first stage may ever write into it, because the moment it has two producers the untested region becomes reachable.

  • If the combined two-stage mapping is surjective, what does that force?
    That the second stage is surjective onto the final identifier set, since every final identifier is produced by the composition and therefore by the second stage on some input. It forces nothing about the first stage, which may reach only a sliver of the interim space while the second stage covers the rest from other inputs. The pattern is the mirror image of the injective case: the composition constrains the near end for injectivity and the far end for surjectivity.
  • Both stages are bijections. What is the inverse of running them in sequence?
    Undo the second stage first, then the first — the inverses apply in reverse order. The reason is mechanical: the last transformation applied is the outermost one, so it must come off before the earlier one is reachable. Getting the order wrong is easy to miss in a multi-hop back-translation because the wrong composition still returns well-formed identifiers; they simply name the wrong records.
  • How would you test the second stage properly, given the pipeline test cannot see its collisions?
    Test it against its own declared domain rather than against whatever the first stage happens to emit: adversarial inputs that are close together, inputs that differ only in the parts the first stage holds constant, and inputs outside the first stage's current range. Then enforce a uniqueness constraint where its outputs land, so that if the assumption is ever violated in production the write fails instead of silently merging two records.

saying these in an interview costs you the question

  • Concludes both stages are injective from an injective composition
  • Says the second stage is the one forced to be injective
  • Claims a pipeline test covers each stage's full domain
  • Applies stage inverses in the original order when undoing both
  • Thinks a surjective composition forces the first stage to be surjective
  • Treats an interim identifier space as private once a second producer exists