Challenge - 5 Problems
Median Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
What is the median after inserting these numbers?
Consider a data stream where numbers are inserted one by one. Using two heaps (a max-heap for the lower half and a min-heap for the upper half), what is the median after inserting the sequence: 5, 15, 1, 3?
DSA Rust
use std::collections::BinaryHeap;
fn main() {
let mut max_heap = BinaryHeap::new(); // lower half
let mut min_heap = BinaryHeap::new(); // upper half (store negative values to simulate min-heap)
let nums = vec![5, 15, 1, 3];
for &num in &nums {
if max_heap.peek().map_or(true, |&x| num <= x) {
max_heap.push(num);
} else {
min_heap.push(-num);
}
// Balance heaps
if max_heap.len() > min_heap.len() + 1 {
if let Some(top) = max_heap.pop() {
min_heap.push(-top);
}
} else if min_heap.len() > max_heap.len() {
if let Some(top) = min_heap.pop() {
max_heap.push(-top);
}
}
}
// Calculate median
let median = if max_heap.len() == min_heap.len() {
(*max_heap.peek().unwrap() + (-*min_heap.peek().unwrap())) as f64 / 2.0
} else {
*max_heap.peek().unwrap() as f64
};
println!("Median: {:.1}", median);
}Attempts:
2 left
💡 Hint
Balance the heaps after each insertion and then find the middle value(s).
✗ Incorrect
After inserting 5, 15, 1, 3, the two heaps balance to lower half: [3,1], upper half: [5,15]. The median is the average of 3 and 5, which is 4.0.
🧠 Conceptual
intermediate1:30remaining
Why use two heaps to find the median in a data stream?
Which of the following best explains why two heaps (a max-heap and a min-heap) are used to find the median efficiently in a data stream?
Attempts:
2 left
💡 Hint
Think about how median relates to the middle values of sorted data.
✗ Incorrect
Using two heaps splits the data into lower and upper halves. The max-heap stores the smaller half, the min-heap stores the larger half. Balancing them keeps the median at the top of one or average of tops, allowing O(1) median retrieval.
🔧 Debug
advanced2:00remaining
Identify the bug in this median finder implementation
What error will this Rust code cause when inserting numbers into the two heaps for median calculation?
DSA Rust
use std::collections::BinaryHeap;
fn main() {
let mut max_heap = BinaryHeap::new();
let mut min_heap = BinaryHeap::new();
let nums = vec![10, 20, 30];
for &num in &nums {
if max_heap.peek().unwrap() >= &num {
max_heap.push(num);
} else {
min_heap.push(-num);
}
if max_heap.len() > min_heap.len() + 1 {
if let Some(top) = max_heap.pop() {
min_heap.push(-top);
}
} else if min_heap.len() > max_heap.len() {
if let Some(top) = min_heap.pop() {
max_heap.push(-top);
}
}
}
println!("Median: {}", max_heap.peek().unwrap());
}Attempts:
2 left
💡 Hint
Check what happens when max_heap.peek() is called before any element is inserted.
✗ Incorrect
The code calls max_heap.peek().unwrap() without checking if max_heap is empty. On the first iteration, max_heap is empty, so unwrap panics causing runtime error.
📝 Syntax
advanced1:30remaining
Which option fixes the syntax error in this Rust median finder snippet?
Fix the syntax error in this Rust code snippet for inserting into heaps:
DSA Rust
if max_heap.peek().map_or(true, |&x| num <= x) { max_heap.push(num) } else { min_heap.push(-num) }
Attempts:
2 left
💡 Hint
Rust statements need semicolons unless they are the last expression.
✗ Incorrect
The push method calls are missing semicolons, causing syntax errors. Adding semicolons fixes the syntax.
🚀 Application
expert2:30remaining
How many elements are in each heap after inserting this sequence?
Using two heaps to find median, after inserting the numbers [8, 12, 10, 5, 7, 6], how many elements are in the max-heap and min-heap respectively?
Attempts:
2 left
💡 Hint
Balance heaps so max-heap can have at most one more element than min-heap.
✗ Incorrect
After inserting all numbers and balancing, max-heap contains [8,7,6,5] and min-heap contains [10,12]. So max-heap has 4 elements, min-heap has 2.