Median of Data Stream Using Two Heaps in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Median After Adding Numbers

What is the median after adding the numbers 5, 15, 1, 3 in order using two heaps?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

// IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
	heap.Fix(h, h.Len()-1)
}

func (h *IntHeap) Pop() interface{} {
	n := h.Len()
	x := (*h)[0]
	(*h)[0] = (*h)[n-1]
	*h = (*h)[:n-1]
	heap.Fix(h, 0)
	return x
}

// MaxHeap is a max-heap of ints (invert Less).
type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
	heap.Fix(h, h.Len()-1)
}

func (h *MaxHeap) Pop() interface{} {
	n := h.Len()
	x := (*h)[0]
	(*h)[0] = (*h)[n-1]
	*h = (*h)[:n-1]
	heap.Fix(h, 0)
	return x
}

func main() {
	low := &MaxHeap{}
	high := &IntHeap{}
	heap.Init(low)
	heap.Init(high)

	nums := []int{5, 15, 1, 3}
	for _, num := range nums {
		if low.Len() == 0 || num <= (*low)[0] {
			heap.Push(low, num)
		} else {
			heap.Push(high, num)
		}

		// Balance heaps
		if low.Len() > high.Len()+1 {
			val := heap.Pop(low).(int)
			heap.Push(high, val)
		} else if high.Len() > low.Len() {
			val := heap.Pop(high).(int)
			heap.Push(low, val)
		}

		// Calculate median
		var median float64
		if low.Len() == high.Len() {
			median = float64((*low)[0]+(*high)[0]) / 2.0
		} else {
			median = float64((*low)[0])
		}

		fmt.Printf("Median after adding %d: %.1f\n", num, median)
	}
}

A

Median after adding 5: 5.0
Median after adding 15: 15.0
Median after adding 1: 5.0
Median after adding 3: 3.0

B

Median after adding 5: 5.0
Median after adding 15: 15.0
Median after adding 1: 1.0
Median after adding 3: 4.0

C

Median after adding 5: 5.0
Median after adding 15: 10.0
Median after adding 1: 1.0
Median after adding 3: 3.0

D

Median after adding 5: 5.0
Median after adding 15: 10.0
Median after adding 1: 5.0
Median after adding 3: 4.0

💡 Hint

Balance the two heaps so their sizes differ by at most one. Median is top of max-heap or average of tops.

We add numbers one by one, pushing smaller half into max-heap and larger half into min-heap. Balancing ensures median is either top of max-heap or average of tops.

🧠 Conceptual

intermediate

Why Use Two Heaps for Median of Data Stream?

Why do we use two heaps (a max-heap and a min-heap) to find the median in a data stream?

A To keep the smaller half of numbers in max-heap and larger half in min-heap, so median is easily found at the top of heaps.

B To use heaps as queues for first-in-first-out order of numbers.

C To store all numbers in two heaps randomly for faster insertion.

D To sort all numbers in one heap and then pop the median directly.

💡 Hint

Think about how median splits data into two halves.

Two heaps split the data into smaller and larger halves. Max-heap stores smaller half so its top is the largest of smaller numbers. Min-heap stores larger half so its top is the smallest of larger numbers. Median is either top of max-heap or average of tops.

🔧 Debug

advanced

Identify the Bug in Median Calculation Code

What error will this code produce when calculating median after adding numbers using two heaps? Code snippet: if low.Len() == high.Len() { median = float64(((*low)[0] + (*high)[0]) / 2) } else { median = float64((*low)[0]) } Note: low is max-heap, high is min-heap.

A No error, code runs correctly and calculates median.

B Compilation error because integer division truncates before float conversion.

C Wrong median value because division by 2 should be 2.0 to get float.

D Runtime error due to accessing empty heap when one heap is empty.

💡 Hint

Check how division works between integers and floats in Go.

In Go, integer division truncates before converting to float64. Dividing by 2 (int) causes truncation. Dividing by 2.0 (float64) ensures correct float division.

❓ Predict Output

advanced

Output After Balancing Heaps

Given the sequence of numbers added: 10, 20, 30, 40, 50, what is the content of the max-heap (low) and min-heap (high) after all insertions and balancing?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
	heap.Fix(h, h.Len()-1)
}
func (h *IntHeap) Pop() interface{} {
	n := h.Len()
	x := (*h)[0]
	(*h)[0] = (*h)[n-1]
	*h = (*h)[:n-1]
	heap.Fix(h, 0)
	return x
}

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
	heap.Fix(h, h.Len()-1)
}
func (h *MaxHeap) Pop() interface{} {
	n := h.Len()
	x := (*h)[0]
	(*h)[0] = (*h)[n-1]
	*h = (*h)[:n-1]
	heap.Fix(h, 0)
	return x
}

func main() {
	low := &MaxHeap{}
	high := &IntHeap{}
	heap.Init(low)
	heap.Init(high)

	nums := []int{10, 20, 30, 40, 50}
	for _, num := range nums {
		if low.Len() == 0 || num <= (*low)[0] {
			heap.Push(low, num)
		} else {
			heap.Push(high, num)
		}

		if low.Len() > high.Len()+1 {
			val := heap.Pop(low).(int)
			heap.Push(high, val)
		} else if high.Len() > low.Len() {
			val := heap.Pop(high).(int)
			heap.Push(low, val)
		}
	}

	fmt.Printf("Max-heap (low): %v\n", *low)
	fmt.Printf("Min-heap (high): %v\n", *high)
}

A

Max-heap (low): [30, 10, 20]
Min-heap (high): [40, 50]

B

Max-heap (low): [20, 10]
Min-heap (high): [30, 40, 50]

C

Max-heap (low): [50, 40, 30]
Min-heap (high): [20, 10]

D

Max-heap (low): [10, 20, 30]
Min-heap (high): [40, 50]

💡 Hint

Remember max-heap stores smaller half, min-heap stores larger half, and heaps are balanced in size.

After inserting all numbers and balancing, max-heap contains the smaller half [30, 10, 20] (max-heap order), min-heap contains larger half [40, 50].

🚀 Application

expert

Calculate Median After Complex Stream

Given the stream of numbers: 2, 8, 3, 5, 10, 9, 4, 7, 6, what is the median after all numbers are added using two heaps?

A 5.5

B 6.0

C 7.0

D 5.0

💡 Hint

Balance heaps after each insertion and find median from tops.

After adding all numbers and balancing heaps, the median is the middle value 6.0 because the total count is odd (9).

Practice

1. What is the main purpose of using two heaps (a max-heap and a min-heap) in finding the median of a data stream?

easy

A. To store all numbers in a single data structure

B. To sort all numbers in ascending order

C. To efficiently keep track of the lower half and upper half of the numbers separately

D. To find the maximum number in the data stream

Solution

1. Step 1: Understand the role of two heaps

   The max-heap stores the smaller half of the numbers, and the min-heap stores the larger half.

2. Step 2: Explain how this helps find the median

   By balancing these heaps, the median is either the top of one heap or the average of the tops of both heaps.

3. Final Answer:

   To efficiently keep track of the lower half and upper half of the numbers separately -> Option C

4. Quick Check:

   Two heaps split data halves = A [OK]

Hint: Two heaps split data halves for median [OK]

Common Mistakes:

• Thinking heaps sort all numbers fully
• Using one heap only
• Confusing max-heap and min-heap roles

2. Which of the following Go code snippets correctly initializes a max-heap and a min-heap for integers using container/heap package?

easy

A. maxHeap := &IntMaxHeap{}; minHeap := &IntMinHeap{}

B. maxHeap := heap.New(IntMaxHeap{}); minHeap := heap.New(IntMinHeap{})

C. maxHeap := &IntMinHeap{}; minHeap := &IntMaxHeap{}

D. maxHeap := make([]int, 0); minHeap := make([]int, 0)

Solution

1. Step 1: Recognize heap initialization in Go

   Heaps are initialized as pointers to custom heap types that implement heap.Interface.

2. Step 2: Identify correct syntax

   Using &IntMaxHeap{} and &IntMinHeap{} creates pointers to heap structs ready for heap operations.

3. Final Answer:

   maxHeap := &IntMaxHeap{}; minHeap := &IntMinHeap{} -> Option A

4. Quick Check:

   Pointer to heap struct = A [OK]

Hint: Use pointers to heap structs for container/heap [OK]

Common Mistakes:

• Using heap.New which does not exist
• Swapping max-heap and min-heap types
• Initializing as slices without heap.Interface

3. Given the following sequence of numbers inserted into the data stream: 5, 15, 1, 3, what is the median after all insertions using two heaps?

medium

A. 5

B. 8

C. 3

D. 4

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 (maxHeap top=5); insert 15 (minHeap top=15); insert 1 ≤5 (maxHeap top=5, contains 5,1); insert 3 ≤5 (maxHeap top=5, contains 5,1,3), balance: len=3 >1+1, pop 5 -> push minHeap top=5 (15,5), maxHeap top=3 (1,3).

2. Step 2: Calculate median from heaps

   Heaps sizes equal (2 each). Median = average of maxHeap top (3) and minHeap top (5) = (3+5)/2 = 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Median = (3+5)/2 = 4 [OK]

Hint: Median is average of two heap tops if sizes equal [OK]

Common Mistakes:

• Taking median as maxHeap top only
• Not balancing heaps after insertion
• Calculating median as sum instead of average

4. In the following Go code snippet for median calculation, what is the bug?

func addNum(num int) {
  if maxHeap.Len() == 0 || num <= (*maxHeap)[0] {
    heap.Push(maxHeap, num)
  } else {
    heap.Push(minHeap, num)
  }
  if maxHeap.Len() > minHeap.Len()+1 {
    heap.Push(minHeap, heap.Pop(maxHeap))
  } else if minHeap.Len() > maxHeap.Len() {
    heap.Push(maxHeap, heap.Pop(minHeap))
  }
}

medium

A. Heaps are not balanced after insertion

B. Comparison operator should be < instead of <=

C. heap.Pop returns interface{}, needs type assertion before Push

D. maxHeap and minHeap are swapped in conditions

Solution

1. Step 1: Analyze balancing logic

   The first condition correctly balances when maxHeap is too large (> minHeap.Len()+1). But the second condition checks minHeap.Len() > maxHeap.Len(), which triggers rebalance correctly when minHeap is larger.

2. Step 2: Why heaps are not balanced

   Original code used > maxHeap.Len() + 1 which fails to rebalance when minHeap is exactly one larger. Changing to > maxHeap.Len() fixes this.

3. Final Answer:

   Heaps are not balanced after insertion -> Option A

4. Quick Check:

   minHeap balance: > max.Len() [OK]

Hint: minHeap balance when len(min) > len(max) [OK]

Common Mistakes:

• Using +1 symmetrically for both balance conditions
• Wrong size difference in minHeap check
• Not balancing after every insertion

5. You want to find the median of a large data stream where numbers can be negative, zero, or positive. Which approach using two heaps ensures correct median calculation even with duplicates and negative values?

hard

A. Use a single max-heap and pop elements until median is found

B. Use a max-heap for lower half and min-heap for upper half, balance sizes, and calculate median from tops

C. Sort all numbers in an array and pick middle element(s) each time

D. Use two min-heaps and merge their outputs to find median

Solution

1. Step 1: Choose correct heap types for halves

   Max-heap stores lower half (including negatives), min-heap stores upper half, handling all values correctly.

2. Step 2: Balance heaps and compute median

   Keep heaps balanced in size; median is top of max-heap if odd count, or average of tops if even count.

3. Final Answer:

   Use a max-heap for lower half and min-heap for upper half, balance sizes, and calculate median from tops -> Option B

4. Quick Check:

   Two heaps balanced handle negatives and duplicates [OK]

Hint: Balance max and min heaps for all number ranges [OK]

Common Mistakes:

• Using two min-heaps which can't split halves properly
• Sorting entire stream each time (inefficient)
• Using single heap only