A user's last 100 actions are kept in a two-ended sequence under one key — what bounds it, and what does reading the middle cost?
answer
- ends flat, interior scales with distance
- insertion order, no caller-supplied position
- no member ages out by itself
- every append owes a trim
- loss is the whole entry, not a truncation
basics
~10 sNothing bounds it but the writer: a lifetime attaches to the entry, not to a member, so each append must also trim the far end. The ends are constant-time; positional work scales with distance.
solid answer
~40 sA two-ended sequence is insertion-ordered and addressable at its ends, so appending the newest action at one end and removing the oldest from the other are both constant-time and independent of length. The bound is entirely the writer's responsibility — members inside one entry cannot carry individual deadlines, so the 100-item cap only exists if every append also trims, or a periodic pass does. Positional work is the opposite story: reaching an element by position means walking to it, so a slice near an end is cheap and one in the middle scales with the distance, and how steeply depends on the representation the store uses for that entry. A whole-sequence read is a single reply as large as the sequence, which is the thing that goes wrong when the trim was forgotten.
go deeper
Recall that the order is insertion order and that both ends are cheap: appending the newest element and dropping the oldest do not get slower as the sequence grows.
Explain the interior penalty — position is reached by counting — and that the length cap is enforced by the writer, because the store expires entries, not the elements inside one.
Own the consequence of a missing trim: unbounded growth, a whole-sequence read that becomes one very large reply, and one entry that turns into a unit of work every other caller waits behind.
Set the rule that every collection declares a bound and names who enforces it, and decide whether recent-history state belongs on a tier where loss removes the entry whole.
## The shape and its cost model A **two-ended sequence** is one entry whose value is an ordered run of elements, where the order is insertion order — the caller does not supply a number that positions each element, it simply appends to one end or the other. Two properties define it: - **The ends are addressable and cheap.** Adding or removing at either end is constant work, whether the sequence holds ten elements or ten thousand. - **The interior is reached by counting.** There is no key to an element; there is a position. Getting or removing an element inside the run means walking to it, so the cost scales with the distance from an end rather than being flat. How steep that is depends on how the store represents the entry — some representations make short sequences cheap at any position — but the shape of the cost model is the same across the class: ends flat, interior scaling. Two consequences follow immediately: - the newest or oldest handful is always cheap to read, however long the run has become; - reaching an element by identity means walking to it, because there is no key inside the entry to address it by. That asymmetry is the whole design guidance. A sequence is the right shape when the access pattern is at the ends: the newest handful, the oldest handful, append and drop. It is the wrong shape when the access pattern is by identity — "remove the action with this id" means finding it first. ## What bounds it: nobody, unless you do This is where the shape bites, and it is the part candidates miss. A lifetime attaches to **the entry**. The whole sequence can be given a deadline; an element inside it cannot. There is no mechanism by which the hundred-and-first action pushes the first one out, and no mechanism by which an element ages out after an hour while its neighbours remain. So the cap is a discipline, and there are only a few ways to hold it: 1. **Trim on write.** Every append is followed by a trim that keeps the sequence to its declared length. The two steps racing each other is an atomicity question and belongs to that subject; the modelling point here is that the trim exists at all and that it is the writer's job. 2. **Trim on read.** Cheaper on the write path, but the bound is then only as good as the read rate — a user who stops reading has a sequence that stops being trimmed. 3. **A sweeping pass.** A background job that walks the keys and trims. This buys a bound at the price of a second moving part, and it is the option that fails quietly when the job stops. 4. **A lifetime on the whole entry.** This bounds age, not *length*. It is a genuine complement to trimming, not a substitute — the entry vanishing whole is very different from its oldest elements falling off. When none of these is in place, the failure is not subtle: the sequence grows without limit, the whole-sequence read becomes a single very large reply, and one entry becomes a unit of work every other caller is queued behind. Sizing a single entry and diagnosing the resulting stall belong to the keyspace and access subjects; what belongs here is that the layout choice created the exposure. ## Reading it | read pattern | cost | comment | |---|---|---| | the newest element | constant | the reason to use this shape | | the newest twenty | proportional to twenty | a slice anchored at an end | | an element at position 4,000 | proportional to the distance | the interior penalty | | the whole sequence | proportional to length, one reply | fine at 100, dangerous unbounded | | "does it contain this id" | proportional to length | the wrong shape for this question | The last row is the honest limitation. A sequence answers position questions. If the dominant question is membership, the shape that answers it without a walk is an unordered collection of distinct members — and if both questions matter, the usual design holds both and keeps them consistent on the write path, which is a real cost to state rather than hide. ## The premise that does not change The sequence lives on a volatile tier, so the honest description of the hundred actions is the last hundred, when they are there at all. On eviction or a restart the entry goes whole: not a truncated list, an absent one. A recent-actions view degrades acceptably under that — it shows nothing and refills. Anything that would be wrong rather than *empty* if the run disappeared has no business being held only here. One boundary worth naming: waiting on a sequence for an element to arrive, and running work items through one so they survive a restart or are redelivered to a coordinated set of readers, are different subjects with different owners. The shape here is a bounded recent-history record, not a job pipeline.
- Why can you not simply give each of the hundred actions its own deadline?A lifetime is attached to the entry, and the sequence is one entry. Elements inside a multi-element value have no independent existence for the store to expire. To get per-element deadlines the elements have to become separate entries, which costs a full per-entry overhead each and turns the recent-history read into a multi-key operation.
- The product now wants "remove the action with this id" as a common operation. Is the sequence still right?Probably not on its own. Removal by identity means locating the element first, which is interior work proportional to how far in it sits, on every call. If that operation is frequent, either hold the identifiers in an unordered collection that answers membership directly and keep the two consistent on write, or reconsider whether a sequence is the shape at all.
- What happens if the trim is skipped for a month on an active user?The sequence keeps every append, so one entry grows without limit. The whole-sequence read turns into one very large reply, the entry becomes a single large unit of work other callers wait behind, and it consumes memory the tier eventually has to reclaim from somewhere. The bound was never enforced by the store; it was only ever the writer's.
saying these in an interview costs you the question
- Assumes the sequence drops its oldest element automatically at the cap
- Believes each element can be given its own time-to-live
- Treats reaching a middle position as being as cheap as an end
- Uses the sequence to answer membership questions by identity
- Says a lifetime on the entry is the same thing as trimming by length
- Expects loss to truncate the sequence rather than remove it whole