skip to content

When does a remapping from old record identifiers to new ones have an inverse that translates any new identifier back?

level: middleimportance: must knowfreq 54%

answer

  1. which direction do you need to undo
  2. injective undoes only what it produced
  3. left inverse versus right inverse
  4. image is not the codomain
  5. bijection onto that set for both ways

basics

~20 s

Injectivity alone gives an inverse only on the identifiers the remap actually produced. To translate back any identifier the new store holds, the remap must also be surjective onto that set — together, a bijection onto it.

solid answer

~60 s

Three inverses are worth separating. A **left inverse** undoes the remap on its own output: `g(f(a)) = a`, and it exists exactly when `f` is injective. A **right inverse** produces a source for any identifier you name: `f(h(b)) = b`, and it exists exactly when `f` is surjective onto that set. A genuine two-sided inverse needs both, so the remap must be a **bijection**, and then the inverse is unique. The usual mistake is to say the identifiers are unique so the map is bijective: unique outputs make it a bijection *onto its image only*, and the image is a tiny slice of what the new store can represent. That distinction decides the contract of the back-translation. If every row in the new store came from the migration, injectivity suffices and the inverse is a partial function whose domain is the image. If the new store also mints identifiers of its own during the cutover, the inverse must stay explicitly partial and answer no such old record rather than guess.

go deeper

for a junior

Remember the shape of the rule: you can undo a mapping only if nothing was lost on the way in. Two old records sharing one new identifier means there is nothing to undo.

for a middle

Distinguish left, right and two-sided inverses, and say which property each needs. Then explain why unique outputs give a bijection onto the image only, and why that makes the back-translation partial.

for a senior

Show how you would operate it: derived inverse by a decodable encoding versus a stored mapping table, how long that table must outlive the migration, and how a back-translation behaves for a record minted after the cutover.

for a principal

Decide the contract before the code: whether the platform guarantees back-translation at all, for how long, and what that commitment costs in retained data, and who else in the organisation is allowed to mint identifiers in that space.

## Three inverses, not one Everyday language has one word for undoing a mapping; the mathematics has three, and the migration question is really about which one you are entitled to. | Inverse | The equation it satisfies | Exists exactly when | What it lets you do | |---|---|---|---| | Left inverse `g` | `g(f(a)) = a` for every old identifier `a` | `f` is injective (domain non-empty) | Recover the old identifier from any new one the remap produced | | Right inverse `h` | `f(h(b)) = b` for every `b` in the target set | `f` is surjective onto that set | Name a plausible source for any identifier in that set | | Two-sided inverse | Both equations at once | `f` is bijective onto that set | Translate freely in either direction, and the inverse is unique | The asymmetry is the whole content of the question. Injectivity is about not losing information, and information you did not lose can be recovered. Surjectivity is about coverage, and coverage decides whether the recovery is defined on everything you might be asked about. ## Image versus codomain: the trap "Every identifier we produced is unique, so the mapping is bijective" is the sentence to be ready for. Unique outputs make the remap a bijection **onto its image** — the set of identifiers it actually produced — and nothing more. The codomain, the space of identifiers the new store can hold, is typically astronomically larger. The consequences are concrete: - Back-translating an identifier **your migration produced** is always possible when the remap is injective. - Back-translating an **arbitrary** identifier the new store could hold is not, because almost all of them were never produced. - So the inverse is a **partial function**. Its domain is the image, and the honest response outside that domain is "no such old record", never a nearest match. ## What this means during a real cutover 1. **Migration-only target.** Every row in the new store came through the remap. An injective remap gives you a left inverse over the whole live identifier set, because here the image *is* that set — the remap is a bijection onto it, which is the condition the question asks for. 2. **Live cutover.** The new store also mints identifiers for records created after the switch. The remap is no longer surjective onto the live set, so a back-translation must be allowed to answer "this record has no predecessor". Code that assumes a total inverse either crashes or, worse, silently attributes a new record to an old one. 3. **Merging migration.** The remap deliberately sends several old records to one new row. It is not injective, so there is no left inverse at all: the best available object is the **preimage**, the set of old identifiers behind a row, and that has to be stored explicitly because it cannot be computed back out. ## Derive the inverse, store it, or recompute it - **Derived.** The old identifier is embedded in the new one under a uniquely decodable encoding, so inverting is a parse. It costs nothing, cannot drift out of date, and its correctness is an argument rather than a data set. - **Stored.** A mapping table records each pair. This works for any remap, including ones with no structure at all, but the table is now a durable asset: it must be backed up, must outlive the migration by as long as anyone can quote an old identifier, and its own uniqueness constraint is what actually enforces the injectivity you claimed. - **Recomputed.** Re-run the forward remap over the old store and index the results. Valid only while the old store still exists in the state it had, which makes it the first of the three to quietly stop working. ## Edge cases an interviewer will push on - **Partiality.** A remap that skips some records is not defined on the whole old set. Its inverse cannot recover what was never mapped, and a reconciliation that does not separate skipped records from merged ones will misdiagnose both. - **Retries.** If the remap draws a new identifier from a sequence generator, it is not a function of its input — the same record gets different identifiers on a re-run, so no inverse is even definable. A remap that is a pure function of the old identifier is safe to re-run and is the precondition for everything above. - **Order.** Whether new identifiers sort the same way as old ones is a separate property. It matters for pagination and for index locality, and it has no bearing on invertibility. - **Uniqueness of the inverse.** When a two-sided inverse exists it is unique, which is why "the" inverse is a legitimate phrase only for a bijection. A merely injective remap has many left inverses, since each unused identifier can be sent anywhere at all.

  • Why is an injective remap's inverse a partial function rather than a total one?
    Its domain is the image, not the whole target space. The new store can represent far more identifiers than the migration ever produced, and those have no old counterpart, so an inverse defined on all of them would have to invent answers. Model it as partial: given an identifier outside the image, return nothing rather than a nearest match. Making that explicit is what stops a lookup from silently attributing a freshly minted record to an old one.
  • A merging migration has no left inverse. What is the best object you can keep instead?
    The preimage of each new row — the set of old identifiers that collapsed onto it. That is a relation, not a function inverse, so it has to be stored alongside the row or in a side table; it cannot be recomputed from the new identifier once the old store is gone. Keeping it restores audit and lineage, which is what the inverse was wanted for, without pretending the mapping is reversible.
  • If a remap has a two-sided inverse, can it have more than one?
    No. A two-sided inverse of a bijection is unique: if two candidates both undo it in both directions they agree on every element, since each element has exactly one source. Merely injective remaps are different — they have many left inverses, because every identifier outside the image is unconstrained and can be sent anywhere. That is a useful tell in an interview: uniqueness of the inverse is itself a sign you are talking about a bijection.

saying these in an interview costs you the question

  • Says unique outputs alone make a remapping bijective
  • Treats the inverse as total over everything the new store can hold
  • Confuses undoing your own output with sourcing any identifier
  • Claims a merging remap can be inverted from the new identifier
  • Assumes an identifier drawn from a sequence generator still has an inverse
  • Thinks preserving sort order is what makes a mapping invertible