Merge with elegance

It’s perhaps the last time I asked this interview question last week. Write a function to return a sorted array containing all elements from two given int arrays. The input arrays are sorted but omission is intentional. Bonus points for:

  1. asking if input array is already sorted?
  2. identifying that it’s the merge step of merge-sort algorithm
  3. or naming the function merge

I have seen correct, clever, dumb, outrageous, uncomfortable and painful responses. For those who provide good answers, I ask them to identify Queue operations and think of an elegant solution instead of the fastest solution. Here is a stunningly elegant implementation of merge operation which treats input and output arrays as Queues.


#ignore mutability of a, b
#first is peek operation and shift is dequeue operation 
def merge(a, b)
  c = []
  c << (a.first < b.first ? a.shift : b.shift) until 
      a.empty? || b.empty? 
  c += a
  c += b
end

Java solution in 7 lines of code:

public static int[] merge(int[] a, int[] b) {
  Q cq = new Q(new int[a.length + b.length]);
  Q aq = new Q(a);
  Q bq = new Q(b);

  while(aq.notEmpty() && bq.notEmpty()) 
      cq.enqueue(aq.peek() < bq.peek() ? aq.dequeue() : bq.dequeue());
  while(aq.notEmpty()) cq.enqueue(aq.dequeue());
  while(bq.notEmpty()) cq.enqueue(bq.dequeue());
  
  return cq.elms;
}

//You will need a helper Queue class called Q to go with it. 
class Q {
    int current;
    int[] elms;

    Q(int[] elms) {
        this.elms = elms;
    }

    boolean notEmpty() {
        return current = elms.length;
    }

    int peek() {
        return elms[current];
    }

    int dequeue() {
        return elms[current++];
    }

    void enqueue(int elm) {
        elms[current++] = elm;
    }
}
Advertisements

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

Create a free website or blog at WordPress.com.

%d bloggers like this: