Resource Library

You’re invited to check out out all the different learning resources in the guide: problems and projects, former Google interview questions, online courses, education sites, videos, and more. You can search for your favorite topics.

If you like tongue twisters and a challenge that tests your coding skills and creativity, sink your teeth into this former Google interview question. Given an iterator of iterators, implement an interleaving iterator (We promise Dr. Seuss didn't invent this one). Great opportunity to practice with nesting, choosing between data structures, and more.

Take the challenge

Google

The Challenge

Given an iterator of iterators, implement an interleaving iterator

Background: Iterator defined

In object-oriented programming, the iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container's elements. The iterator pattern decouples algorithms from containers; in some cases, algorithms are necessarily container-specific and thus cannot be decoupled. This code snippet illustrates:

Copied
int[] arr = [1, 2, 3];Iterator<Integer> it = arr.iterator();while(it.hasNext()){  print it.next();}// 123hasNext() // returns whether or not the iterator has additional elementsnext() // returns next element in iterator, throws NoSuchElementException otherwise.
Your challenge, should you choose to accept it...

Given an iterator of iterators, implement an interleaving iterator that takes in an iterator of iterators, and emits elements from the nested iterators in interleaved order. That is, if we had the iterators i and j iterating over the elements [ia, ib, ic] and [ja, jb] respectively, the order in which your interleaving iterator should emit the elements would be [ia, ja, ib, jb, ic].

Your interleaving iterator should implement the Iterator interface, take in the iterator of iterators in its constructor, and provide the next and hasNext methods. Assume that there are no additional methods offered by the iterator.

Given the following three iterators put into an array of iterators…

Copied
int[] arr1 = [1, 2, 3];int[] arr2 = [4, 5];int[] arr3 = [6, 7, 8, 9];Iterator<Integer> a = arr1.iterator();Iterator<Integer> b = arr2.iterator();Iterator<Integer> c = arr3.iterator();Iterator<Integer>[] iterlist = [a, b, c];

… build an “Interleaving Flattener” (IF), which works much like an iterator:

Copied
IF itfl = new IF(iterlist);while(IF.hasNext()){  print IF.next();}// 1 4 6 2 5 7 3 8 9

To assist you, here’s a skeleton for the class:

Copied
class IF{  public IF(Iterator<T>[] iterlist){  }  public T next(){  }    public boolean hasNext(){  }}
Learning objectives

This question gives you the chance to practice with iterators, iteration, data structures, classes, and nesting. It calls for thoughtful problem-solving and optimizing your solution. If you write it successfully in one language, try it again in a second.

Solution explained, commentary

Here are some possible solutions:

Less Efficient Solution - O(k) operations

Initialize by iterating over the nested iterators, adding them to a member list or array (linked list is fine).

Have a helper to move to the next iterator that can provide the next element. This can be called in both hasNext() and next(). Helper should only go through each nested iterator once (no more elements if it goes a full cycle without finding anything)

To interleave you have to hold on to references to all the inner Iterators (i.e. all the iterators returned by the outer Iterator) in order to be able to revisit the first one once you reach the last one. This is correct for the ones for which hasNext() is true. So the solution must use a data structure from which you can prune the empties.

This requires maintaining a bit more state than just the collection of iterators. A common solution is to store all the iterators in a List, then when it hits the end of the list, wrap back until each iterator is expired. If you hit an iterator that is expired (.hasNext() returns false), you can skip over it.

More Efficient Solution - O(1) operations, O(k) initialization

Don't add an iterator to the iterator list upon initialization if it’s empty. If an iterator does not have any more elements, remove it from the list. This will also simplify the helper method by not having to keep track of a cycle.

Note that for this to be O(1) for next() then getting the next iterator and removing it must also be O(1) - using a linked list for storage and its iterator (a new one for each cycle) for getting and removal is one possibility.

Another possibility is a queue, where you only add an iterator back to the end of the queue if it has more elements.

The Queue (generally more optimal)

Use the queue to do the cycling of the list for you. When you pull an element from an iterator, check to see if the iterator is empty. If the iterator is not empty, add it back to the queue. If it’s empty, then you’re out of elements.

If done correctly, this is a slightly easier version of Solution 2 to write, as it leverages existing data structures to do most of the abstraction for you.

Assumes:

  • k iterators
  • w elements / iterator
  • n total elements
  • implementation (assuming O(1) pop), this should be:

  • O(k) constructor
  • O(1) next
  • O(1) hasNext
  • Code snippet for solution

    Solution one: The Array

    Assumes
    - k iterators
    - w elements / iterator
    - n total elements

    Java Copied
    class IF{    private int iter_index = 0;    private Iterator<T>[] iterlist;    public IF(Iterator<T>[] iterlist) {        This.iterlist = iterlist;    }    public T next() throws NoSuchElementException {        for(int i = 0; i < this.iterlist.length; i++) {            int new_iter_index = this.iter_index + i % this.iterlist.length;            if(iterlist[new_iter_index].hasNext()) {                T val = iterlist[new_iter_index].next();                iter_index = new_iter_index + 1 % this.iterlist.length;                return val;            }        }        throw NoSuchElementException;    }        public boolean hasNext() {        for(int i = 0; i < this.iterlist.length; i++) {            if(iterlist[i].hasNext()) {                return true;            }        }        return false;    }}
    Solution two: The LinkedList

    Assumes
    - k iterators
    - w elements / iterator
    - n total elements

    Java Copied
    class IF{    private int iter_index = 0;    private LinkedList<Iterator<T>> iterlist;    public IF(Iterator<T>[] iterlist) {        this.iterlist = LinkedList(iterlist);        for (int i = 0; i < this.iterlist.size(); i++) {            if (!this.iterlist[i].hasNext()) {                this.iterlist.remove(i);            }        }    }    public T next() throws NoSuchElementException {        if (!hasNext()) throw NoSuchElementException;        T val = iterlist[iter_index].next();        if (!this.iterlist[iter_index].hasNext()) {            this.iterlist.remove(iter_index);        }        iter_index = this.iter_index + 1 % this.iterlist.size();        return val;    }        public boolean hasNext() {        return this.iterlist.size() != 0;    }}
    Solution three: The Queue (more optimal)

    Assumes
    - k iterators
    - w elements / iterator
    - n total elements - And that we have a Queue class that generally works. Add will add to the end, pop will pop from the front.

    Java Copied
    class IF{    private Queue<Iterator<T>> iterqueue;    public IF(Iterator<T>[] iterlist) {        this.iterqueue = new Queue();        for (int i = 0; i <iterlist.size(); i++) {            if (iterlist[i].hasNext()) this.iterqueue.add(i);        }    }    public T next() throws NoSuchElementException {        if (!hasNext()) throw NoSuchElementException;        Iterator<T> it = this.iterqueue.pop();        T val = it.next();        if(it.hasNext()) this.iterqueue.add(it);        return val;    }        public boolean hasNext() {        return this.iterqueue.size() != 0;    }}