skip to content

In a rebalance where no shard may stay on its former host, what fraction of all n! reassignments qualify?

level: seniorimportance: should knowfreq 34%

answer

  1. no element may keep its original position
  2. subtract the arrangements fixing at least one
  3. the signed sum collapses to a factorial series
  4. the series is the expansion of 1/e
  5. about 37 percent, steady from n = 5

basics

~20 s

Roughly 37 percent - about 1/e - and from n = 5 onward the fraction barely moves as n grows. These no-fixed-point arrangements are derangements, counted by an alternating sum over the shards that could have stayed put.

solid answer

~50 s

Call an assignment where no shard keeps its former host a **derangement**. Count by exclusion: from all `n!` assignments, subtract those fixing at least one shard. There are `C(n,j)` ways to choose `j` shards that stay and `(n-j)!` ways to arrange the rest, so `D(n) = sum_j (-1)^j C(n,j) (n-j)!`, which simplifies to `n! x (1 - 1/1! + 1/2! - 1/3! ...)`. That bracket is the series for `1/e`, so `D(n)/n!` approaches about `0.368` and converges so fast that by `n = 5` it is within a fifth of a percentage point. Concretely `D(4) = 9` of 24 and `D(5) = 44` of 120. The practical reading: a random shuffle satisfies a no-stay-put requirement about a third of the time, so rejection sampling works but is not free, and it is not a substitute for a construction that guarantees the property.

go deeper

for a junior

Recall the idea that an arrangement leaving nothing in its original place has a name and a count, and that it is far from all or none of the possibilities.

for a middle

Explain the derivation: subtract arrangements fixing at least one shard using C(n,j)(n-j)! terms, and show why the ratio collapses to the factorial series for 1/e.

for a senior

Show what the constant buys operationally - a retry budget near three attempts, a bounded loop, a deterministic fallback - and why the fraction's independence from n is the useful part.

for a principal

Weigh whether a strict no-stay-put rule is worth its data movement at all, since it forces every shard to transfer when a partial rebalance might meet the same goal far cheaper.

## The situation A rebalancer is reassigning `n` shards across `n` hosts, and the operational rule is that **no shard may remain on the host it was on** - perhaps because the point of the move is to drain every current placement, or because staying put would defeat a hardware rotation. The natural questions are how many valid reassignments exist, and whether simply shuffling and retrying is a sane way to find one. ## Counting by exclusion Count the assignments you do **not** want, then remove them. Let `Ai` be the set of assignments in which shard `i` stays on its former host. You want the arrangements in none of the `Ai`. - Fixing one named shard leaves the other `n-1` free: `|Ai| = (n-1)!`, and there are `C(n,1)` such sets. - Fixing two named shards leaves `(n-2)!`, with `C(n,2)` choices - and these overlap the single-shard sets heavily, which is exactly why plain subtraction fails. - In general, a term built from `j` named shards contributes `C(n,j) (n-j)!`. Signed, that gives the **derangement count**: `D(n) = sum over j from 0 to n of (-1)^j C(n,j) (n-j)!` Dividing by `n!` and noting that `C(n,j)(n-j)!/n! = 1/j!` collapses it to the cleaner form: `D(n)/n! = 1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n / n!` ## Why it settles near 1/e That alternating series is the Taylor expansion of `e^x` at `x = -1`, so the ratio converges to `1/e`, approximately `0.3679`. The convergence is exceptionally fast because the error after the `n`-th term is bounded by `1/(n+1)!`: | n | D(n) | n! | ratio | |---|---|---|---| | 2 | 1 | 2 | 0.500 | | 3 | 2 | 6 | 0.333 | | 4 | 9 | 24 | 0.375 | | 5 | 44 | 120 | 0.3667 | | 6 | 265 | 720 | 0.3681 | The small cases genuinely differ - at `n = 2` exactly half the arrangements qualify - but from about `n = 5` the ratio is within a fifth of a percentage point of `1/e` and stays there. That stability is the surprising part and the part interviewers are usually probing: **the fraction does not decay as the system grows**. Intuition says that avoiding `n` separate bad events should get harder with `n`; here each individual event also gets rarer, and the two effects cancel. ## What it means operationally - **Rejection sampling is viable.** Shuffle, check for a shard that stayed, retry. The expected number of attempts is about `e`, or under three, independent of how many shards there are. - **But it is not a guarantee.** A tail of unlucky runs exists, so a retry loop needs a bound and a deterministic fallback - for instance rotating every shard one position, which trivially fixes nothing and is a valid reassignment. - **The count is not the plan.** `D(n)` says how many reassignments avoid a stay-put; it says nothing about capacity, replica placement or the data volume each move costs. Real rebalancers optimise for bytes moved under constraints, and the derangement condition is only one of them. - **Constraints compose badly.** Add a second rule - say, no shard may move to a host in its former rack - and the count needs its own signed sum over the new condition family. There is no shortcut that multiplies the two fractions, because the conditions are not independent. ## A useful cross-check Two identities make the numbers easy to verify under pressure. First, `D(n)` is the nearest integer to `n!/e` for `n >= 1`: `24/e = 8.83` rounds to 9, `120/e = 44.15` rounds to 44. Second, the recurrence `D(n) = (n-1) x (D(n-1) + D(n-2))`, from `D(1) = 0` and `D(2) = 1`, regenerates the sequence exactly: `D(3) = 2 x (1 + 0) = 2`, `D(4) = 3 x (2 + 1) = 9`, `D(5) = 4 x (9 + 2) = 44`. If a candidate's derangement figure fails both checks, the signed sum was mis-signed somewhere. ## The structure behind the small cases For `n = 4` the nine qualifying reassignments split into six that move all four shards in a single cycle and three that are two disjoint swaps. Nothing else is available: any arrangement with a 3-cycle over four shards must leave the fourth in place, and so is excluded. Being able to name that decomposition shows the count came from understanding rather than from a remembered formula.

  • A retry loop shuffles until no shard stays put - how many attempts should you budget?
    About `e`, under three on average, because roughly 37 percent of shuffles qualify and the attempts are independent. Budget a hard retry cap anyway: the distribution has a tail, and a bounded loop with a deterministic fallback - rotating every shard one position always qualifies - is safer than an unbounded retry.
  • Why does the qualifying fraction not shrink as the number of shards grows?
    Two effects cancel. There are more shards that could stay put, but each individual shard is less likely to land back on its own host. The expected number of stay-puts is exactly one for every `n`, and the probability of zero settles at `1/e` rather than drifting with size.
  • The rebalance adds a second rule - no shard may move within its former rack. Does the 37 percent still hold?
    No, and you cannot multiply the two fractions, because the conditions are not independent. The count needs a fresh signed sum over the enlarged family of forbidden placements, and the qualifying fraction generally drops sharply. This is where exact counting gives way to a constructive placement algorithm.

It is the gift-exchange draw where nobody may draw their own name: with more than a handful of participants, a random draw works about a third of the time, and that odds figure stops changing however many people join.

saying these in an interview costs you the question

  • Claiming the qualifying fraction shrinks toward zero as n grows
  • Saying half of all shuffles avoid a stay-put shard
  • Subtracting the single-shard cases once and calling it exact
  • Treating a derangement count as a rebalancing plan
  • Multiplying two constraint fractions as if independent