How to design and implement a deep iterator?

包子IT面试培训 助你拿到理想的offer!

Question:

Write a deep iterator to iterate through a list of objects or integer which could be another list or integer. This is frequently asked by LinkedIn, Twitter and Hulu.

For example, this collection contains Integer or another collection. L means it is a collection that contains either integer or another L.

----> 5

|

---- 3 -> 4 -> L -> 6

|

1 -> 2 -> L -> 7-> 8

We would expect an iterator to loop through it will print out 1, 2, 3, 4, 5, 6, 7, 8

Analysis:

The input is a list of objects which could be another list or a integer. The input is kind of similar to a tree or a forest data structure. Here we are asked to implement two functions of a iterator, hasNext and next. (Iterator in Java has hasNext(), next() and remove(). ) So we need to iterate through the tree. Using recursion it is easy, but here we need to convert a recursion problem to a iteration problem. So we need a stack to keep track of the levels we are in the iteration.

The code is like following.

....