@lycjava3 Yes, WalkerIX takes linear space and chase1991 only constant. That's why I meant it deserves it's own spot in the light :-). For formatting, start writing a new question or answer and you'll see info/options above the editor and a preview below it. The same formatting stuff works in comments.
I don't see the point of not using existing iterators to implement ZigzagIterator. Yes they are all iterators, and yes, they have the same interface, but they behave in VERY DIFFERENT WAYS. What's wrong with building a house with bricks? Avoid using existing iterators just makes the code less readable and less efficient(think about the case when v1 and v2 are linked lists, what's the time complexity of v1.get(index)?). Even if you copy them to array lists, you'll use much more space than simply using iterators. Would you really not use iterators if you encounter the same problem in real world?
An interview problem is supposed to be a simplified version of a real-world problem. And you are supposed to give a solution just like what you would give when you encountered it during work. It makes sense to add time or space constraints as we have seen, since those are also what we are facing in real world. And it makes sense to forbid using existing libraries or APIs only when it would achieve a better performance if without them, which happens when what we want to implement are very basic, like some string operations. So @aaron_iglesias no offense, your interviewer was very ridiculous.
I don't find it cool that you copy the vectors. If you're exposing an iterator interface for vector it is expected to work in O(1) space.. You could use a pointers to the vectors or iterators (you will need pointers to the end of each one also).
@soamaaazing Great strategy to use a queue to handle vector switching. Intuitively, one would employ an additional "indicator" to reference the current vector for next value retrieval (I used an iterator pointing to current vector for k vector case). However, the pop and push operations of queue itself can perform the job for free.
I think "Round-Robin Iterator" would be good. Or "Cyclic Iterator". Though Round-Robin sounds nicer and already suggests that there are several things and that we're going through each of them ("cyclic" could refer to cycling through a single 1d-vector).
The logic is right. I was asked a very similar question during a interview, and the problem of this solution is that you have to store all data in memory. If it is huge, not practical. In that case, should store iterator over input collections then