I said that it might be nice in a functional language using recursion, which seemed to surprise the interviewer. He offered that I could code it in any language I liked, but I decided to stick with Java, lacking the nerve to barge into Scala or Haskell on a whiteboard. And as I was thinking that doing the functional style in Java might require building some list-comprehension things, I decided to abandon the functional idea entirely.
I stumbled around a bit, coding and explaining, and ended up with a very messy whiteboard, but apparently did ok, as they've asked me back for more interviews.
I wasn't happy with the result though. Of course I didn't get to take the whiteboard home with me, but I decided to reproduce it approximately (I extracted a small helper that definitely hadn't been on the board), and it ended up like this:
public static List<Integer> merge(List<Integer> list1,
List<Integer> list2) {
if (null == list1)
return list2;
if (null == list2)
return list1;
ArrayList<Integer> result = new ArrayList<Integer>();
Iterator<Integer> iter1 = list1.iterator();
Iterator<Integer> iter2 = list2.iterator();
Integer next1 = getNext(iter1);
Integer next2 = getNext(iter2);
while ((null != next1) || (null != next2)) {
if (null == next1) {
result.add(next2);
next2 = getNext(iter2);
}
else if (null == next2) {
result.add(next1);
next1 = getNext(iter1);
}
else if (next1 < next2) {
result.add(next1);
next1 = getNext(iter1);
}
else {
result.add(next2);
next2 = getNext(iter2);
}
}
return result;
}
private static <T> T getNext(Iterator<T> iter) {
if (iter.hasNext()) {
return iter.next();
}
return null;
}
This does work, but it's not pretty, basically because it's in a very procedural style, and because there's some repetition I don't see an easy way to eliminate. So I considered what could be done to improve it.
My first impulse was of course to return to the functional idea. So here's the Scala code I should have written on that whiteboard:
def merge(list1: List[Int],
list2: List[Int]): List[Int] = list1 match {
case Nil => list2
case head1::tail1 => {
list2 match {
case Nil => list1
case head2::tail2 => {
if (head1<head2)
head1::merge(tail1, list2)
else
head2::merge(list1, tail2)
}
}
}
}
Much more concise, and reasonably clear modulo knowing Scala. And unless I went into complete panic because of the situation, I probably could have written it on the whiteboard and explained the Scala bits more quickly and with less stumbling than what I actually did. Of course this is using the Scala List class rather than the one from the Java collections library, so to actually use it from Java might involve some conversion.
As with much functional code, the main things needed for this are the head and tail functions (hidden by use of a pattern-matching idiom in theScala code above), which are not supplied by the Java collections library List. But away from the stress of interviews and whiteboards, it occurred to me that these are pretty trivial to make, and I quickly translated into Java:
public static List<Integer> merge(List<Integer> list1,
List<Integer> list2) {
if ((null == list1) || (list1.isEmpty()))
return list2;
if ((null == list2) || (list2.isEmpty()))
return list1;
ArrayList<Integer> result = new ArrayList<Integer>();
Integer head1 = head(list1);
Integer head2 = head(list2);
if (head1 < head2) {
result.add(head1);
result.addAll(merge(tail(list1), list2));
}
else {
result.add(head2);
result.addAll(merge(list1, tail(list2)));
}
return result;
}
private static Integer head(List<Integer> list) {
return list.get(0);
}
private static List<Integer> tail(List<Integer> list) {
return list.subList(1,list.size());
}
Not as pretty as the Scala version because Java lacks the pattern-match stuff, but definitely an improvement over the procedural mess. I could see changing it so that the list was decorated to add the head and tail functions instead of just having them as static utility methods.
I'd probably do something like this in real code, as I think list manipulation makes sense in functional style. But it's not quite normal Java style.
The other version uses iterators to traverse both lists, and has to grab appropriately from both and advance them both correctly, which is a bit painful. But it struck me that a natural OO approach might be to make a composite iterator in which to hide all those decisions. And in order to select which one without advancing both iterators, maybe a decorated iterator having lookahead capability would be nice. This lead to two new Iterator classes (in which I didn't bother implementing the remove method):
LookaheadIterator:
import java.util.Iterator;
public class LookaheadIterator<T> implements Iterator<T> {
private Iterator<T> delegate;
private T lookahead;
public LookaheadIterator(Iterator<T> iter) {
this.delegate = iter;
getNext();
}
@Override
public boolean hasNext() {
return (null != lookahead);
}
@Override
public T next() {
T current = lookahead;
getNext();
return current;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
public T lookahead() {
return lookahead;
}
private void getNext() {
if (delegate.hasNext()) {
lookahead = delegate.next();
}
else {
lookahead = null;
}
}
}
MergedIterator:
import java.util.Comparator;
import java.util.Iterator;
public class MergedIterator<T> implements Iterator<T> {
private Comparator<T> comparator;
private LookaheadIterator<T> iterator1;
private LookaheadIterator<T> iterator2;
public MergedIterator(Comparator<T> comparator,
Iterator<T> iter1, Iterator<T> iter2) {
this.comparator = comparator;
this.iterator1 = new LookaheadIterator<T>(iter1);
this.iterator2 = new LookaheadIterator<T>(iter2);
}
@Override
public boolean hasNext() {
return (iterator1.hasNext() || iterator2.hasNext());
}
@Override
public T next() {
T next1 = iterator1.lookahead();
T next2 = iterator2.lookahead();
if (null == next1) {
getNext(iterator2);
return next2;
}
if ((null == next2) || (comparator.compare(next1, next2) < 0)) {
getNext(iterator1);
return next1;
}
else {
getNext(iterator2);
return next2;
}
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
private void getNext(Iterator<T> iter) {
if (iter.hasNext()) {
iter.next();
}
}
}
The merge method itself (once you've fence-posted the null argument cases) is then of course a matter of creating the MergedIterator and iterating through it adding to a new list.
These extra classes make it a lot more code than the functional version for this toy example, and in fact maybe more code than the dumb procedural implementation, but it might be argued that this is a more object-oriented approach, and it might make sense if there were other needs for these iterators.
I still prefer the functional style for this example, and wish I'd done it in the interview.
