A URL shortener indexes buckets with hash % bucketCount and crashes on a negative index — why?
answer
- half of all hash values are negative
- which operand's sign does remainder follow
- the fix everyone reaches for first
- count the negatives versus the positives
- one value that negation cannot flip
basics
~20 sHash values are signed fixed-width integers, and the remainder operation takes the sign of the dividend, so a negative hash yields a negative index. Taking the absolute value does not fix it: the most negative representable value has no positive counterpart and stays negative.
solid answer
~50 sThe hash function returns a signed fixed-width integer, so roughly half of all keys produce a negative value. In most arithmetic, remainder truncates toward zero and keeps the sign of the dividend, so `h % m` is negative whenever `h` is — and indexing a bucket array with it faults. The obvious patch, `|h| % m`, is the trap: in two's-complement arithmetic the range is asymmetric, so the single most negative value has no positive counterpart and negating it returns itself, still negative. That leaves a bug that fires on about one key in four billion — invisible in tests, and eventually a crash in production on a specific short URL that then fails forever. The correct reductions are a floored modulus, `((h % m) + m) % m`, or clearing the sign bit with a mask before reducing. Both are branch-free and deterministic.
code
pseudocode · 12 linesh = hash(key) // signed, fixed width: often negative
idx = h % m // remainder keeps the sign of h
bucket = table[idx] // negative index -> fault
// reflex patch, still not total:
idx = |h| % m // for the single most negative value,
// negation overflows to itself -> still < 0
// total forms:
idx = ((h % m) + m) % m
idx = (h & 0x7fffffff) % m // clear the sign bit, do not negatego deeper
Know that hash values are signed and can be negative, and that a remainder keeps the sign of the value being divided, so the index can come out below zero.
Explain the two's-complement asymmetry: there is one more negative value than positive, so negating the most negative value returns itself. Give a reduction that is total for every input.
Show how you would find this from a production symptom — one specific key failing deterministically while everything else works — and how you would test it, by exercising the reduction at the type's extreme values rather than with random keys.
Make the reduction a single reviewed helper used everywhere rather than an expression rewritten per call site, and treat numeric-boundary reasoning as a standing review item, since this failure class costs far more to diagnose in production than to prevent.
## Where the negative comes from A hash function's output type is a fixed-width signed integer in the great majority of designs. Any decent hash mixes bits thoroughly, which means the top bit — the sign bit — is set about half the time. So about half of all keys hash to a negative number. This is not a defect in the hash; it is the expected consequence of using the full output range. The bug appears at the reduction step, where the hash value is converted into a slot index. The textbook formula is `index = h mod m`. In mathematics, `mod` always yields a result in `0..m-1`. In machine arithmetic, the common remainder operation is defined by truncating division, which makes the remainder carry the **sign of the dividend**. So `-17 % 8` is `-1`, not `7`. Index a bucket array with `-1` and you get a fault on the very first request whose key happens to hash negative. In the URL shortener this is characteristic: the service works in development against a handful of seeded links, then throws on a real short code the moment traffic is real, because the crash is keyed to the specific string. ## Why the obvious fix is worse than no fix The reflex patch is to take the absolute value first: `index = |h| % m`. It looks total. It is not, and the reason is worth being exact about. Two's-complement representation is asymmetric. For a width of `w` bits the representable range is `-2^(w-1) .. 2^(w-1) - 1`: there is one more negative value than there are positive ones. Negation is implemented as invert-and-add-one, and applying it to the most negative value overflows back to itself. So for exactly one input out of `2^w`, the absolute value is still negative, and `|h| % m` is still negative. What that buys you is a crash whose probability is about one in four billion per key for a 32-bit hash. It will not appear in a unit test, will not appear in a load test with synthetic keys, and will appear one afternoon in production on a single short code — which then fails deterministically, forever, for that one link, while every other link works. Chasing that from a stack trace alone is a genuinely hard afternoon. This is why the pattern is a standing review item rather than a curiosity. ## Reductions that are actually total Two correct forms, both cheap: - **Floored modulus:** `index = ((h % m) + m) % m`. The inner remainder lands in `-(m-1) .. m-1`; adding `m` makes it non-negative; the outer remainder brings it back under `m`. Total for every input, and it preserves the full spread of the hash. - **Clear the sign bit:** mask off the top bit before reducing, e.g. `index = (h & 0x7fffffff) % m` for a 32-bit hash. This is not the same operation as taking an absolute value — it reinterprets rather than negates, so the most negative value maps to zero instead of overflowing. It costs one instruction and halves the effective range, which is harmless when `m` is far smaller than the range. A third option, where the language offers it, is to hold the hash in an unsigned type or apply an unsigned reduction, which removes the question entirely. ## The general lesson to state out loud The interviewer is not really testing whether you memorised an idiom. They are testing whether you treat the reduction from hash value to slot index as a place where a total function is required, and whether you reason about the boundaries of a numeric type rather than about its typical values. The family this bug belongs to is the same one as `mid = (lo + hi) / 2` overflowing in binary search, and as a length subtraction underflowing on an empty range: an expression that is correct across the whole domain you imagined, and undefined at the one edge of the domain the type actually has. The habit that catches all of them is asking, for every arithmetic step on a value you did not construct, what happens at the extreme values of the type — then adding a test at exactly those values, since random testing will never reach them.
- How would you write a test that catches this, given random keys never will?Test the reduction function directly rather than through the table. Feed it the extreme values of the hash type — the most negative value, minus one, zero, and the maximum — for several bucket counts, and assert the result lies in 0..m-1. Boundary values must be enumerated deliberately; a random or property test with uniform inputs will essentially never generate them.
- Does clearing the sign bit hurt the distribution?Not measurably, when the bucket count is far smaller than the hash range. Masking discards one bit of entropy and folds the negative half of the range onto the positive half, but the remaining bits still feed the reduction. It is a different operation from negation: it reinterprets the value rather than flipping it, so it is total by construction.
- What other everyday algorithm bugs come from the same type-boundary blind spot?The classic is computing a midpoint as the sum of two indices divided by two, which overflows once the sum exceeds the type's maximum even though both indices are valid. Subtracting sizes that can underflow on an empty range is another. All share the shape: arithmetic that is correct for typical values and undefined at the type's edges.
saying these in an interview costs you the question
- Assumes remainder always returns a non-negative result
- Fixes it with an absolute value and calls it total
- Claims a good hash never produces negative values
- Adds a branch that only rechecks after the faulty reduction
- Dismisses a one-in-four-billion bug as not worth handling