Some more on interview questions – Heaps

I haven’t been writing anything for some time. It is not because I was a lazy git; quite the contrary, it is because I have been studying for the interview. Yes, for another interview which I, miraculously, have not failed this time (nice for a change huh). But this means that I now have more things to add to my programming interviews topic.

Everyone knows that algorithms and data structures questions take an important place in interviews. These two topics are intertwined, because for some algorithms, a choice of the data structure determines the running time of the algorithm and makes it actually useful, instead of just some mind-bending exercise. Usually, people are recommended to refresh such data structures as linked lists, trees, queues, stacks, and heaps before the interview.

A side note: not many questions about the trees are usually asked at the interview; and you will more often see a programming task being about a linked list or even a simple array. Why is that? Well, maybe it is because a lot of such questions require to actually know the algorithm, because it would be hard to invent it on the spot. (There’s even a question on Quora about Why graph questions are not asked that often answered by Grace Laakmann, who is a great authority on everything interview-related). That doesn’t mean you still don’t have to know at least BFS and DFS though. But also, there’s one structure that does come up rather often. It is a Heap

What is a heap? It is a balanced tree-like structure that guarantees a O(log(n)) time to find or insert an element and O(1) time to determine a max(min) element because it’s always at the head of a heap.

What are the cases where the heap can be useful? Well, as Tim Roughgarden tells in his great Coursera course on algorithms, if you see that you need to find a max/min repeatedly, then you should consider using a heap.

In fact, there is a whole sorting method called heap sort, which is totally based on using the heap. That is, all elements are dumped into the heap, and then the root is repeatedly extracted until the heap is empty. Voila! The data is now sorted in O(n*log(n)) time.

So, let us look at the example from leetcode.com called a K-way merge. You have K sorted lists, each with length N, and you need to merge them into one. How would you go about it?

The first idea would be, why not a heap sort? Dump them all into the heap, get back out, and walk away smiling. But this way, we do not use the fact that the lists are pre-sorted. So, heap sort would give us O(n * k * log(n)) time, with O(k*n) space. Can we do better?

Actually, yes we can.

The basic idea is, that as the lists are pre-sorted, then the first minimum element is among the K list heads. And the second minimum is among the K elements that you get once the first minimum is found and its list moves to the next element, etc. So, the idea would be, we need to keep K pointers, starting at list heads, find the min element across the current pointers, add it to the result and move its pointer to the next position.

Which means that in each step, we need to find the min element. And that is where the heap comes in. The difference from our first idea is, the heap always contains no more than K elements. Which means that the min search is O(log(k)), where K is always less than N. We still go through all the elements though. So, the time complexity would be O(k*n*log(k)), with space O(k). It’s not a groundbreaking change, but still nice, considering that usually K is much less than N.

Full example from Leetcode (with the custom class for list data structure):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    private class KeyComparator implements Comparator {
        @Override
        public int compare(ListNode self, ListNode other) {
            int val = self != null? self.val: -1;
            int otherVal = other != null? other.val: -1;
            return val > otherVal? 1: (val < otherVal? -1: 0);
        }
    }
    
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        ListNode root = null;
        ListNode current = null;
        int k = lists.length;
        PriorityQueue q = new PriorityQueue(k, new KeyComparator());
        
        // initialize current nodes
        for (ListNode head: lists) {
            if (head != null) {
                q.add(head);
            }
        }
        
        while (!q.isEmpty()) {
            // get min node
            ListNode head = q.poll();
            // create result node
            ListNode node = new ListNode(head.val);
            if (root == null) {
                root = node;
            }
            if (current != null) {
                current.next = node;
            }
            current = node;
            // now we need to move that node list to next
            // it means we add next key to queue
            if (head.next != null) {
                q.add(head.next);
            }
        }
        return root;
    }
}
Advertisements

About Maryna Cherniavska

I have productively spent 10+ years in IT industry, designing, developing, building and deploying desktop and web applications, designing database structures and otherwise proving that females have a place among software developers. And this is a good place.
This entry was posted in interviews, java, Uncategorized and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s