Data Processing Algorithms Algorithm Design

The reasoning

The insight is that deduplication is only ever *within* a key. If you partition by a hash of the key, two rows with the same key are guaranteed to land in the same partition, so no cross-partition comparison is ever needed. Each partition can then be handled entirely independently — in memory, in parallel, on different machines, in any order.

Choose the partition count so the largest partition's distinct keys fit comfortably in the memory you have, with headroom for skew. If a partition turns out to be too big, recurse: partition it again with a different hash seed. That recursion is exactly what a database's hash join does when a partition does not fit, and saying so shows the pattern is understood rather than memorised.

The measured pair beside this shows the effect: the naive set holds all 198,654 distinct keys; the partitioned version's peak set is 12,600 — bounded by the partition count you chose rather than by the data.

Two design questions the interviewer will follow with. Which row do you keep when there are duplicates? 'Any' is rarely the requirement — usually it is the latest by an event timestamp, and that needs a deterministic tie-break or your output changes between runs. And is exact deduplication even required? If the requirement is 'no duplicates within 24 hours', a bounded window is far cheaper than global exactness; if approximate is acceptable, a Bloom filter gives you bounded memory at the cost of dropping a small fraction of legitimate rows — which is usually unacceptable, and worth saying explicitly rather than leaving implied.

The reasoning

A single high-water mark encodes one assumption: that work completes in order. The moment it does not, the scalar has to choose between two bad options. Advance past the missing day and it is permanently skipped — silently, because nothing records that it was owed. Refuse to advance and every subsequent day is blocked behind it, which is head-of-line blocking applied to a pipeline.

A ledger separates 'how far have we got' from 'what is done'. One row per unit of work — usually per date or per partition — with a state: pending, running, succeeded, failed. Progress is then a set rather than a number, gaps are representable, and out-of-order completion is ordinary rather than exceptional.

What that buys, concretely. The late day is a pending row that gets picked up when its data arrives, with no special case. 'What is missing' is a query rather than an investigation. Reprocessing is setting rows back to pending, which makes backfill the same mechanism as normal operation rather than a separate script. And it makes the pipeline self-describing: anyone can see what has been done without reading logs.

The costs, to be fair to the scalar. A ledger is state you must maintain, and it can itself be wrong — a row marked succeeded whose output was never written is worse than no ledger, so the state transition and the output must be committed together. It needs a bounded retention policy or it grows forever. And for a pipeline that genuinely is strictly ordered and never has gaps, it is overhead. The rule I would give: the moment lateness or partial failure is possible, the scalar is a bug waiting for a date.

The reasoning

Before anything, establish that reprocessing one past date is safe: run it, diff the output against what is already there, and confirm the target ends identical rather than doubled. Seven hundred runs of a non-idempotent write is not a backfill, it is an incident, and this check costs ten minutes.

Then bound the resources. The backfill must not compete with production for the same pool — a separate pool, or a hard concurrency cap, so the worst case is that the backfill is slow rather than that the nightly run misses its deadline. This has to be enforced by the scheduler rather than agreed by convention.

Then chunk and checkpoint. Process a month at a time, record each chunk's completion in the ledger, and make the whole thing resumable from where it stopped. That gives you three things: the ability to pause when production needs capacity, verification points before continuing, and a failure that costs a month rather than two years.

Then order it by value. Run the most recent months first — they are what people actually query — so the backfill delivers usable results early and can be abandoned partway with most of the benefit realised. Backfilling chronologically from two years ago means the useful part arrives last.

Then reconcile as you go: per-chunk row counts and a checksum against the source, checked at each checkpoint rather than at the end. A backfill that ran to completion and produced wrong output is worse than one that stopped early, and you only find out which you have if you check while it is running. And the alternative worth considering before starting: if the work is warehouse-shaped, one statement over the whole range may beat seven hundred orchestrated runs entirely.

The reasoning

The procedure: for each row compute a fingerprint — a hash over the business columns, excluding anything volatile — and store `(key, fingerprint)` for the whole table. Today, compute the same and full-outer-join against yesterday's. Present today only means an insert; present yesterday only means a delete; present in both with different fingerprints means an update; identical fingerprints are unchanged and are the vast majority.

This is the only reliable way to detect deletes without CDC, which is the part people miss. A timestamp-based incremental pull cannot see a deleted row at all, because there is nothing left to have a timestamp — that is why 'incremental by updated_at' pipelines quietly accumulate rows that no longer exist upstream.

The cost is honest: you read the full source every day, so this is not cheap. What it saves is downstream — instead of rewriting forty million rows into the warehouse, you write the few thousand that changed, which is where the expense actually is. The fingerprint map is small: a key and a hash per row, tens of megabytes at this scale, not the full table.

The details that matter. Choose the hashed columns deliberately, and exclude anything that changes without meaning — a `last_synced_at` from the vendor will make every row look updated. Normalise before hashing, since whitespace and casing differences produce false updates. Store the fingerprint table partitioned by key range so the join is efficient. And keep the previous snapshot until the new one is verified, so a bad run can be rolled back rather than leaving you with no baseline.

The reasoning

The naive approach — collect all counts and sort — moves and orders every distinct term. The right shape has three stages. Locally: count occurrences on each node, which is a hash aggregation bounded by distinct terms on that node. Still locally: keep only the top hundred by count, using a min-heap of size a hundred, so anything smaller than the heap's root is discarded immediately. Then ship each node's hundred to a coordinator and merge.

The heap is what makes the local stage cheap: it holds exactly k entries and each candidate costs one comparison against the root and at most a log-k reinsertion, against the `n log n` of sorting everything. The measured snippet in the Implementation category shows the heap result matching a full sort exactly, and holding ten entries instead of ordering fifty thousand.

The correctness caveat that must be volunteered: taking the top hundred per node and merging is *not* guaranteed exact. A term ranked 101st on every node, and therefore discarded everywhere, could have a global total exceeding a term that was first on one node. The standard mitigation is to keep more than you need per node — the top few thousand rather than the top hundred — which makes the error vanishingly unlikely without making it impossible.

If exactness is genuinely required, the local top-k has to be replaced by a full shuffle by term so all occurrences of a term meet, and then the top-k is computed on true global counts. That is the expensive-and-correct version. If approximation is acceptable and memory is the binding constraint, Count-Min Sketch or Space-Saving gives bounded memory with bounded error — and knowing which of the three the requirement calls for is the actual answer.

The reasoning

Split the problem: top-k needs counts, and counts need memory proportional to distinct keys. If distinct keys fit — fifty thousand pages is nothing — then count exactly in a hash map and maintain a heap of k, which is exact and cheap. That is the case in most real systems, and it is worth checking before reaching for a sketch.

If distinct keys do not fit — hundreds of millions of URLs — then exact counting is impossible in one pass and bounded memory, and you choose an approximation. Count-Min Sketch gives per-key counts in fixed memory that never underestimate; Space-Saving maintains a fixed-size set of candidate heavy hitters with error bounds and is designed specifically for this question.

The property that makes both acceptable *for this problem* is that heavy hitters are exactly the keys they estimate well. The measured Count-Min table shows the top key estimated at 200,337 against a true 200,000 — a 0.2% error — while a tail key with a true count of 10 is estimated at 165. The absolute error is roughly constant, so it is negligible for the head and enormous for the tail. Since top-k only cares about the head, that is a trade that costs nothing where it matters.

The design details to name: a heap gives you the top k but not their exact counts if the counts came from a sketch, so a second pass or a separate exact counter for the surviving candidates is a common refinement. Distributed, the same top-k-per-node-then-merge caveat applies. And a decaying variant — periodically halving all counts — is what turns 'top pages ever' into 'top pages recently', which is usually the actual requirement.

The reasoning

Start with why it is not a delivery setting. Between 'write the data' and 'commit the offset' there is always a window; a crash inside it means the message is redelivered. No amount of acknowledgement protocol removes that window, because two systems cannot atomically agree without a shared transaction. So exactly-once *effect* is the achievable goal, not exactly-once *delivery*.

**Shape one: transactional.** Write the data and the consumer offset in the same transaction, to the same store. A crash rolls both back or commits both, so the redelivered message finds the offset already advanced. This is clean and it requires the offset to live where the data lives — which is exactly what the checkpoint example does with a single atomic file replace, and what Kafka's transactional producer does across topic and offset.

**Shape two: idempotent.** Make the write itself insensitive to repetition — a MERGE on a natural key, a delete-then-insert of the message's partition, or a primary key that rejects the duplicate. Then at-least-once delivery is harmless: the second application is a no-op. This is more robust in practice because it survives redelivery from *any* cause, including a human replaying a topic, not just a crash in the window.

The choice between them: transactional is exact and constrains where your state lives; idempotent is more general and requires a natural key and a write pattern that can express replacement. My default is idempotent, because it degrades gracefully — and I would say explicitly that a deduplication table keyed by message id is the fallback when the data has no natural key, with the same bounded-retention caveat as any dedup set.

The reasoning

Kahn's algorithm gives both the order and the parallelism for free. Compute each node's in-degree. Take the whole set of zero in-degree nodes as one *level* — every node in it can run concurrently. Remove them, decrement their children's in-degrees, and repeat. The result is a sequence of levels, and its length is the critical path.

Cycle detection falls out: if at some point no node has in-degree zero and nodes remain, the remainder contains a cycle. Those exact nodes are the diagnostic — reporting 'a cycle exists' is much less useful than reporting which four datasets are in it, and the leftover set is that list.

The refinement that matters in practice is that level-by-level is not optimal. Waiting for an entire level to finish before starting the next means the slowest node in each level gates everything, which is a barrier where none was required. A better scheduler is event-driven: when a node completes, decrement its children and start any that reach zero. Same order guarantees, no artificial synchronisation — which is the difference between a stage-based runner and a genuine dependency scheduler.

Then the operational parts. Failure handling: a failed node means its entire descendant subtree cannot run, and marking them skipped rather than failed keeps the diagnosis clean. Priority within an available set, so the critical path goes first. And resource limits, since 'as much parallelism as possible' is bounded by pools rather than by the graph. The graph tells you what *may* run; the scheduler decides what *does*.

The reasoning

The detector has to be cheaper than the pipeline or nobody will run it often. Per-partition summaries do that: for each day or key range, count rows and compute an order-independent aggregate over the business columns — a sum of per-row hashes works, because it is commutative and so does not depend on ordering or parallelism. Compare source against target. That is a small aggregate on each side rather than a row-by-row diff.

The repair should be the ordinary pipeline, aimed at the disagreeing partition. This is why idempotence is the precondition for self-healing: if reprocessing a partition is safe, repair is just 'run it again for this date', and the same code path is used for the normal case and the recovery. If it is not safe, every repair is a bespoke operation and nothing can be automatic.

The safety rails matter more here than usual, because this thing acts on its own. Bound how much it may repair per run, so a source-side outage that makes everything disagree cannot trigger a full reprocess of two years. Alert when the repair rate exceeds a threshold, because frequent healing means a systemic problem rather than a transient one — a self-healing pipeline that quietly repairs the same partition every night has hidden a bug rather than fixed it. And log every repair, so the history is visible.

The design point to state: reconciliation is not a replacement for correctness, it is a detector for the errors your design cannot prevent — late data outside the window, a missed CDC event, a partial write. Those categories are unavoidable rather than sloppy, which is why the mature answer is to expect them and check, rather than to claim they cannot happen.

The reasoning

The mistake is trying to serve both requirements with one mechanism. Sizing the allowed lateness for the worst case means every window in the job retains state for a week — state cost multiplied by ten thousand to accommodate a thousandth of the events, paid continuously. Sizing it for the common case means the 0.1% is silently dropped, which is a correctness bug nobody can see.

So separate them. The streaming path keeps a short allowed lateness — a few minutes — and emits fast, approximate-but-almost-always-right results. Events beyond that are not dropped but written to a late-arrivals table with their event time. A batch job then periodically recomputes the affected windows from the complete record and updates the served values.

That makes the trade explicit and controllable: latency for the common case, correctness eventually for everything, and a cost that scales with the number of late events rather than with the total number of windows. It is the lambda-architecture idea applied narrowly, without duplicating the whole pipeline.

The parts to specify. The serving layer must accept corrections — a value that can be updated, not an append-only log that would double-count. Consumers need to know a number can change, and by how much and for how long, which is a contract rather than an implementation detail. And the late-arrivals table needs monitoring in its own right: a sudden rise in late events is a signal about a client or a network, and it is invisible if late data is dropped.

The reasoning

The core is a partition-and-sort followed by a linear sweep. Partition by user id so all of a user's events are together, sort by event time within the user, then walk forward assigning a session id that increments whenever `event_time - previous_event_time > 30 minutes`. In SQL this is a window function: a lag, a comparison, and a running sum of the boundary flag.

Cost is dominated by the sort, and it inherits everything from the window-function discussion — it is a shuffle plus a per-partition sort, and it is skew-sensitive because one very active user's entire history must be ordered on one node.

The boundary problem is where it gets interesting. Processing a day at a time, a session that starts at 23:50 and continues to 00:20 is split into two by the batch boundary, so you report two sessions where there was one. The fix is to overlap: read the previous batch's trailing thirty minutes, sessionise the union, and emit only sessions whose *start* falls in the current batch. Overlap plus a rule for which batch owns each result — that pattern generalises to any windowed computation processed in chunks.

In streaming the equivalent is a session window with a gap duration, and the framework handles the merging — including the case where a late event bridges two previously-separate sessions and they must be combined, which is the reason session windows are the most state-hungry kind. And the requirement worth clarifying before implementing: is the timeout inactivity-based, or is there also a maximum session length? Without a cap, one automated client with an event every twenty-nine minutes produces a single session lasting months.

The reasoning

Initialise the heap with one element from each of the k streams, tagged with which stream it came from. Repeatedly pop the minimum, emit it, and pull the next element from that same stream, pushing it onto the heap. When a stream is exhausted it simply stops contributing. The output is fully sorted and memory is proportional to k, not to n.

The cost is `n log k` comparisons — each of the n elements enters and leaves the heap once, at `log k` each. The alternative of concatenating and sorting is `n log n`, which is worse whenever k is much smaller than n, and it also requires holding everything. Doing it pairwise instead — merge two, then merge the result with the third — is `n·k` in the worst case, which is why the heap matters.

The practical constraint is buffering rather than the heap. Reading one element at a time from two hundred files means two hundred interleaved random reads, which destroys sequential throughput. Real implementations buffer a block per stream, so memory is `k × buffer_size` — and that product is what actually bounds the fan-in, which is why an external sort's fan-in is a hundred rather than a million.

Where this shows up: the merge phase of external sort, sort-merge join, compaction in an LSM tree or a table format, and merging pre-sorted partial results from a distributed job. The variant worth knowing is merging with deduplication — when two streams carry the same key, keep the one from the newer file, which is exactly how a compaction applies updates and deletes while merging.

The reasoning

The decomposition that makes this possible: the aggregate is partitioned by day, and each day's result depends only on that day's facts. So a change to one day invalidates one output partition, and recomputing it is cheap. That property — that the output partitions map cleanly onto input partitions — is what you are checking for before proposing anything.

Replace, do not adjust. Recomputing the affected day from its facts and overwriting the output partition is idempotent and self-correcting. Applying a delta — adding the new rows' revenue to the existing total — is faster and accumulates error: a correction, a duplicate delivery or a retry each shift the total permanently, and nothing detects it. Deltas are only safe when the operation is genuinely invertible and delivery is exactly-once, which is rarely both.

Then you need to know which days are dirty. If facts carry the day they belong to, the set of days touched by an ingest batch is a by-product of the ingest — record it. Corrections to old data mark old days dirty, which is exactly the case a `WHERE day = today` incremental would miss.

Then the safety net: periodically recompute everything and compare, or reconcile per-partition totals against the source. Incremental computation is an optimisation over a full recompute, and it needs the full recompute as its check — weekly is usually enough. And the aggregate has to be decomposable for any of this to work: sums and counts are, and a distinct count or a median is not, which is where a mergeable sketch earns its place.

The reasoning

The procedure per day: full-outer-join today's snapshot against the currently-open history rows on the business key. Four outcomes. In both and the tracked columns match — do nothing. In both and they differ — set the open row's valid_to to today and insert a new open row with today's values. Only in the snapshot — insert an open row. Only in the history — the key has disappeared upstream, so close the open row.

The fingerprint is what makes 'differ' cheap and precise: hash the tracked columns and compare hashes rather than comparing column by column. It also forces the decision about *which* columns constitute a change — a vendor's `last_exported_at` moving must not create a new version, and if you compare everything it will.

Idempotence is the property to design for, because this will be rerun. Running the same day twice must not create two versions, so the operation should be expressed as a merge keyed on `(business_key, valid_from)` rather than as blind inserts. That also makes a backfill of a missed day safe, provided the days are processed in order — and they must be, because each day's result depends on the previous state, which is the one genuine ordering dependency in the design.

The gaps to name honestly. Daily snapshots can only capture daily granularity: two changes on the same day appear as one, and a value that changes and reverts within a day is invisible. That is inherent to snapshot-based history, not a flaw in the algorithm, and the alternative is CDC. And the half-open interval convention — `valid_to` of one row equals `valid_from` of the next — has to be stated, because a temporal join written with `<=` on both ends double-counts events on the boundary.

The reasoning

Assigning a hundred files each ignores size, so a worker that draws the big ones takes far longer and the job waits for it. The measure that matters is bytes per worker, not files per worker.

The standard heuristic is longest-processing-time-first: sort the files by size descending, and give each in turn to whichever worker currently has the least assigned. Handling the big items first is what makes it work — the small ones at the end are what smooth out the remainder. It is a classic approximation with a known bound of about four-thirds of optimal, which is more than good enough and takes one sort.

The limit is that no assignment beats the largest single item. If one file is bigger than the ideal per-worker share, that worker's time is set by that file and the total cannot go below it. The fix is not a better assignment but a smaller unit of work: split the file, if the format allows it — which is why splittable formats and row groups matter, and why a single unsplittable gzip file is a scheduling problem as much as a compression one.

Two refinements for the real version. Size is a proxy for cost, and it is a bad proxy when files differ in compression or in how much work each row triggers — if you have a better predictor, use it. And static assignment is fragile when workers differ in speed; a work-stealing or pull-based queue, where each worker takes the next item when it becomes free, adapts automatically and is usually simpler than computing a perfect partition in advance.

The reasoning

Both sides must be retained, because either can arrive first. So state is every unmatched row from both streams within the retention interval — which is why the interval is the whole design. Without one, state grows forever and the job dies; that is the same unbounded-state failure in a new costume.

The interval has to come from the data. Measure the distribution of the delay between an order and its payment and pick a percentile you can defend — say the 99.9th at four hours. Then the join condition is both the key and the time bound, which is what a framework expresses as an interval join.

The decision people skip is what happens to the unmatched remainder. When an order's retention expires with no payment, is it dropped, emitted with nulls as an outer join, or routed somewhere for later reconciliation? All three are legitimate and they produce different numbers, so it is a business decision. Silently dropping is the default in many implementations and is almost never what anyone wanted.

The practical alternatives worth raising. If one side is small and slow-moving, it is not a stream-stream join at all — make it a lookup against a materialised table and the state problem disappears. And if the tolerance is genuinely hours, a micro-batch join over a windowed table is often simpler to operate and reason about than a stateful streaming join, at the cost of latency you may not need. Choosing the simpler mechanism when the latency requirement allows is a good instinct to demonstrate.

The reasoning

The dual-write problem: writing to A then B has three outcomes, and one of them is A succeeded and B did not. Retrying B may duplicate; skipping it leaves them inconsistent. There is no ordering of two independent writes that avoids this, which is why the answer is structural rather than a matter of care.

The outbox pattern is the standard resolution. In the same transaction as the data write, insert a row into an outbox table describing what should be published. That is one atomic write to one system. A separate relay then reads unpublished outbox rows, publishes them, and marks them done. If the relay crashes it republishes — so consumers need to be idempotent, which is at-least-once delivery with an idempotent consumer, the same conclusion as the exactly-once question.

Change data capture is the same idea with less code: publish the warehouse's own change log rather than maintaining an outbox, so the published stream is derived from the committed state by construction and cannot disagree with it.

What I would avoid: two-phase commit across a warehouse and a message broker, which most such pairs do not support and which introduces a coordinator that can block. And 'write to Kafka first, then consume it into the warehouse' is worth naming as the other legitimate shape — it makes the stream authoritative and the warehouse derived, which is a real architecture rather than a workaround, and the choice between them is which system you want to be the source of truth.

The reasoning

A random draw per event fails the requirement twice: the same user appears sometimes and not others, so per-user analysis is meaningless, and it is not reproducible between runs. Hashing the *key* rather than drawing per event fixes both — `hash(user_id) % 1000 < 10` keeps a stable, uniformly-chosen 1% of users and every event they ever produce.

The properties that follow are what make this the standard technique. No state, so it works in a stateless map with no coordination. Identical on every node and in every rerun, so distributed and batch and streaming agree. And it composes: a 0.1% sample is a subset of the 1% sample if you use the same hash, which lets you nest analyses.

The caveats. It is a sample of *users*, not of events, so a user with a million events contributes all of them — for event-level statistics that is a biased sample, and heavy users are over-represented within the chosen set. If you need an event-level sample, hash the event id instead, and accept losing per-user completeness. Which of the two you want depends on the question being asked, and getting it backwards makes the analysis wrong rather than noisy.

And where a genuine uniform sample of a stream of unknown length is required, reservoir sampling is the right tool — one pass, k items, every item equally likely regardless of when it arrived. It is the answer to a different question, and knowing which of the two the requirement calls for is the point.

The reasoning

Model each identifier as a vertex and each known-same pair as an edge. An identity cluster is a connected component, and the standard distributed algorithm is label propagation: initialise every vertex's label to its own id, then repeatedly set each vertex's label to the minimum among itself and its neighbours, until no label changes. Every vertex in a component converges to the same minimum id, which becomes the cluster key.

The cost is the number of iterations, which is bounded by the graph's diameter — so long chains are the slow case. Small-world graphs converge in a handful of rounds; a pathological chain of a million vertices takes a million. Large-star/small-star refinements reduce that to a logarithmic number of rounds and are what production implementations use.

The engineering realities. This is iterative, so each round is a full join and shuffle of the edge set — expensive, and worth caching the edges. Skew is severe and structural: one enormous component, typically created by a shared identifier like a household device or a test account, dominates a partition and one task runs forever. That is not incidental — bad edges create giant components, so data quality on the edge set matters more than the algorithm does.

Which leads to the guard I would build in first: cap component size and quarantine anything above it for inspection, rather than letting one bad edge merge two million people into a single identity. And note that this is monotonic — components only ever merge — so incremental maintenance means adding edges and merging the affected components, while *removing* an edge may split a component and cannot be done incrementally at all. That asymmetry decides whether you can maintain the result or must periodically rebuild it.

The reasoning

**Size and shape.** Total volume, and separately the cardinality of the key — those are different numbers and it is cardinality that decides whether a hash table fits. Then the distribution: is one key a third of the data, because that changes the design rather than the tuning.

**Budget.** Memory available per worker, and whether the answer is needed in seconds, minutes or by morning. A batch job with an eight-hour window and a streaming requirement of one second are different problems with the same description, and people often do not say which they have.

**Exactness.** Must the count be exact, or is 1% acceptable? This single question decides between a hash table and a sketch, and it is the one candidates most often assume rather than ask. Financial reconciliation and a real-time dashboard sit on opposite sides of it.

**Failure behaviour.** What must be true if this dies halfway — can it be rerun, must the partial output be invisible, is the input replayable? That determines whether you need checkpointing, idempotent writes, or both, and it is the difference between a prototype and something that runs nightly.

**Arrival.** Does the data arrive in order, on time, and exactly once? Late, out-of-order and duplicate arrivals each change the design, and assuming they do not happen is how the most expensive mistakes get made. Having established those five, the algorithm is usually determined — and the answer to give is the procedure plus the specific thing you would measure to know whether it is holding up.

The reasoning

**The inversion is the insight.** To track the largest values you keep a **min**-heap, not a max-heap. The heap holds the k largest seen so far, and its root is the *smallest* of those — which is exactly the kth largest overall, available in O(1).

**The algorithm.** Fill the heap with the first k values. For every value after that, compare it to the root: if it is smaller, discard it immediately — the common case, and it costs one comparison. If it is larger, pop the root and push the new value, O(log k). Memory is k entries forever, whether the stream has a thousand values or a trillion.

**Why the obvious alternatives fail.** Sorting needs all the values, which you do not have. A max-heap of everything is O(n) memory, which is the constraint you were given. Keeping a sorted list of k works and costs O(k) per insertion instead of O(log k) — fine for k = 3, wrong for k = 10,000.

**Edge cases the interviewer will ask about.** Fewer than k values seen so far — there is no kth largest, and returning the minimum instead of null is a silent bug. Duplicates — decide whether "3rd largest" means the 3rd distinct value or the 3rd position, because `[9, 9, 9, 5]` gives 9 or 5 depending on the answer, and both are defensible. Negative numbers change nothing, which is worth saying because it is the first thing many candidates check.

**Where this shows up in data engineering:** top-k per key over a stream, keeping the N most recent versions of a record, and any "worst offenders" monitor. It is the same structure as bounded top-k, and it is distinct from heavy-hitters — heavy-hitters has an unbounded *key* space and needs a sketch, where this has an unbounded *value* stream and a fixed k.

The reasoning

**Why naive is wasteful.** Recomputing `max()` over each window redoes work: consecutive windows overlap in k-1 elements, so almost every comparison has already been made. The fix is to carry state between windows instead of rebuilding it.

**The deque invariant.** Hold indices, and keep the values at those indices in strictly decreasing order. Two operations maintain it. On arrival, pop from the **back** every index whose value is less than or equal to the new one — they can never be the maximum again, because the new element is both larger and more recent, so it outlives them. Then push the new index. Separately, pop from the **front** any index that has fallen out of the window. The front is now the maximum of the current window, in O(1).

**Why it is O(n) despite the inner loop.** Each index is pushed exactly once and popped at most once across the entire run. The inner `while` can pop several elements on one step, but that cost was already paid for at push time — amortised O(1) per element, O(n) total. This is the argument to give, because the visible nested loop makes it look quadratic.

**Why "less than or equal" and not "less than".** With `<`, equal values accumulate in the deque and it grows; with `<=`, the older duplicate is discarded in favour of the newer one, which is correct because the newer one survives longer in the window. Getting this wrong does not break the answer, it breaks the memory bound.

**Where it matters here:** this is how a stream processor maintains a windowed max or min without buffering the window, and the same shape handles windowed minimum by reversing the comparison. When a job holding a windowed aggregate uses memory proportional to the window rather than to the number of distinct answers, this is usually what is missing.

The reasoning

**The trap is that identical-looking is not identical.** A customer buying the same coffee twice in the same minute produces two payments with the same amount, the same merchant, the same card and possibly the same timestamp to the second. They are two payments. Any dedup keyed on content deletes one of them, and the customer is charged once for two coffees — a silent, unrecoverable error in the direction that loses money for someone.

**So identity has to be asserted, not inferred.** The producer generates an idempotency key or transaction reference per payment attempt, and a retry of that attempt reuses it. That is the only thing that can distinguish "the same payment sent twice" from "two payments that look alike", because only the producer knows which it was.

**Two different problems get conflated here.** *Transport duplicates* — the same payment delivered twice by an at-least-once pipeline — are solved by the producer key, exactly. *Business duplicates* — a genuine double charge caused by a user double-clicking — are a fraud or UX problem, and the correct output is a flag for review, not a deletion. Content matching is a reasonable heuristic for the second and a bug for the first.

**When there is genuinely no key**, and sometimes there is not, be explicit about what you are building: a composite key from the fields that should be unique together, with the collision risk stated, and output routed to review rather than to automatic deletion. "We flag likely duplicates for a human" is a defensible answer; "we delete rows with matching hashes" is not.

**At scale**, the exact-set membership check on the key is the bounded-dedup problem — a bloom filter over a time window in front of an exact lookup, sized for the throughput and the acceptable false-positive rate. But that is the implementation, and it only becomes relevant once the key question is settled.