Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Find the Median of a Number Stream (medium)

Problem Statement

Design a class to calculate the median of a stream of numbers. The class should have the following two methods:

  1. insertNum(int num): stores the number in the class
  2. findMedian(): returns the median of all numbers inserted in the class

If the count of numbers inserted in the class is even, the median will be the average of the two middle numbers.

Example 1:

1. insertNum(3)
2. insertNum(1)
3. findMedian() -> output: 2.0
4. insertNum(5)
5. findMedian() -> output: 3.0
6. insertNum(4)
7. findMedian() -> output: 3.5

Constraints:

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Azimul Haque

· 4 years ago

In the python solution, in the function insert_num, I couldn't understand the logic in this line, as there are no comments to understand the code, reaching out for your help.

if not self.maxHeap or -self.maxHeap[0] >= num:

The first part if not self.maxHeap I believe is checking if the maxHeap is empty or not. Am i correct?

The second part of logic -self.maxHeap[0] >= num, I didn't understand at all. What is it doing?

  • What is self.maxHeap[0]? is it the first element of maxHeap from begining? i.e. smallest value in maxHeap?
  • Why did we add a negative sign in -self.maxHeap[0]?
  • Why are we checking if -self.maxHeap[0] is >= num?

Please elaborate.

Show 1 reply
Amelia Sharpe

Amelia Sharpe

· 3 years ago

Why is the runtime O(logN) instead of O(NlogN)? It takes O(logN) to insert an element and balance the two heaps. And if we are inserting N elements, shouldn't the overall runtime be O(NlogN)?

Show 1 reply
Jay Karlsven

Jay Karlsven

· 2 years ago

In all of the previous problems for Heaps in JavaScript, the recommended solutions involved using sorted arrays to essentially "simulate" a Heap.

So my solution to the problem involved an insertion function that inserted to a min heap array. To retrieve the median, I simply calculated the middle element of the array (or middle 2 if the array length was even).

This solution seems so much simpler to me and had WAY less code than the recommended solution. I realize this isn't like, the "Heap" solution, so writing out an entire Heap class might help better with long term understanding of Heaps but this seems so much less complex to me. Someone want to point out where I'm wrong here?

class Solution {
  constructor() {
    this.nums = [];
  }

  insertNum(num) {
    let index
Show 1 reply
A

Athanasios Petsas

· 4 years ago

Could someone explain what this variable definition (in C++ solution) does: priority_queue, greater> minHeap; ? the greater is a functor, right? To me it seems like applying the greater functor for all the elements of a priority queue. Is it like having a maxHeap and through this greater functor we are turning it into a minHeap?

Show 5 replies
P

Pete Stenger

· 4 years ago

Would it be incorrect to insert into whatever heap is smaller in size, and then swap the tops of the heap if they are unordered?

Show 1 reply
K

kasey

· 3 years ago

is anyone else's coding window not working?

A

Aditya Bhave

· 2 years ago

If any of the heaps is empty, calling top() on them is undefined behavior. Consider changing the code like this

if (minHeap.empty()) {
   return maxHeap.empty() ? 0 : maxHeap.top();
}

if (maxHeap.size() == minHeap.size()) {
   return maxHeap.top() / 2.0 + minHeap.top() / 2.0;
}

return maxHeap.top();
}
Sourav Singh

Sourav Singh

· 2 years ago

package main

import (
    "container/heap"
    "fmt"
)

// MinHeap structure (heap of larger half)
type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] } // Min-heap: smaller values at top
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// MaxHeap structure (heap of smaller half, but as max-heap)
type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] } // Max-heap: larger values at top
func (h MaxHeap) Swap(i,
Singh Singh

Singh Singh

· 2 years ago

Time complexity of insertNum could be N*log(n) as it's called N times and each time it takes log(n) where n is the number of elements in heap.

Please explain if I'm wrong

Show 1 reply
Hasnain Zeeshan

Hasnain Zeeshan

· 2 months ago

There's a bug in your answer checking system. Ints are being treated as incorrect even if the number itself correct. For example:

Wrong Answer 0.079 s

[5,1,4]

Output: 4

Expected: 4.0

These are equivalent & the answer should be correct.