You keep one distinct-count sketch per hour: why can you not add the 24 hourly counts to get the day's distinct total?
answer
- distinctness is not additive
- returning users are counted twice
- combine the structures, not the numbers
- error is a percentage of the answer
- merge upward, never split downward
basics
~20 sAdding hourly totals counts anyone who returned in a later hour more than once. Distinct-count sketches are combined instead: merge the hourly structures into one covering the whole day, then read a single estimate from the merged result.
solid answer
~50 sDistinctness does not add up. Someone active at nine and again at three appears in two hourly answers, so the sum is an upper bound on the day, not the day. What these structures give you instead is the ability to combine them: merging the hourly sketches produces a structure equivalent to one that had been fed every item from all 24 hours, and you read one estimate from that. The reading is still an estimate — the error is quoted relative to the answer, so it is a percentage rather than a fixed number of items, and it is usually a typical deviation rather than a ceiling every reading respects. Two caveats matter in practice: merging generally requires the sketches to have been created with the same accuracy setting, and not every fixed-memory counting structure supports merging at all.
go deeper
Recall that distinct counts do not add: someone active in two hours is counted in both. The structures are combined, and the combined structure is then read once.
Explain the merge and its limits — union yes, subtraction and intersection no — and state the error as a percentage of the answer rather than a number of items.
Show the design judgment: choose the finest window anyone will ask about, put a lifetime on each window entry, and know that merging usually requires matching accuracy settings and is not offered by every structure.
Decide what tolerance each consumer is entitled to, and keep the estimate out of any number that gets reconciled or billed on, however convenient the one figure would be.
## Why the sum is not the answer A distinct count asks *how many different things were seen*, and that quantity is not additive across periods. A user active in the nine o'clock hour and again in the three o'clock hour is counted once in each hourly answer. Summing 24 hourly answers therefore gives an upper bound on the day — equal to the day's true distinct count only in the degenerate case where nobody appeared in two hours — and on a real service it overshoots badly, because returning within a day is the normal behaviour, not the exception. This is not an artefact of approximation. Adding 24 *exact* hourly distinct counts is wrong in exactly the same way. The approximation is a separate matter, discussed below. ## What a distinct-count sketch promises A **distinct-count sketch** is a fixed-memory structure with three operations: add an item, read the estimated number of distinct items added, and — usually — merge it with another sketch. It stores none of the items, so it cannot tell you *who* was seen, only roughly *how many different* things were. Its error is quoted **relative to the answer**, which has two consequences people routinely get backwards: - The error is a **percentage**, so the absolute gap grows with the count. A couple of per cent of ten thousand is a couple of hundred; a couple of per cent of ten million is a couple of hundred thousand. - The quoted figure is normally a **typical deviation, not a hard ceiling**. Individual readings can fall outside it. If your consumer needs a guaranteed bound rather than a typical one, check what the specific implementation actually claims. ## Merging, and where it stops Merging is the operation that makes windowed counting practical. Combining two sketches yields a structure equivalent to one that had been fed the items of both — the union — and you then take a single reading from it. The combination step introduces no extra loss of its own; the reading remains an estimate, which is where the error lives. That distinction is worth stating precisely, because 'merging is exact' is a claim people repeat and then over-trust. What merging does not give you: - **No subtraction.** You cannot remove one period from another to get 'who was new' or 'who left'. - **No direct intersection.** Overlap can be inferred from the union and the two individual counts, but that subtracts estimates from estimates, and when the real overlap is small the error can be larger than the quantity you are computing. - **No compatibility across settings.** Sketches generally merge only when they were created with the same accuracy parameters; and some fixed-memory counting structures offer no merge at all. Check before designing on it. - **No members.** Nothing in the merged structure identifies anyone. ## Three ways to answer 'distinct users per period' | approach | memory | answers longer windows | error | |---|---|---|---| | sum of per-hour counts | small | no — overcounts returning users | structurally wrong, not just imprecise | | merge of per-hour sketches | one fixed-size entry per hour | yes, by merging the range | the sketch's relative error on one reading | | exact collection per hour | grows with active users | yes, by union of collections | none | ## Designing the windows 1. **Pick the finest window you will ever be asked about**, because you can merge upward but never split downward. Hourly entries answer hours, days and weeks; daily entries can never answer an hour. 2. **Keep one entry per window** and put a lifetime on the entry so old windows retire themselves. The entry is the unit a lifetime attaches to, so items inside it cannot expire individually — rotation is by whole entry, not by member. 3. **Merge on read**, over exactly the windows the question covers, and treat the merged structure as throwaway. The storage story is what makes this attractive: 90 days of history is 90 fixed-size entries, whatever the traffic was. The same history in exact collections is proportional to the number of distinct users in every one of those days. ## What varies between stores Whether these structures exist server-side at all differs across this class of store — some provide them, some provide them only as an add-on, and some not at all, in which case the structure lives in the application and the store holds it as opaque bytes. Accuracy settings, whether they are adjustable, and whether merging requires matching settings likewise differ by implementation. Phrase the design as 'one fixed-size entry per window, merged on read' and it survives a move; phrase it around one implementation's parameters and it does not.
- The business now wants distinct users over a rolling 90 days. What do you store?One fixed-size sketch per day, merged across the 90 on read. Storage is 90 entries regardless of traffic, and the same entries also answer any shorter range. Exact collections for 90 days would scale with the number of distinct users in every one of those days, which is the cost the sketch exists to avoid.
- Can you get the users who were present in both of two windows?Not directly, and not by identity at all — no members are kept. The size of the overlap can be inferred from the merged count and the two individual counts, but that subtracts estimates from estimates, and when the overlap is small the error can exceed the result. An exact answer needs a structure that keeps the members.
- Why is the error described as a percentage rather than a number of users?Because the guarantee is relative to the answer: the structure's accuracy is a fraction of the count it reports, so the absolute gap grows as the count grows. Consumers who need an absolute tolerance — 'within 100 users' — are not being served by that contract at large volumes.
saying these in an interview costs you the question
- Adds per-window estimates and calls the total distinct
- Says merging is exact, so the merged answer is exact
- Assumes any two sketches merge regardless of how they were created
- Thinks subtracting one sketch from another yields the users who left
- Reads relative error as a fixed number of users at any scale
- Expects the structure to name the users behind the count