Why is head == tail ambiguous in a ring buffer with no count field, and how do you fix it?
answer
- count the states two indices can encode
- how many occupancies does capacity N allow?
- N separations, N+1 possible sizes
- either add state or waste a slot
- the full test versus the empty test
basics
~20 sWith two indices and all N slots usable, head == tail means empty after zero writes and full after N writes — indistinguishable. Fix it with a count field, one permanently unused slot, or non-wrapping counters.
solid answer
~50 sTwo indices in `0..N-1` express only N distinct separations between head and tail, but a buffer of capacity N has N+1 possible occupancies, 0 through N. By pigeonhole two must collide, and the collision is exactly empty versus full: both leave `head == tail`. Three standard repairs. Keep an explicit `count`: all N slots usable, full is `count == N`, cost is a third piece of state both operations must maintain. Sacrifice one slot: full is `(tail + 1) mod N == head`, no extra state, only N-1 items fit. Or let head and tail be monotonically increasing counters that never wrap, index with `counter mod N`, size is `tail - head` and full is `tail - head == N` — all N slots plus free sequence numbers, at the cost of reasoning about counter overflow.
code
pseudocode · 15 lines// a = N slots; head = oldest index; tail = next write index
is_empty():
return head == tail
enqueue(x):
a[tail] = x
tail = (tail + 1) mod N
dequeue():
x = a[head]
head = (head + 1) mod N
return x
// N enqueues, no dequeue: tail wraps exactly back onto headgo deeper
Know that head and tail alone cannot tell empty from full, and that the usual first fix is to store how many items are present. Be able to write the full test for the scheme you chose.
Derive the ambiguity from the state space — N index separations against N+1 possible occupancies — and lay out the three repairs with the capacity and state each one costs.
Read a diff and spot the mismatch: a fullness scheme that disagrees with the emptiness test, a size formula that can never report a full buffer, an overwrite path that skips the bookkeeping.
Decide which scheme a codebase standardises on and why: readable count fields by default, non-wrapping counters when consumers need sequence numbers and gap detection, and an explicit position on counter width and overflow.
## Why the ambiguity is structural, not a coding slip A ring buffer of capacity N can hold 0, 1, 2, ... N items — that is **N+1 distinct states** you must be able to read off the bookkeeping. If your bookkeeping is two indices, each in `0..N-1`, the only thing that carries occupancy information is their separation `(tail - head + N) mod N`, which takes **N distinct values**. N+1 states into N values: two states must share a representation. They do, and they are the two that matter most — a buffer with nothing in it and a buffer with no room in it both report `head == tail`. This is why the bug survives review so often. The `is_empty()` test looks obviously right, the enqueue looks obviously right, and the defect only appears when the buffer fills exactly, at which point writes silently overwrite live data or reads return slots that were never written. ## Fix 1: an explicit count Store `count` alongside the indices. Empty is `count == 0`, full is `count == N`, and both operations adjust it. - Usable capacity: all N slots. - Cost: one extra word, and a third piece of state that can drift. Every path that moves an index must move the count — the classic failure is an overwrite path that advances head and tail but forgets that count should stay the same. - Readability: highest. If the buffer is not on a measured hot path, this is usually the right answer. ## Fix 2: the sacrificial empty slot Refuse to ever fill the last slot. Then `head == tail` can only mean empty, and full is `(tail + 1) mod N == head`. - Usable capacity: N-1 items in an N-slot array. - Current size: `(tail - head + N) mod N`, which by construction can never report N — that ceiling *is* the sacrificed slot. - Cost: one slot, and nothing else. No extra state to keep consistent, which is why the scheme is a staple of small fixed-memory implementations where each index has a single owner. - Trap: allocating N slots and then advertising capacity N in the API. The advertised capacity is N-1. ## Fix 3: a fullness flag (the wrap bit) Keep one boolean. After a write, set `full = (tail == head)`; after any read, clear it. Empty is `head == tail and not full`; full is `head == tail and full`. - Usable capacity: all N slots, for one bit instead of a word. - Cost: the flag must be maintained on *every* path, including the overwrite path, and a missed path reintroduces the exact ambiguity you were fixing. ## Fix 4: non-wrapping counters Let `head` and `tail` only ever increase; they count events, not positions. Index with `tail mod N`. Then: - Size is `tail - head`, full is `tail - head == N`, empty is `tail == head`. No ambiguity at all — the counters distinguish "nothing has happened" from "N things have happened". - Usable capacity: all N slots. - Bonus: `tail` is a sequence number. A consumer that remembers the last value it read can tell exactly how many records it missed, which is worth a great deal in streaming and recording use. - Cost: the counters themselves are finite. On a 32-bit counter, roughly four billion appends later it overflows. If the counter type has well-defined wraparound and the capacity divides the counter's modulus — that is, capacity is a power of two — the subtraction `tail - head` performed in that same arithmetic still yields the correct size across the wrap, and the design survives. If wraparound is undefined for the type, or capacity is not a power of two, the size computation goes wrong at the wrap and the buffer reports absurd occupancies. ## Choosing | Scheme | Extra state | Usable slots | Full test | Main hazard | |---|---|---|---|---| | Count field | one word | N | `count == N` | count drifts from the indices | | Sacrificial slot | none | N-1 | `(tail + 1) mod N == head` | advertised capacity is off by one | | Fullness flag | one bit | N | `head == tail and full` | a path that forgets the flag | | Non-wrapping counters | none (wider indices) | N | `tail - head == N` | counter overflow | ## What the interviewer is listening for Three things. First, that you can *derive* the ambiguity from the state space rather than reciting it. Second, that for whichever scheme you pick you can state both the full test and the size formula without hesitating — those two expressions are where the off-by-ones live. Third, that you notice a diff mixing schemes: a `count` field plus a `head == tail` emptiness test is not belt-and-braces, it is two sources of truth that will eventually disagree.
- Your team picks non-wrapping counters. What breaks after roughly four billion appends on a 32-bit counter?The counter reaches its maximum and wraps. If wraparound is well defined for that counter type and capacity is a power of two dividing the counter's modulus, then `tail - head` computed in the same arithmetic still gives the correct size across the wrap, and nothing breaks. If the counter's overflow behaviour is undefined, or capacity is not a power of two, the subtraction produces a nonsense size — typically a huge occupancy that makes the buffer look permanently full.
- In the sacrificial-slot scheme, how do you compute the current number of stored items?`size = (tail - head + N) mod N`. The `+ N` keeps the intermediate non-negative before reducing. Note that this expression can return at most N-1, and that ceiling is precisely the sacrificed slot: the scheme buys unambiguous state by making the size N unrepresentable.
- A reviewer proposes a single fullness boolean instead of a count word. Does that work?Yes, for a single-threaded buffer. Set the flag after a write when `tail == head`, clear it on any read, and test `head == tail` together with the flag to separate empty from full. It costs one bit instead of a word and keeps all N slots. The risk is coverage: every path that moves an index must touch the flag, and one path that forgets — usually the overwrite path — restores the original ambiguity.
saying these in an interview costs you the question
- Tests only head == tail and calls the buffer empty
- Assumes a wrapped tail is always numerically ahead of head
- Thinks the sacrificial slot changes asymptotic cost
- Keeps a count but updates it in only one operation
- Claims comparing head < tail settles fullness