Machine Learning System Design Interview #6 - The Streaming Median Trap

Why exact statistics crash real-time fraud systems - and how sketching algorithms save you from OOM failure.

You’re in a Senior ML System interview at Google DeepMind.

The interviewer smiles and sets a trap:

“We need to detect fraud in real-time. Write a function to calculate the running Global Median of transaction values coming from the payment stream.”

90% of candidates walk right into the 𝐎𝐎𝐌 (𝐎𝐮𝐭 𝐨𝐟 𝐌𝐞𝐦𝐨𝐫𝐲) 𝐞𝐫𝐫𝐨𝐫.

The reflex is to think in Python scripts.

- “Easy. I’ll maintain a list of transaction values.”

- “On every new event, I’ll append to the list, sort it, and pick the middle index.”

- “Or I’ll just use numpy.median() on the buffer.”

The interviewer stops you. “The stream is unbounded. It never ends. You just tried to sort infinity.”

In Batch processing, median is a sorting problem. You have the full dataset in RAM.

In Stream processing, you never have the full dataset.

If you try to store every transaction to calculate an exact median, your memory footprint grows linearly O(N) until your container crashes. You aren’t building a fraud detector; you’re building a memory leak.

The Solution: 𝐔𝐧𝐛𝐨𝐮𝐧𝐝𝐞𝐝 𝐀𝐩𝐩𝐫𝐨𝐱𝐢𝐦𝐚𝐭𝐢𝐨𝐧 𝐏𝐚𝐭𝐭𝐞𝐫𝐧.