skip to content

A news feed caps each outlet at two items per page, yet one outlet fills four consecutive slots - how did that happen?

level: middleimportance: should knowfreq 44%

answer

  1. each page obeyed the cap independently
  2. the boundary is invisible to the reader
  3. count slots, not pages
  4. the look-back must cross the request
  5. carry the tail in the cursor

basics

~20 s

The cap's window is the page, and the window resets at the page boundary. Slots nine and ten of the first page plus slots one and two of the second are four in a row to a scrolling reader, because the second request counted from zero.

solid answer

~40 s

The quota is being enforced per request. Each page is a separate, stateless call, so the second one starts its outlet counters at zero and is free to place two more items from the outlet that just finished the previous page - four consecutive slots, with every page individually obeying the cap. The fix is to make the window a **span of slots rather than a page**: "at most two of this outlet in any five consecutive slots", with the tail of the previously served slate carried forward in the pagination cursor so the next request can continue counting. A page-level cap constrains the *count* on a page; a sliding slot window constrains the *spacing* a reader actually perceives.

code

pseudocode · 19 lines
pseudocode
WINDOW = 5                       # measured in slots, not pages
MAX_IN_WINDOW = 2

placed = decodeTail(cursorIn)    # last WINDOW-1 slots already shown to this reader
slate = []

for each c in candidatesByScore:
    if length(slate) == SLOT_COUNT:
        break

    lookBack = lastN(concat(placed, slate), WINDOW - 1)
    sameOutlet = count of items in lookBack where outlet(item) == outlet(c)

    if sameOutlet >= MAX_IN_WINDOW:
        continue                 # defer: c keeps its score and stays eligible below

    append c to slate

cursorOut = encodeTail(concat(placed, slate), WINDOW - 1)

go deeper

for a junior

Recall that each page of a feed is a separate request, so a limit expressed per page starts counting again on the next one.

for a middle

Do the arithmetic and name the fix: a window measured in slots, a look-back that spans requests, and the tail of the previous slate carried in the pagination cursor.

for a senior

Anticipate what breaks in production - reused cursors, prefetched pages that are never shown, a client that re-sorts, and starvation of an outlet that dominates the shortlist.

for a principal

Decide what the constraint is really about - the column, the visit, or a commercial commitment - because that choice, not the code, determines where the state has to live.

## Why the cap leaked Nothing was violated. Page one held two items from the outlet; page two held two. The cap held on both. What failed is the assumption that the reader experiences pages - they experience a continuous column of slots, and a boundary that is real to the server is invisible to them. The arithmetic is worth doing explicitly, because interviewers ask for it. With a cap of `2` per page and a page of ten, the worst case is the outlet taking slots **9 and 10** of page one and slots **1 and 2** of page two: **four** consecutive. A cap of three per page would give six. The general form is `2 * cap` consecutive slots at any boundary. ## Window over slots, not over pages The repair is to define the constraint on the axis the reader sees: 1. Pick a window measured in **slots** - for example, at most two items from one outlet in any five consecutive slots. 2. When placing slot `n`, look back over the last `window - 1` placed items, regardless of which request placed them. 3. If the outlet already appears at the limit inside that look-back, defer the candidate and try the next one. 4. Carry the tail of the slate forward so the next request can perform step 2 across the boundary. Step 4 is the one people forget, and it is the whole fix. ## Carrying the state across a stateless request Each page is its own request, so the look-back has to come from somewhere: | approach | where the state lives | holds across | main cost | |---|---|---|---| | page-level cap | nowhere | a single response | leaks at every boundary | | cursor-carried window | encoded in the pagination cursor the client returns | one continuous scroll | cursor grows; a reused or edited cursor lies | | session counter | a low-latency key-value store keyed by session | a whole session, across devices sometimes | an extra read on the serving path, and a write | The cursor is the usual choice for a scroll, because it keeps the serving path stateless and the state is exactly as long-lived as the scroll. A session counter is what you reach for when the constraint is about the whole visit rather than the current column - "no more than six from this outlet today" - and it buys that at the price of a read and a write per request. ## What the window does to relevance A tighter window costs more relevance than a looser one, for the obvious reason: more candidates are deferred, and the ones that fill their slots scored lower. Two properties are worth knowing: - **Deferral is not loss.** A deferred candidate keeps its score and usually lands a few slots later, so the cost is displacement rather than removal. - **Starvation is real at the tail.** An outlet that dominates the shortlist has many candidates permanently deferred, and if the window is tight enough they never reach a slot within the pages the reader scrolls. ## Failure modes to name in the interview - **A stale or reused cursor.** A reader who reloads with an old cursor gets a look-back that no longer matches what is on their screen, and the guarantee quietly weakens. - **A client that re-sorts.** If the surface reorders the returned items, the spacing the server computed is gone; the window is only a guarantee on the order actually rendered. - **Infinite scroll re-requests.** Prefetching the next page and then discarding it consumes window state for slots that were never shown. - **Interaction with de-duplication.** Both mechanisms defer candidates, so a tight window on top of aggressive duplicate collapsing can empty the pool faster than the over-fetch budget allows for. - **Counting the wrong entity.** Capping by outlet does not cap by owner: several outlets under one owner satisfy an outlet cap and still read as one voice dominating the column.

  • With a cap of three per page, how many consecutive slots can one outlet hold?
    Six - the last three slots of one page and the first three of the next. The general form is twice the cap at any page boundary, which is why the number surprises people: a cap that sounds modest per page describes a much larger run in the column the reader actually scrolls.
  • When is a session-level counter the right window instead of a cursor-carried one?
    When the constraint is about the visit rather than the column - a daily exposure limit for one outlet, or a commercial commitment counted per session. That state has to outlive a single scroll and survive a reload, which a cursor cannot promise, so it goes in a low-latency key-value store keyed by session at the cost of a read and a write per request.

saying these in an interview costs you the question

  • Insists the cap was violated when every page obeyed it
  • Assumes the serving path remembers the previous page by default
  • Puts the look-back state on the client without integrity protection
  • Thinks a deferred candidate was dropped from the results
  • Caps by outlet and assumes that also caps by owner