High Queue Question 156 of 224

How do you find the median of every sliding window of size k?

DSA interview set · Speak this in 60–90 seconds · Faridabad & Delhi NCR

PICTURE THIS: 1, 2, 2, 8

Mean3.25average

Median2middle

Mode2most often

Simple meaning

Two heaps (max-low, min-high) plus delayed deletions via a frequency map, or a policy-balanced multiset.

WHY — Queue instead of guessing?

Why interviewers care about Queue:

This is a process

question about Queue.

Panels listen for order,

trade-offs, and what you would actually do on a DSA project - not buzzwords.

Stay structured

Name the idea, why it exists, then one short example.

Close cleanly

End with when you use it and one common pitfall.

STEPS — What happens step by step?

Before you speak the answer, walk the interviewer through these steps:

1
Two heaps (max-low, min-high)
plus delayed deletions via a frequency map, or a policy-balanced multiset.
2
Each insert/delete is O(log
k), so O(n log k) time and O(k) space.
3
A sorted list per
window is O(n k) and too slow for large k.
4
Give an example
One tiny concrete case you can say aloud.
5
Common mistake
What juniors usually get wrong.
6
Close
When you pick this over the alternative.

EXAMPLE — See it in action

Here's a short line you can speak, broken into clear beats:

Say this line

“Each insert/delete is O(log k), so O(n log k) time and O(k) space.”

Break into beats

EachinsertdeleteisOlog

Speaking order

2987408337471632900

Note: Adapt this scaffold to your own project — keep it under 60–90 seconds.

Key takeaway

Two heaps (max-low, min-high) plus delayed deletions via a frequency map, or a policy-balanced multiset. Each insert/delete is O(log k), so O(n log k) time and O(k) space.