Dan D Kim

Let's share stories

If you are going to use Javascript for the coding interview, be prepared for heaps

2020-03-30 Dan D. Kimjavascript

Javascript is great. It’s simple.

It’s dynamically typed. There isn’t too much “boiler plate” code, unlike Java.

It’s a solid choice for a coding interview.

But there is one thing that Javascript falls short of other popular languages that can make you perform bad in interviews.

Javascript does not have a standard heap / priority queue data structure that you can use out of the box.

Imagine you get a question where the optimal runtime and space complexity is only achievable by using a priority queue / heap. What do you do?

Sure, there are npm libraries out there done by individuals, but are you really going to import npm modules during your interview? If your interviewer is cool with it, maybe. But unless the package is widely accepted like Lodash, then it could be frowned upon.

Other languages like Python and Java have these data structures built into their libraries, but Javascript falls short on this one.

So let’s talk about what you should do with Javascript when an interviewer asks a heap question.

Intro

Q: What kind of heaps are we talking about?

In this post, we are talking about Binary Heaps. If you don’t know what they are, read this

Q: What kind of ordering of Binary Heaps are we talking about?

We are talking about min-heap and max-heap orderings.

Min-heap: value of the node is less than its children.

Max-heap: value of the node is greater than its children.

“Heap is not necessary to solve a question”

True.

You can still solve a question without using a heap.

But there are questions where using a heap will get you the optimal runtime and space complexity, which is why there is such an advantage to using it.

Here’s an example question, taken from Leetcode.

Question 1

Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

If you haven’t solved this question, try solving it before reading the solution!!

No-heap vs heap solution

You could simply solve this by putting all the elements into an array, sorting it and returning the element at the kth index.

Sorted Array: [1,5,9,10,11,12,13,13,15]

Index to return: array.length - k

Problem solved. emoji-white_check_mark

Hey but what is your space and runtime complexity?

Runtime: O( nlog(n) ) average, O( n^2 ) worst case

Space: O( log(n) ) average

Those are the complexities of Quicksort. Why Quicksort? Because that’s what the Javascript V8 Engine (the stuff that runs on Google Chrome, Node, etc) uses. You can read more about it here.

Also you need to know this: even though Quicksort sorts everything in-place, it partitions the array and calls itself recursively, which adds to the space (stack) complexity.

Now, let’s compare against the heap solution. What are the runtimes / space if you were to use a heap?

With an array-implementation of a heap, you could solve within the following runtime and space complexities:

Runtime: O( nlog(n) )

Space: O( 1 )

Runtime doesn’t have a worst case of O( n^2 ). emoji-white_check_mark

It uses constant space, given that the heap is implemented iteratively. You can find a good example of iterative implementation in Javascript further down this post, or here in Java (just so you get the idea).

The following table summarizies the comparison.

Runtime Space
No heap O( nlog(n) ) average
O( n^2 ) worst case
O( log(n) )
Heap O( nlog(n) ) O( 1 )

Since the runtime for the average case is the same, you might be thinking ”isn’t that good enough“?

Let’s look at a question where the difference is substantial.

Question 2

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Input:

[
  1->4->5,
  1->3->4,
  2->6
]

Output: 1->1->2->3->4->4->5->6

If you haven’t solved this question, try solving it before reading the solution!!

No heap vs heap solution

Without using a heap, you could solve this question by sorting each array in ascending order by their first element.

Then you pop the first element from the first arraay and add it to your output.

You do this each time you pop an element and add it to your output.

There are k arrays and n elements.

Sorting k arrays by their first element will take O( klog(k)) time on average. O( k^2 ) worst case.

You are doing this for each element in the k arrays. If all k arrays had n elements, you will do this n times.

So your total runtime will be O( nklog(k) ) average, O( nk^2 ) worst case.

Space complexity will be O( log(k) ).

What if you use a heap?

With a heap, everytime you heapify the k arrays, it will take O( log(k) ) time.

You will need to do this for each element in the k arrays.

So the total runtime will be O( nlog(k) ) time.

Space complexity will be O( k ) or O( 1 ), depending on how you implement the heap. You could do everything in-place to reach O( 1 ) but it’s a lot of work and your interviewer may not see it as being necessary, so long as you are able to talk about how you could implement it using O( 1 ) space.

We can see from the following table that the runtime and space complexity is a lot more optimal with a heap.

Runtime Space
No heap O( n * klog(k) ) average
O( nk^2 ) worst case
O( log(k) )
Heap O( n*log(k) ) O( 1 )

Plan B

When you are given a heap question, you might simply state that the heap isn’t a standard data structure in Javascript, and the interviewer might give you a grace pass.

But here’s something you can do to win some points.

Knowing how to implement the array-based heap will impress your interviewer.

It’s a lot easier than you may think it is.

No, you don’t need a class.

No, you don’t need dozens of lines of code.

All you need is a function that takes in an array and heapifies the array.

This requires you to understand the logic of an array-based heap. If you haven’t read it yet, read it here.

Here’s what I mean.

For Question 1, we could do something like the following:

for (let i = 0; i < k; i++) {
  minHeapify(input) // O( log(n) ) runtime
  popMin(input) // O( 1 ) runtime
}

return input[1] // index starts at 1 due to the array-heap implementation

You could merge the popMin functionality inside minHeapify, but for simplicity here I won’t.

Here’s my Javascript implementation of minHeapify(), which is coming from the Java implementation of percolatingDown(int n) here

function minHeapify (array, index) {
  const temp = array[index]
  let childIndex

  for (; index * 2 < array.length; index = childIndex) {
    childIndex = index * 2

    // Choose the smaller of the two (left, right) children
    if (childIndex != array.length - 1 && array[childIndex] > array[childIndex + 1]) {
      childIndex ++
    }

    if (temp > array[childIndex]) {
      array[index] = array[childIndex]
    } else {
      break
    }
  }

  array[index] = temp
}

You could use such a function for both Question 1 and Question 2.


I hope you learned something. Let me know if anything could be better explained. Happy interviewing :)