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;
}
}
Chandra Patni