Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Find the Median of a Number Stream

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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,
A

Anonymous

· 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();
}
A

Anonymous

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

Anonymous

· 3 years ago

is anyone else's coding window not working?

A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 5 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
A

Anonymous

· 5 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

Reading Progress

0%

Vote for new content