Data Processing Algorithms Interview Questions for Data Engineers

01

The 5 kinds of Data Processing Algorithms question

Cut by what a question asks you to DO, not by the topic it names. The same topic scores differently when you have to explain it, build it, or work out why it broke — and those three fail separately.

• 20Mechanics & InternalsHow the machinery works when nobody is looking. What a hash aggregation does when it runs out of memory, what a Bloom filter can and cannot tell you, and why a columnar engine reads a predicate before it reads a column.External merge sort & spilling · Hash vs sort aggregation · Bloom filters · Columnar & vectorized execution→
• 20Bottleneck DiagnosisA system that is slow, stuck or wrong, described by its symptoms. Name the mechanism before proposing a fix: head-of-line blocking, a skewed partition, a watermark that cannot advance, a join that spilled.Head-of-line blocking · Work partitioning & skew · Watermarking & progress tracking (scalar vs ledger) · External merge sort & spilling→
• 23Algorithm DesignDesign the procedure, not the snippet. Deduplicate more rows than fit in memory, backfill two years without saturating the warehouse, or replace a scalar watermark that one missing date can block forever.Dedup at scale · Backfill & reprocessing · Watermarking & progress tracking (scalar vs ledger) · Incremental computation & delta detection→
• 20ImplementationNow write it, in bounded memory, with a defined behaviour when it is interrupted halfway. Checkpointing, resumability and idempotence are the parts that separate a working prototype from something that can run nightly.Checkpointing & resumability · Idempotency & exactly-once · Merge/upsert (copy-on-write vs merge-on-read) · Retry, backoff & circuit breaking→
• 22Complexity & Trade-off AnalysisWhat does it cost, and what does it give up. Exact counts against a sketch that is one percent wrong for a thousandth of the memory, a full scan against an index that has to be maintained, accuracy against recovery time.HyperLogLog · Count-Min Sketch · Cardinality estimation · Reservoir sampling→

02

The ones that keep coming up

Answered here, in short. The full reasoning, the wrong answer and the follow-up are one click away.

1. 01Values arrive one at a time and after each one you must report the 3rd largest seen so far. You cannot keep them all. What do you use?A min-heap of size k. The root is the kth largest, and each arrival is either discarded in O(1) or swapped in for O(log k) — constant memory regardless of how many values arrive.→
2. 02For every window of 5 consecutive readings, report the maximum. Doing it naively is O(n·k) — how do you get it to O(n)?A monotonic deque holding indices whose values are in decreasing order. The front is always the window maximum; each index is pushed once and popped once, so the whole pass is O(n).→
3. 03You are asked to find duplicate payments in a transaction list. Before writing any code — what makes two payments duplicates of each other?Only an identifier the producer assigned can say two records are the same payment. Matching on amount, merchant and timestamp finds records that look alike, which is a different and much weaker claim.→
4. 04Implement a rate limiter allowing 100 requests per minute per key. Compare the fixed window, the sliding window log and the sliding window counter.Fixed window is O(1) memory and allows a 2× burst at the boundary. Sliding window log is exact and costs memory proportional to the requests in the window. Sliding window counter approximates the log in O(1) and is what most production limiters use.→
5. 05You already use HyperLogLog for all-time distinct users. Now you need distinct users in the last 30 days, rolling daily. Why can you not just subtract?HLL sketches union but cannot be subtracted, because a register records a maximum and removing an element cannot restore what it was before. Keep per-day sketches and merge the 30 you need at query time.→

03

What Data Processing Algorithms interviews actually cover

• 01Watermarking & progress tracking (scalar vs ledger)
• 02Head-of-line blocking
• 03Out-of-order & late arrival
• 04Idempotency & exactly-once
• 05Checkpointing & resumability
• 06Backfill & reprocessing
• 07Incremental computation & delta detection
• 08CDC diffing
• 09Merge/upsert (copy-on-write vs merge-on-read)
• 10Dedup at scale
• 11Work partitioning & skew
• 12Retry, backoff & circuit breaking
• 13Topological dependency resolution
• 14Reconciliation & self-healing
• 15Join algorithms
• 16External merge sort & spilling
• 17Hash vs sort aggregation
• 18Bloom filters
• 19HyperLogLog
• 20Count-Min Sketch
• 21Reservoir sampling
• 22Top-k / heavy hitters
• 23Compression & encoding
• 24Columnar & vectorized execution
• 25Predicate pushdown
• 26Cardinality estimation
• 27Streaming windows & watermark semantics

04

Learn it, then practise it