A 'same customer' rule matches names within one edit, so Jon matches Jan and Jan matches Ian: what breaks when you group with it?
answer
- reflexive and symmetric, one missing
- distance is not transitive
- no classes, only a procedure
- order decides the groups
- chains fuse distinct people
basics
~20 sThe rule is reflexive and symmetric but not transitive, so it has no equivalence classes. 'The group of a row' stops being a property of the data and becomes a property of the traversal order, and chains of near matches fuse distinct people.
solid answer
~40 sA distance threshold is reflexive (distance zero) and symmetric (distance is symmetric), but not transitive: Jon and Jan differ by one edit, Jan and Ian by one edit, and Jon and Ian by two. Without transitivity the relation induces no partition, so there is no such thing as 'the group containing Jan' — there is only whatever grouping the algorithm that walked the pairs happened to produce. Two consequences follow. The result is **order dependent**: change the input order, the shard boundaries or the number of workers and the groups change. And it is **not idempotent**: feeding merged output back in merges more. Tightening the threshold does not fix it, because two rows at distance `t` from a third can sit `2t` apart at any positive `t`.
code
pseudocode · 21 linesgroups = empty list
for each row in stream:
target = first group g in groups
such that some member m of g matches row
if target exists:
add row to target
else:
append new group [row] to groups
// stream Jon, Ian, Jan:
// Jon -> new group [Jon]
// Ian -> matches nothing (Jon is 2 edits away) -> new group [Ian]
// Jan -> matches Jon -> joins it
// result: [Jon, Jan] and [Ian]
// stream Jan, Jon, Ian:
// Jan -> new group [Jan]
// Jon -> matches Jan -> joins it
// Ian -> matches Jan -> joins it
// result: [Jan, Jon, Ian]go deeper
Recall the counterexample shape: two names one edit apart, each one edit from a middle name, two edits from each other. That single triple is what breaks the rule.
Explain why the missing property matters: without transitivity there are no classes, so the emitted groups come from the procedure that walked the pairs rather than from the rule itself.
Diagnose it from symptoms — customer counts that differ between runs, a merge that keeps merging when re-run, one implausibly large group — and connect each symptom to order dependence or chaining.
Decide what the platform does with a relation that cannot be an equivalence, rather than tuning it: which relation is allowed to define identity, and which is allowed only to propose candidates.
## Why the rule is not an equivalence The rule is 'edit distance between the names is at most 1'. Check the three properties honestly: - **Reflexive** — a name is at distance 0 from itself, and 0 is at most 1. Holds. - **Symmetric** — edit distance does not care which string you start from. Holds. - **Transitive** — fails, and a three-row witness proves it. Jon to Jan is one substitution. Jan to Ian is one substitution. Jon to Ian is two substitutions, which is over the threshold. One witness is enough. The rule is a **tolerance relation** — reflexive and symmetric, not transitive — and tolerance relations do not partition anything. ## What 'the group of a row' even means now With an equivalence relation, the class of a row is defined by the relation alone: collect everything the row matches and you are done, because symmetry and transitivity guarantee that everyone in that collection agrees on the same collection. Remove transitivity and that guarantee evaporates. Jan matches both Jon and Ian, but Jon and Ian do not match each other, so there is no set that everyone in it agrees on. What the pipeline emits is therefore not 'the classes of the rule'. It is the output of a specific procedure, and different procedures give different answers on the same data: | Procedure | What it emits for Jon, Jan, Ian | |---|---| | first match wins, streaming | depends on arrival order: either two groups or one | | close the relation under chaining | one group of three | | require every pair inside a group to match | two overlapping candidates, and you must break the tie by some rule the matcher never supplied | None of these is wrong as code. The point is that the *rule* no longer determines the answer, so the answer is an implementation detail masquerading as a fact about customers. ## The two failure signatures **Order dependence.** A streaming first-match grouper places a row into the first existing group containing a member it matches. Feed it Jon, Ian, Jan and you get two groups; feed it Jan, Jon, Ian and you get one group of three. Same data, same matcher, different result. In practice the order is set by shard boundaries, worker counts, retry paths and sort order, none of which are stable — so the same nightly job produces different customer counts on different nights and nobody can reproduce yesterday's output. **Chaining.** If instead you close the relation under chaining, every near match becomes an actual merge, and a run of small differences walks across the data set. It only takes `n - 1` linking pairs to collapse `n` distinct records into one, so a dense neighbourhood of similar names — which is exactly what a real customer table contains — produces one enormous group that merges people who share nothing. ## Thresholds do not repair it Candidates reach for tuning: lower the threshold. The arithmetic says no. If the rule is 'distance at most `t`' and `a` is at distance `t` from `b`, and `b` is at distance `t` from `c`, then `a` and `c` may sit at distance `2t`, which fails the rule for every `t` greater than 0. Lowering `t` makes the chains shorter and the misses more numerous; raising it makes the chains longer. The failure is structural, not a parameter value. The single threshold that is transitive is `t = 0` — exact equality of the compared value — and that is a different rule: comparing a derived value for equality is an equivalence for free, because equality of values is one. ## What the failure costs downstream Because the grouping is not a property of the data, nothing derived from it is stable either: customer counts, per-customer aggregates, the identifier other systems store. Re-running the merge over its own output merges more, so 'run it again' is not a safe recovery step and the record count drifts down with every pass. A row can be reported as the same customer as one row and a different customer from another row that matched the first — an answer that is coherent for a similarity score and incoherent for identity. The honest reading is that a near-match rule is a good *candidate generator* and cannot be an *identity relation*; treating the two as the same object is the defect.
- Does tightening or loosening the edit threshold restore transitivity?Neither. For a rule 'distance at most `t`', two rows at distance `t` from a common third row can be `2t` apart, which fails the rule for every positive `t`. Loosening lengthens the chains, tightening shortens them and loses genuine duplicates, and only `t = 0` — exact equality of a derived value — is transitive, which is a different rule.
- Two runs over identical input produce different groupings. What in the pipeline explains it?The order the pairs were consumed: shard boundaries, worker counts, retry paths or a changed sort. With a non-transitive rule the grouping is a property of the traversal rather than of the data, so anything that perturbs the traversal perturbs the output — and no amount of determinism in the matcher itself removes that.
Standing within arm's reach of your neighbour does not put everyone in a queue within arm's reach; a chain of near neighbours spans the whole room while the two ends have never met.
saying these in an interview costs you the question
- Says a lower threshold restores transitivity
- Claims the classes exist but are expensive to compute
- Thinks a deterministic matcher makes the grouping deterministic
- Assumes re-running the merge is idempotent
- Treats chained merges as tuning rather than structure
- Believes symmetry alone makes group membership well defined