Design Ad Frequency Capping

Understanding the problem

A viewer on the ad-supported plan starts an episode. Before the stream fills an ad slot, something has to decide which ad to show. Part of that decision is a limit: this viewer has already seen the same car ad four times today, so do not show it a fifth. That limit is a frequency cap. The prompt is to design the system that enforces it. Cap how many times a given viewer sees a given ad or campaign over a rolling window, and do it inside the split second the player has before the slot has to be filled.

Name the hard part before drawing a box. The cap itself is arithmetic. A counter, a limit, a comparison. What makes this a system is where the counter lives and how fast you can read it. Every ad request asks the cap a question, so the read sits on the hottest path in the ad stack and has a latency budget measured in milliseconds. The counter is written from a different place, when an impression plays, and there are a lot of viewers, a lot of campaigns, and more than one server counting. So the design is a distributed counter keyed by viewer and campaign. A fleet of ad servers reads it on every request and increments it on every impression, without the count drifting or the read blowing the budget.

The Netflix angle

Netflix runs an ad-supported plan, and it is building the ad-serving stack that fills those slots in-house rather than renting it. A Netflix TechBlog post on building its ads event processing pipeline describes the piece this prompt covers: a frequency capping service that tracks impressions per campaign and profile, which the Ad Server checks on each ad decision. That is why this shape shows up in the loop and why the interviewer treats it as a real system, not a toy counter. Two instincts land here. First, respect the latency budget out loud. The cap is read on the ad-serving path, so a design that pauses to run a consistent read against a database on every request has already failed. Say why before you are pushed. Second, be honest about consistency. The count you read is a few impressions stale by nature, because impressions are logged after they play. Decide what a small overshoot on a cap costs, and design for that answer instead of reaching for a strong guarantee the budget cannot pay for.

Bounding the requirements first

Spend a minute bounding the problem, because "frequency capping" hides several caps and the scope decides the design. State the functional surface plainly. On every ad request the system answers one question: may this viewer be shown this campaign right now, given how many times they have already seen it inside the window. It records an impression when an ad plays, not when it is merely selected, because a selected ad that never renders must not burn a viewer's cap. It holds a count per viewer and per campaign, and often per creative inside a campaign, over a rolling window such as a day or an hour. And it serves that verdict fast enough to sit on the ad-selection path without slowing it.

Then draw the line around what you build now and what you name and defer. Real ad systems carry a stack of caps at once: a per-creative cap, a per-campaign cap across all its creatives, a per-advertiser cap, and pacing rules that spread a budget across the day. Deriving all of them in the first pass guarantees you run out of time before the counter is clean. Build the single rolling-window cap on one viewer-and-campaign pair as the core, and make the design so the others have an obvious home. A design where "add a per-advertiser cap on top" means keying the same counter differently is a good design. One where it means rewriting the read path is not.

• The grading axis: hot-path reads at scale. This cap is queried on every ad request across a fleet of servers, so the design is graded on serving the verdict inside a millisecond budget, not on the arithmetic of a counter. When you reach a fork, keep the read fast and say what you traded for it.
• Count the impression, not the choice: log on render, not on select. An ad that is selected but never plays must not consume the viewer's cap. The increment fires when the impression renders and is confirmed, which is why the write path is separate from and slower than the read.
• The counter is keyed: by viewer and by campaign. The natural key is the pair of a canonical viewer id and a campaign id, with a finer creative id when a campaign has several ads. Keying it this way is what lets the same store carry a per-creative, per-campaign, or per-advertiser cap without a new mechanism.
• The window rolls: a moving span, not a calendar reset. A cap of three per day usually means three in the last twenty-four hours, not three since midnight, so the count ages impressions out continuously. The rolling shape drives the algorithm choice and the memory it costs.

The counter store, keyed by viewer and campaign

Start from the state, because the whole system is one small piece of state read and written a great many times. The unit is a count of impressions for one viewer on one campaign inside the window. The key is the pair of ids, the viewer and the campaign, and the value is however you represent "how many, and recently enough to still count". Underline that noun. The store is a map from a composite key to a windowed count, living in memory close to the ad servers so a read is a lookup rather than a query.

The decision that makes the store correct rather than merely fast is treating the count as derived from a stream of impression events, not as a number you mutate blindly. An impression is a fact that happened at a time. The count for a viewer-and-campaign pair is the number of those facts that fall inside the current window. Keep that framing and two things follow. The verdict is always a function of the events and the clock, so an old impression falling out of the window lowers the count on its own. And the store can be rebuilt from the durable impression log if the in-memory counter is lost, which is what keeps a cache failure from erasing every viewer's history.

// The key is the PAIR that scopes the cap: one viewer, one campaign. The same
// key shape carries a per-creative cap (add the creative id) or a per-advertiser
// cap (swap the campaign id for the advertiser id) with no new mechanism.
final class CapKey {
    final String viewerId;    // the CANONICAL viewer, resolved across devices
    final String campaignId;  // the thing the cap is counted against
    // equals + hashCode over both fields: this is the map key
}
// The value is a WINDOWED count, not a bare integer. It is derived from the
// impressions that fall inside the rolling window, so an impression aging out
// of the window lowers the count without anyone decrementing it by hand.
final class WindowedCount {
    // the ticks at which impressions played, only those still inside the window.
    // bounded by the cap, because once the cap is hit no more are recorded.
    final Deque<Long> impressions = new ArrayDeque<>();
    int countAt(long now, long window) {           // how many still count at 'now'
        while (!impressions.isEmpty() && impressions.peekFirst() <= now - window)
            impressions.pollFirst();               // drop what has aged out
        return impressions.size();
    }
}

Defend two details in that snippet out loud. The viewer id is the canonical viewer rather than the device. A cap that counts per device lets the same person see the same ad on the phone and again on the television without either count knowing about the other. Cross-device identity is what makes the cap mean what a viewer expects, and it is a real piece of the problem, not a footnote. And the value is a windowed structure rather than a single number, because a plain integer cannot answer "how many in the last twenty-four hours" once impressions start aging out. The window is the reason the count is a small structure and not a counter you only ever increment.

Rolling-window algorithms, and what each costs

The window is where the interviewer will push, because "three per day" can mean two very different things and the memory bill depends on which. The simple reading is a fixed window: reset the count at a calendar boundary, midnight say, and count impressions since then. It is one integer per key and it is cheap. It also has the boundary burst everyone who has built one knows. A viewer can see three ads at 23:59 and three more at 00:01, six in two minutes, because the reset does not care that they clustered around the edge. For a daily brand cap that is often acceptable. Say the flaw plainly and let the requirement decide.

The honest rolling window is a sliding window, and it comes in two forms. The exact form keeps the timestamps of the impressions inside the window and prunes the ones that have aged past it, so the count is precisely "how many in the last twenty-four hours" at any instant. It is exact, and its memory is bounded by the cap, because once a key hits its cap you stop recording. The approximating form keeps a small set of sub-buckets, one per hour of a daily window, and slides the set forward as time passes, trading a little precision at the edges for a fixed, tiny footprint per key. Reach for the exact log when caps are small, which they usually are, and name the bucketed approximation as the move when a key must stay constant-size regardless of the cap.

The system end to end

Lift the counter into a running system and draw it, because the design is really the split between the fast read on the ad request and the slower write when the impression plays. Read the diagram by role. Blue is the outside world, the ad request arriving and the ad being served. Indigo is the services that transform: identity resolution, ad selection, and the cap check itself. Violet is the policy step that turns counts into a verdict. Amber is the impression log stream. Green is the state the system owns, the hot counter store and the durable impression store behind it. Follow the numbered edges for one full request. The request resolves to a canonical viewer, and selection asks the cap check whether a candidate campaign is under its limit. The check reads the counters, the verdict comes back, and the winning ad is served. Only then, asynchronously, is the impression logged, the counter incremented, and the durable store appended.

The read path and its latency budget

The cap check sits on the ad-serving path, and that one fact shapes every choice under it. When a slot opens the player cannot wait, so the whole ad decision runs inside a budget measured in milliseconds, and the cap check is only one step in it. That rules out the obvious first design, a strongly consistent read against a database on every request, because a cross-network consistent read spends the budget many times over. The counter has to live in memory, close to the ad servers, so the read is a local lookup. Everything else in this section falls out of protecting that lookup.

Now put the counter behind more than one server, because a single in-memory counter is a single point of failure and cannot hold every viewer. Shard the counter store by the key, the viewer-and-campaign pair, so each shard owns a slice of the keyspace and any ad server can reach the shard that holds a given key. That keeps the read a single hop to one shard. The write is the subtle part. Incrementing a shared counter is a read-modify-write, and if two impressions for the same key land at once and each reads the old value before writing, one increment is lost and the cap counts short. So the increment has to be atomic on the store, an atomic add rather than a read-then-write, the same way a distributed rate limiter makes its check-and-increment one step. Say that out loud, because a lost increment is a cap that quietly overshoots.

Caps, consistency, and cross-device identity

Say the consistency call plainly, because it is the judgment the round is set to find. The count you read is not the true count. Impressions are logged after they play and the increment lands a beat later, so a read on the hot path is a few impressions behind reality by design. That means a cap can overshoot slightly: a viewer might see the ad one extra time when several impressions are in flight at once, or across two servers that have not yet seen each other's increments. The right response is not to reach for a strong guarantee. It is to decide what that small overshoot costs. For a brand-awareness cap, one extra impression is invisible and a strongly consistent read would trade the whole latency budget to prevent a harm nobody feels.

So the default is eventual consistency on the read, with strong consistency reserved for the caps where an overshoot is expensive. Some caps are contractual: a hard limit an advertiser paid for, or a legal ceiling on a sensitive category. There the extra impression is a real cost. Those specific caps warrant a tighter path, a per-key serialized increment or a consistent read for that campaign only, paid for on the small slice of traffic that needs it. Cross-device identity feeds the same trade. Resolving a request to one canonical viewer is what makes the cap count the person and not the screen. That resolution can itself be slightly stale, so a viewer who just switched devices might briefly be counted twice. Name it, and treat it the way you treat the counter: eventually correct is fine for a brand cap, worth tightening only where an overshoot is billed.

• The read is stale by design: a few impressions behind. Impressions are logged after they play and the increment lands a beat later, so the hot read trails reality. This is the deliberate cost of keeping the read a local lookup rather than a consistent query, and it is why a cap can overshoot slightly under concurrent impressions.
• Default to eventual consistency: the overshoot is usually cheap. For a brand-awareness cap, one extra impression is invisible, so trading the latency budget for a strong guarantee buys nothing. Eventual consistency on the counter is the right default, and saying why is the judgment the round rewards.
• Reserve strong caps for hard limits: pay for it only where it bills. A contractual or legal ceiling makes an overshoot a real cost. Those specific campaigns get a tighter path, a serialized increment or a consistent read, on the small slice of traffic that needs it rather than for everyone.
• Cross-device identity: count the viewer, not the screen. Resolving a request to one canonical viewer makes the cap follow the person across phone and television. The resolution can be slightly stale, so a just-switched viewer may briefly double-count, which is fine for a brand cap and worth tightening only where it bills.

The runnable core: a rolling-window frequency capper

Real serving is concurrent and distributed, so a runnable version cannot be the sharded counter itself, it would pass or fail by luck of the scheduler. Pull out the part that is deterministic and testable: the rolling-window accounting the whole system is built to protect. Pass the current tick in explicitly rather than reading a clock, so the verdict is a function of its inputs and runs the same way every time, the way a real harness injects time. The sharding and the atomic increment live in the prose above; the runnable below is the single-key contract every shard must honor, one viewer-and-campaign pair at a time.

The mapping is direct. Each viewer-and-campaign key has its own rolling window of impression ticks. A call to allow prunes the impressions that have aged out of the window ending at the current tick. If the remaining count is under the cap, it records this impression and returns true, or leaves the count alone and returns false when the cap is already met. Get the window boundary, the at-cap denial, and the per-key independence right and you have written the exact accounting a shard enforces under load. The impression exactly at the window edge and the key that is already full are the whole exercise, the way the boundary case is the whole exercise in a hit counter.

1

Frequency capper: the rolling-window contract, per viewer and campaign

Medium

Problem

Implement a rolling-window frequency capper for ad impressions. Each viewer-and-campaign pair may be shown a campaign at most cap times within any rolling window of window ticks. Time is passed in explicitly so the behavior is deterministic.

- FrequencyCapper(cap, window) creates a capper where any viewer may see any campaign at most cap times inside a window of window ticks.
- allow(user, campaign, nowTick) is called when an ad slot for campaign could be filled for user at time nowTick. First discount the impressions for that viewer-and-campaign pair that have aged out of the window, meaning every recorded tick t with t <= nowTick - window. Then, if the remaining count is below cap, record an impression at nowTick and return true (the ad may be shown); otherwise record nothing and return false (the viewer is capped out). An impression exactly window ticks old has aged out and no longer counts.

The window boundary, the at-cap denial, and per-key independence are the whole exercise. An impression exactly window ticks old must not count, and a key at its cap must deny and record nothing. One viewer-and-campaign pair must never touch another's count. Assume nowTick never goes backwards for a given key.

Input encoding. A test case is a JSON array of operations. The first entry is ["FrequencyCapper", [cap, window]]; each later entry is [method, [args]]. The expected array holds each operation's return, with null for the constructor.

Input: FrequencyCapper(2,10); allow("u","c",0); allow("u","c",0); allow("u","c",0); allow("u","c",10)

Output: true, true, false, true

Cap 2, so the first two impressions at tick 0 are allowed and recorded, and the third at tick 0 is denied because the pair is already at its cap. At tick 10 the two impressions at tick 0 have aged out (0 <= 10 - 10), so the count is back to zero and the ad may be shown again.

Input: FrequencyCapper(1,5); allow("u","c",0); allow("u","c",4); allow("u","c",5); allow("u","c",6)

Output: true, false, true, false

Cap 1. The impression at tick 0 is allowed. At tick 4 the pair is still capped, so it is denied. At tick 5 the tick-0 impression has aged out exactly at the window edge (0 <= 5 - 5), so the ad is allowed and recorded. At tick 6 that new impression at tick 5 still counts, so the request is denied.

How this uses the pattern

Keep a map from the (user, campaign) pair to a queue of impression ticks. On allow, drop every tick that is <= nowTick - window from the front, then compare the remaining count to the cap: if below, append nowTick and return true, else return false. A first-seen pair starts empty.

Frequency capper: the rolling-window contract, per viewer and campaign

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [["FrequencyCapper",[2,10]],["allow",["u","c",0]],["allow",["u","c",0]],["allow",["u","c",0]],["allow",["u","c",5]],["allow",["u","c",10]],["allow",["u","c",11]]]Expected: [null,true,true,false,false,true,true]

Input: [["FrequencyCapper",[1,5]],["allow",["u","c",0]],["allow",["u","c",4]],["allow",["u","c",5]],["allow",["u","c",6]]]Expected: [null,true,false,true,false]

Input: [["FrequencyCapper",[1,100]],["allow",["u","c1",0]],["allow",["u","c2",0]],["allow",["u","c1",0]],["allow",["u","c2",5]],["allow",["u","c1",100]]]Expected: [null,true,true,false,false,true]

Input: [["FrequencyCapper",[2,10]],["allow",["u1","c",0]],["allow",["u1","c",0]],["allow",["u1","c",1]],["allow",["u2","c",1]],["allow",["u2","c",1]],["allow",["u2","c",1]]]Expected: [null,true,true,false,true,true,false]

Input: [["FrequencyCapper",[3,10]],["allow",["u","c",0]],["allow",["u","c",2]],["allow",["u","c",4]],["allow",["u","c",5]],["allow",["u","c",11]],["allow",["u","c",13]]]Expected: [null,true,true,true,false,true,true]

Need a hint? (3 available)

The Netflix angle

This is the correctness core of the frequency-capping design reduced to what runs deterministically. Netflix cares that the rolling window is exact and the cap holds. On the sharded, concurrent version, those are the invariants the atomic increment protects. An off-by-one at the window edge is a viewer seeing an ad one time too many or too few. The interviewer is watching three things survive the tests: an impression exactly at the window boundary that must age out, a key at its cap that denies and records nothing, and viewer-and-campaign pairs that keep fully separate state. State those invariants before you code, and drive the boundary cases yourself: fill a key to its cap, let the window roll exactly to the edge, and interleave two keys to prove one never spends the other's count.

Take it further

The natural Netflix extension puts the systems concerns back. Make it distributed without blowing the latency budget: shard the counter by the viewer-and-campaign key so a read is one hop. Make the increment a single atomic add rather than a read-then-write. Otherwise two impressions for one key landing at once race away a count and let the cap overshoot. Then decide the consistency posture per cap: default to an eventually consistent read since a brand cap overshooting by one impression costs nothing. Give a contractual or legal ceiling a tighter serialized path on just its traffic. Finally, swap the exact impression log for a bucketed window when a key must stay constant-size regardless of the cap, and say what precision you trade for the fixed footprint.

Show solution & walkthrough

Ad selection, scale, and failure

The cap does not live alone, so say how it plugs into ad selection, because a cap that returns the right verdict but wires in wrong still fails the round. Selection generates candidate campaigns from targeting and pacing. The cap check is a filter over that candidate set: for each candidate, ask whether the viewer is under its limit, drop the ones that are capped out, and rank what survives. Keeping the cap a filter that selection consults, rather than logic baked inside selection, is what lets the two evolve apart, and it is why the check is read-only and cheap. The impression event flows the other way, emitted when the ad renders, and that is the only thing that moves a counter.

Then walk the failure and scale modes out loud, because on a live ad path they are routine. The counter store browns out. The check has to choose: fail open and let the ad show, risking a small overshoot, or fail closed and skip the ad, losing revenue on a slot that was fine. For a brand cap, failing open is usually right, and saying which way you fail and why is the reliability instinct the room wants. A hot campaign concentrates load on the shards holding its keys, so the key includes the campaign and spreads across shards rather than piling onto one. The durable impression log lags the live counter, so the two are reconciled and the counter rebuilt from the log after a loss, rather than trusted blindly. An impression is logged at-least-once on a real stream, so the counting tolerates a duplicate. It either dedupes on an impression id or accepts that a rare double count is cheaper to absorb than to prevent on a brand cap.

The Netflix angle

The instinct that reads as a Netflix hire is to design for the request that is happening a million times over, not the clean single one. Say out loud that the read is a local lookup because it sits in the ad-serving budget. The count is eventually consistent, because a brand cap overshooting by one costs nothing and a consistent read would spend the whole budget. The increment is atomic, because a lost one is a cap that silently overshoots. Then say how you would prove it and how it degrades. Reconcile the live counter against the durable impression log so drift surfaces. Decide the fail-open-or-closed posture per cap from what the cap is protecting, a brand impression versus a contractual ceiling. A candidate who reasons about the counter under a show-release traffic spike with a shard running hot, rather than only the calm single-viewer case, is showing the availability judgment this loop probes harder than most.

What the round rewards

The bar on this design is a fast, correct cap reasoned from the counter and the read path, not raw throughput math. Whichever ad-domain prompt you draw, a frequency cap, a pacing system, an audience filter, the moves are the same. Model the state first, a count keyed by viewer and campaign derived from a stream of impressions, so the window and the rebuild come almost for free. Pick the window algorithm from the requirement and know the memory each costs, the fixed window and its boundary burst, the exact sliding log bounded by the cap, and the bucketed approximation with a constant footprint. Keep the read a local lookup inside the latency budget, shard the counter by its key, and make the increment atomic so concurrent impressions cannot race a count away. Choose the consistency posture deliberately, eventual by default because a brand overshoot is cheap, strong only where a cap bills. Resolve to a canonical viewer so the cap counts the person and not the screen. And name the failure modes yourself, a browning counter store, a hot campaign, a lagging log, a duplicated impression, because on a live ad path those are the design, not the footnotes. Show that judgment and the ads skin sits naturally on top.