# Missing level of technical depth (Recursive to Iterative)

I recently have given a coding test in a reputable IT company. There were three coding questions.

They refused me by saying that

as we felt they didn't demonstrate the level of technical depth we're seeking from candidates

Question 2 : Missing level of technical depth (Flatten Tree)

and this is the 1st question.

Question 1:

Reimplement this code so that its results will always be the same, but that it does not cause a stack overflow on large inputs. Your solution must still implement the Folder interface.

package iteration;

import java.util.Queue;

public interface Folder<T, U>
{
U fold(U u, Queue<T> list, Function2<T,U,U> function);
}


package iteration;

public interface Function2<T, U, R>
{
R apply(T t, U u);
}


package iteration;

import java.util.Iterator;
import java.util.Queue;

public class MyFolder<T, U> implements Folder<T, U>
{

public U fold(U u, Queue<T> ts, Function2<T, U, U> fun) {

if(u == null || ts == null || fun == null)
throw new IllegalArgumentException();

if (ts.isEmpty()) {
return u;
}

//get an iterator first instead of forEach loop, because poll() is modifying underlying collection/queue
Iterator<T> iter = ts.iterator();
while (iter.hasNext()) { //loop over the items

u = fun.apply( ts.poll() , u);

}

return u;
}

public static void main(String[] args) {

Folder<Integer,Integer> folder = new MyFolder<Integer, Integer>();

for(int lop =0; lop < 1000000; lop++ ){ //add some values in the Queue
}
Integer result = folder.fold(0, q, new Function2<Integer, Integer, Integer>() {
public Integer apply(Integer val1, Integer val2) {
return val1 + val2;
}
});

System.out.println("Result: " + result);
}
}

• Can you give a bit more context on the task? Was it related to any real system or just imaginary? And what did the original code look like? May 23, 2014 at 15:44
• This code was given to me and was told to just make it iterative. It was previously recursive. Besides I wasn't given any context nor other details. May 23, 2014 at 15:46
• The question says reimplement, what is the original code? May 26, 2014 at 7:02

as we felt they didn't demonstrate the level of technical depth we're seeking from candidates

This is a stock response. The engineers who interviewed you probably said something like “nah, not good enough”, so someone in HR sent you their stock response. Don't worry about the exact words; it wasn't written about you.

Some problems they might have objected to:

• fold shouldn't throw an IllegalArgumentException when U is null; null is a reasonable input.
• It traverses the Queue with both Queue.poll (which removes the first element) and an iterator (which doesn't modify the queue). Pick one or the other. Doing both may not even have well-defined behavior — what happens to the iterator when you remove the current element?
• The initial isEmpty check is redundant. If the queue is empty, the iteration loop will do nothing.
• There are lots of blank lines that take space without contributing to readability. That you include them in such a small program suggests you're not used to large programs.

There are also some design flaws in the specification.

• Folder should not be an interface. It makes no sense to create an object in order to call its fold method; fold should simply be a static method.
• If the original version used Queue.poll instead of an iterator, then it destroys the contents of the queue. It's usually not a good idea to modify arguments unnecessarily, because it tends to create bugs.
• fold should probably accept any Iterable, not just a Queue.

If you didn't point out these problems, they might take that as a sign you wouldn't notice design flaws in real work either. Part of a programmer's job is noticing problems and (when feasible) fixing them!

• Generally I agree, but Folder as an interface with one method does make sense. See en.wikipedia.org/wiki/Strategy_pattern May 24, 2014 at 3:13
• @Tom: Reifying a strategy is useful only to allow switching between multiple strategies, but there's no indication that's needed here. May 24, 2014 at 4:40
• In an interview setting, there's rarely an indication of why complexity is needed. Here, it could be as simple as including an interface to see how comfortable an applicant is with implementing an interface. May 25, 2014 at 3:08