Apple Interview Question
Software Engineer / DevelopersCountry: United States
Most recursive functions can be written iteratively (in fact, if the last statement of a recursive function is the recursion, a compiler can optimize out the recursion, leaving an iterative version of the function). I think the task is to convert that recursive function into an iterative one.
Yes, you still might run out of memory, but your stack memory will be exhausted long before your heap.
As far as I understand, the question is about converting a recursive function to iterative one to eliminate stack overflow for large amount of input.
public class MyFolder<T, U> implements Folder<T, U> {
public U fold(U u, Queue<T> ts, Function2<T, U, U> function) {
if (u == null || ts == null || function == null)
throw new IllegalArgumentException();
while(!ts.isEmpty()) {
u = function.apply(ts.poll(), u);
}
return u;
}
}
Can you explain what is the problem is? You need to traverse folder's tree? User BFS and with FIFO queue or DFS with Stack all of them will be stored in Heap and won't cause StackOverflowError , just OutOfmemoryError)))
- glebstepanov1992 December 12, 2013