Friday, November 7, 2014

Facebook: Merge k sorted arrays

Merge k sorted arrays, each array may have max "n" elements.
Warm up: Leetcode: Merge k sorted lists
http://buttercola.blogspot.com/2014/08/leetcode-merge-k-sorted-lists.html


Merge k-sorted list
Method 1: Divide-and Conquer
public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if(lists == null || lists.size() == 0) {
            return null;
        }
        
        if (lists.size() == 1) {
            return lists.get(0);
        }
        
        return mergeHelper(0, lists.size() - 1, lists);
    }
    
    private ListNode mergeHelper(int lo, int hi, List<ListNode> lists) {
        if (lo == hi) {
            return lists.get(lo);
        }
        
        int mid = lo + (hi - lo) / 2;
        
        // divide
        ListNode left = mergeHelper(lo, mid, lists);
        ListNode right = mergeHelper(mid + 1, hi, lists);
        
        // Conquer
        return mergeTwoLists(left, right);
    }
    
    private ListNode mergeTwoLists(ListNode left, ListNode right) {
        if (left == null) {
            return right;
        }
        
        if (right == null) {
            return left;
        }
        
        ListNode dummyNode = new ListNode(0);
        ListNode p = left;
        ListNode q = right;
        ListNode curr = dummyNode;
        
        while (p != null && q != null) {
            if (p.val <= q.val) {
                curr.next = p;
                p = p.next;
                curr = curr.next;
            } else {
                curr.next = q;
                q = q.next;
                curr = curr.next;
            }
        }
        
        if (p != null) {
            curr.next = p;
        } else if (q != null) {
            curr.next = q;
        }
        
        return dummyNode.next;
    }
}

Method 2: Use a heap
public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(), new PriorityQueueComparator());
        
        for (ListNode node : lists) {
            if (node != null) {
                pq.offer(node);
            }
        }
        
        ListNode dummyNode = new ListNode(0);
        ListNode curr = dummyNode;
        
        while (!pq.isEmpty()) {
            ListNode temp = pq.poll();
            curr.next = temp;
            curr = curr.next;
            
            if (temp.next != null) {
                pq.offer(temp.next);
            }
        }
        
        return dummyNode.next;
    }
    
    private class PriorityQueueComparator implements Comparator<ListNode> {
        public int compare(ListNode a, ListNode b) {
            return a.val - b.val;
        }
    }
}

Take-away message:

  1. Before careful the node is null the first time inserting a node into the pq
  2. How to create a pq, and implements the comparator
  3. Compare with Collections.sort(Array, new Comparator());
Merge k sorted array, instead of a list
public class Solution {
    public List<Integer> mergeKArraies(List<List<Integer>> arrs) {
        
        List<Integer> result = new ArrayList<Integer>();
        if (arrs == null || arrs.size() == 0 ) {
            return result;
        }
        
        if (arrs.size() == 1) {
            result.addAll(arrs.get(0));
        }
        
        int k = arrs.size();
        
        return mergeKArraiesHelper(arrs, 0, k - 1);
        
    }
    
    private List<Integer> mergeKArraiesHelper(List<List<Integer>> arrs, int lo, int hi) {
        if (lo == hi) {
            return arrs.get(lo);
        }
        
        int mid = lo + (hi - lo) / 2;
        
        List<Integer> left = mergeKArraiesHelper(arrs, 0, mid);
        List<Integer> right = mergeKArraiesHelper(arrs, mid + 1, hi);
        
        return merge(left, right);
    }
    
    private List<Integer> merge(List<Integer> left, List<Integer> right) {
        int i = 0;
        int j = 0;
        
        List<Integer> result = new ArrayList<Integer>();
        while (i < left.size() && j < right.size()) {
            if (left.get(i) <= right.get(j)) {
                result.add(left.get(i));
                i++;
            } else {
                result.add(right.get(j));
                j++;
            }
        }
        
        if (i < left.size()) {
            while (i < left.size()) {
                result.add(left.get(i));
                i++;
            }
        } else if (j < right.size()) {
            while (j < right.size()) {
                result.add(right.get(j));
                j++;
            }
        }
        
        return result;
    }
}

Note:
Merge k sorted arrays could not use priority queue solution. That is because when we add an element into the queue, we lost the connection of the node's original list. That is different from the Listed list.

Complexity:
Naive: O(k^2 * n)
Divide-and-Conquer: (klogk * n)
PQ: the same as D-and-C.


No comments:

Post a Comment