Median of Data Stream Using Two Heaps in DSA Javascript - 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 Javascript

class MedianFinder {
  constructor() {
    this.small = [] // max heap
    this.large = [] // min heap
  }

  addNum(num) {
    if (this.small.length === 0 || num <= -this.small[0]) {
      this.small.push(-num)
      this.small.sort((a, b) => a - b)
    } else {
      this.large.push(num)
      this.large.sort((a, b) => a - b)
    }

    if (this.small.length > this.large.length + 1) {
      this.large.push(-this.small.shift())
      this.large.sort((a, b) => a - b)
    } else if (this.large.length > this.small.length) {
      this.small.push(-this.large.shift())
      this.small.sort((a, b) => a - b)
    }
  }

  findMedian() {
    if (this.small.length > this.large.length) {
      return -this.small[0]
    } else {
      return (-this.small[0] + this.large[0]) / 2
    }
  }
}

const mf = new MedianFinder()
mf.addNum(5)
mf.addNum(15)
mf.addNum(1)
mf.addNum(3)
const median = mf.findMedian()
console.log(median)

A 4

B 3

C 5

D 6

💡 Hint

Think about how the two heaps balance the numbers and how median is calculated from their tops.

After adding 5 and 15, median is (5+15)/2 = 10. After adding 1, median is 5. After adding 3, numbers are [1,3,5,15], median is (3+5)/2 = 4.

🧠 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 store all numbers twice for redundancy.

B To sort all numbers in ascending order efficiently.

C To use one heap for odd numbers and one for even numbers.

D To keep track of the lower half and upper half of numbers separately for quick median calculation.

💡 Hint

Think about how median relates to the middle values in a sorted list.

Two heaps split the data stream into lower half (max heap) and upper half (min heap). This allows quick access to middle values for median calculation.

🔧 Debug

advanced

Identify the Bug in MedianFinder Implementation

What error will this code produce when adding numbers and finding median?

DSA Javascript

class MedianFinder {
  constructor() {
    this.small = [] // max heap
    this.large = [] // min heap
  }

  addNum(num) {
    if (this.small.length === 0 || num <= -this.small[0]) {
      this.small.push(-num)
      this.small.sort((a, b) => a - b)
    } else {
      this.large.push(num)
      this.large.sort((a, b) => a - b)
    }

    if (this.small.length > this.large.length + 1) {
      this.large.push(-this.small.shift())
      this.large.sort((a, b) => a - b)
    } else if (this.large.length > this.small.length) {
      this.small.push(-this.large.shift())
      this.small.sort((a, b) => a - b)
    }
  }

  findMedian() {
    if (this.small.length > this.large.length) {
      return -this.small[0]
    } else {
      return (-this.small[0] + this.large[0]) / 2
    }
  }
}

const mf = new MedianFinder()
mf.addNum(1)
mf.addNum(2)
mf.addNum(3)
console.log(mf.findMedian())

A The code runs correctly and outputs 2

B The code outputs 1.5 instead of 2

C The code throws a TypeError because shift() is used on a sorted array without heap structure

D The code throws a SyntaxError due to missing semicolons

💡 Hint

Think about how shift() affects the heap property after sorting.

The code uses arrays and sorts them to simulate heaps but uses shift() which removes the first element, breaking the heap property. This causes incorrect behavior or errors.

📝 Syntax

advanced

Which Option Fixes the Heap Balancing Logic?

Given the buggy code below, which option correctly fixes the balancing logic to maintain heaps properly? class MedianFinder { constructor() { this.small = [] // max heap this.large = [] // min heap } addNum(num) { if (this.small.length === 0 || num <= -this.small[0]) { this.small.push(-num) this.small.sort() } else { this.large.push(num) this.large.sort() } if (this.small.length > this.large.length + 1) { this.large.push(-this.small.shift()) this.large.sort() } else if (this.large.length > this.small.length) { this.small.push(-this.large.shift()) this.small.sort() } } findMedian() { if (this.small.length > this.large.length) { return -this.small[0] } else { return (-this.small[0] + this.large[0]) / 2 } } }

A Replace shift() with pop() and use a proper heap data structure instead of sorting arrays.

B Remove all sorting calls and rely on push() only.

C Use unshift() instead of push() to add elements to arrays.

D Replace push() with concat() to add elements.

💡 Hint

Think about how heaps work and how to maintain their properties.

Heaps require specific operations like push and pop with heapify. Using shift() and sorting arrays breaks heap properties. Using pop() with a proper heap fixes this.

🚀 Application

expert

Calculate Median After Complex Stream Operations

Given the following sequence of numbers added to the MedianFinder: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, what is the median after all insertions?

DSA Javascript

class MedianFinder {
  constructor() {
    this.small = [] // max heap
    this.large = [] // min heap
  }

  addNum(num) {
    if (this.small.length === 0 || num <= -this.small[0]) {
      this.small.push(-num)
      this.small.sort((a, b) => a - b)
    } else {
      this.large.push(num)
      this.large.sort((a, b) => a - b)
    }

    if (this.small.length > this.large.length + 1) {
      this.large.push(-this.small.shift())
      this.large.sort((a, b) => a - b)
    } else if (this.large.length > this.small.length) {
      this.small.push(-this.large.shift())
      this.small.sort((a, b) => a - b)
    }
  }

  findMedian() {
    if (this.small.length > this.large.length) {
      return -this.small[0]
    } else {
      return (-this.small[0] + this.large[0]) / 2
    }
  }
}

const mf = new MedianFinder()
[10,20,30,40,50,60,70,80,90,100].forEach(n => mf.addNum(n))
console.log(mf.findMedian())

A 60

B 55

C 50

D 65

💡 Hint

Count the numbers and find the middle two values for even count.

There are 10 numbers, so median is average of 5th and 6th numbers in sorted order: (50 + 60)/2 = 55.