Median of Data Stream Using Two Heaps in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to add a number to the max heap.

DSA Typescript

maxHeap.[1](num);

Drag options to blanks, or click blank then click option'

Apop

Bpeek

Csort

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of push to add elements.

Trying to use peek which only views the top element.

We use push() to add a new number to the max heap.

2fill in blank

medium

Complete the code to balance the heaps when max heap size is greater than min heap size by more than one.

DSA Typescript

minHeap.[1](maxHeap.[2]());

Drag options to blanks, or click blank then click option'

Ashift

Bpop

Cpeek

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using peek instead of pop to remove element.

Using shift which is not a heap method.

We pop the top from maxHeap and push it into minHeap to balance sizes.

3fill in blank

hard

Fix the error in the code to get the median when heaps are of equal size.

DSA Typescript

return (maxHeap.[1]() + minHeap.[1]()) / 2;

Drag options to blanks, or click blank then click option'

Apeek

Bpop

Cpush

Dsort

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() removes elements and changes the heap.

Using push() is for adding elements, not retrieving.

We use peek() to get the top elements without removing them.

4fill in blank

hard

Fill both blanks to correctly insert a number into the appropriate heap.

DSA Typescript

if (num [1] maxHeap.[2]()) {
  maxHeap.push(num);
} else {
  minHeap.push(num);
}

Drag options to blanks, or click blank then click option'

A<=

B>

Cpeek

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() instead of peek() to compare.

Using > instead of <= changes the logic.

We compare num with the top of maxHeap using peek() and insert accordingly.

5fill in blank

hard

Fill all three blanks to rebalance heaps when min heap size is greater than max heap size.

DSA Typescript

if (minHeap.size() > maxHeap.size() + [1]) {
  maxHeap.[2](minHeap.[3]());
}

Drag options to blanks, or click blank then click option'

A1

Bpop

Cpush

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using 2 instead of 1 for size difference check.

Using pop and push in wrong order.

We check if minHeap is bigger by 1, then push the popped element from minHeap to maxHeap.

Practice

1. What is the main purpose of using two heaps (a max heap and a min heap) in the Median of Data Stream problem?

easy

A. To sort all numbers in ascending order

B. To store all numbers in a single data structure

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

D. To remove duplicates from 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 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 = efficient median [OK]

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

Common Mistakes:

• Thinking heaps sort all numbers fully
• Using one heap only
• Confusing heaps with arrays

2. Which TypeScript syntax correctly declares a max heap using a priority queue for numbers?

easy

A. const maxHeap = new PriorityQueue<number>((a, b) => b - a);

B. const maxHeap = new PriorityQueue<number>((a, b) => a - b);

C. const maxHeap = new PriorityQueue<number>();

D. const maxHeap = new PriorityQueue<number>((a, b) => a + b);

Solution

1. Step 1: Understand max heap comparator

   Max heap comparator returns positive if first is less than second, so b - a creates max heap.

2. Step 2: Check each option

   const maxHeap = new PriorityQueue<number>((a, b) => b - a); uses (b - a) which is correct for max heap; others do not create max heap order.

3. Final Answer:

   const maxHeap = new PriorityQueue<number>((a, b) => b - a); -> Option A

4. Quick Check:

   Comparator b - a = max heap [OK]

Hint: Max heap comparator subtracts first from second [OK]

Common Mistakes:

• Using a - b for max heap (creates min heap)
• Not providing comparator
• Using addition in comparator

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. 3

B. 4

C. 5

D. 8

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 -> maxHeap=[5] (top=5), minHeap=[]; Insert 15 -> minHeap=[15] (top=15), sizes 1:1; Insert 1 -> maxHeap=[5,1] (top=5), sizes 2:1; Insert 3 -> maxHeap=[5,3,1] (top=5), sizes 3:1 -> balance (max.size > min.size+1), move max.top=5 to minHeap -> maxHeap=[3,1] (top=3), minHeap=[5,15] (top=5), sizes 2:2.

2. Step 2: Calculate median from heaps

   Sizes equal, median = (maxHeap.top + minHeap.top)/2 = (3 + 5)/2 = 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Median of [5,15,1,3] = 4 [OK]

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

Common Mistakes:

• Taking median as top of one heap only
• Not balancing heaps after insertion
• Wrong average calculation

4. Consider this TypeScript snippet for adding a number to the data stream median finder:

if (num <= maxHeap.peek()) {
  maxHeap.enqueue(num);
} else {
  minHeap.enqueue(num);
}

// Balance heaps
if (maxHeap.size() > minHeap.size() + 1) {
  minHeap.enqueue(maxHeap.dequeue());
} else if (minHeap.size() > maxHeap.size()) {
  maxHeap.enqueue(minHeap.dequeue());
}

What is the bug in this code?

medium

A. It compares num with minHeap.peek() instead of maxHeap.peek()

B. It balances heaps incorrectly by moving elements the wrong way

C. It uses enqueue instead of push for heaps

D. It does not handle empty maxHeap before peek() call

Solution

1. Step 1: Analyze peek() usage on maxHeap

   If maxHeap is empty, calling peek() causes error because no element exists yet.

2. Step 2: Identify missing empty check

   Code should check if maxHeap is empty before peek() or handle initial insertion separately.

3. Final Answer:

   It does not handle empty maxHeap before peek() call -> Option D

4. Quick Check:

   Empty heap peek() causes runtime error [OK]

Hint: Check heap empty before peek() to avoid errors [OK]

Common Mistakes:

• Assuming heaps always have elements
• Mixing enqueue and push methods
• Balancing heaps incorrectly

5. You want to extend the Median of Data Stream solution to support removing numbers from the stream efficiently. Which data structure modification is best to support both insertion and removal while maintaining median calculation?

hard

A. Use two heaps with a hash map to mark removed elements lazily

B. Use two balanced binary search trees (like AVL or Red-Black trees) instead of heaps

C. Use a single sorted array and binary search for insertion and removal

D. Use two queues to store lower and upper halves

Solution

1. Step 1: Understand removal challenge in heaps

   Heaps do not support efficient arbitrary removal, so direct removal is costly.

2. Step 2: Explain lazy removal with hash map

   Mark elements as removed in a hash map and skip them during heap operations to simulate removal efficiently.

3. Step 3: Compare other options

   Balanced trees support removal but are more complex; arrays are inefficient; queues do not maintain order.

4. Final Answer:

   Use two heaps with a hash map to mark removed elements lazily -> Option A

5. Quick Check:

   Lazy removal with hash map + heaps = efficient median update [OK]

Hint: Lazy removal with hash map keeps heaps efficient [OK]

Common Mistakes:

• Trying direct removal from heaps
• Using arrays causing slow operations
• Ignoring complexity of balanced trees