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:
- asking if input array is already sorted?
- identifying that it’s the merge step of merge-sort algorithm
- 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; } }