Wednesday, August 27, 2014

[LinkedIn, Twitter and Hulu Onsite] 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.

You could use the following code to test it.

No comments:

Post a Comment