CareerCup

public class RoundRobinIterator {
    List<Iterator> iterators;
    int index;  //current element
    int size;

    public RoundRobinIterator(List<Iterator> iter) {
        iterators = iter;
        size = iterators.size();
        index = 0;
        if(size > 0) locateNext();
    }

    public Object next() {
        locateNext();
        if(size == 0) return null;
        return iterators.get(index).next();
    }

    public boolean hasNext() {      // tradeoff - O(1) or O(n) ?
        if(size == 0) return false;
        return true;

    }

    private void locateNext() {
        if(iterators.get(index).hasNext()) {
            index = (index + 1) % size;
        }
        while(size > 0 && !iterators.get(index).hasNext()) {
            Iterator tmp = iterators.get(index);
            iterators.set(index, iterators.get(size - 1));
            iterators.set(size - 1, tmp);
            size--;
            if(index == size) index = 0;
        }
    }

}

Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

We provide ONE TO ONE courses that cover everything in an interview including
the latest interview questions categorized by companies,
algorithms,
SYSTEM DESIGN Courses(highly recommended for people interviewing with FLAG)
and mock interviews.

All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work.

Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.

Welcome to contact us with any questions. Thanks for reading.

The idea would be to keep track of which "Iterator" in the list was last accessed. If we reach the end of the list, then wrap it up from the beginning again.

Wrapping part can be done using count % size of the list

The Next method will check if the given iterator has any data left, if not, remove that iterator from the last so that next time this iterator is not accessed.

Here is a sample implementation with the result.

Time Complexity:
next: O(N) --> as we may end up scanning the entire list to get the value
hasNext: O(N)

public class IteratorRoundRobin {
    public static void main(String[] args) {
        List<Integer> l1 = new ArrayList<>();
        l1.add(1);

        List<Integer> l2 = new ArrayList<>();
        l2.add(10);l2.add(11);

        List<Integer> l3 = new ArrayList<>();
        l3.add(20);l3.add(21);l3.add(22);l3.add(23);l3.add(24);

        List<Iterator> input = new ArrayList<>();
        input.add(l3.iterator());
        input.add(l2.iterator());
        input.add(l1.iterator());
        RoundRobinIterator rri = new RoundRobinIterator(input);

        System.out.println("rri.hasNext() = " + rri.hasNext()); //Expected value: true
        System.out.println("rri.next() = " + rri.next()); //20
        System.out.println("rri.hasNext() = " + rri.hasNext()); //true
        System.out.println("rri.next() = " + rri.next()); //10
        System.out.println("rri.next() = " + rri.next()); //1
        System.out.println("rri.next() = " + rri.next()); //21
        System.out.println("rri.next() = " + rri.next()); //11
        System.out.println("rri.next() = " + rri.next()); //22
        System.out.println("rri.next() = " + rri.next()); //23
        System.out.println("rri.hasNext() = " + rri.hasNext()); //true
        System.out.println("rri.next() = " + rri.next()); //24
        System.out.println("rri.hasNext() = " + rri.hasNext()); //false
    }
}

class RoundRobinIterator {
    List<Iterator> list = null;
    int size = 0;
    int count = 0;
    public RoundRobinIterator(List<Iterator> itrs) {
        list = itrs;
        size = list.size();
    }

    public Object next(){
        Object result = null;
        while(list.size() > 0 || result != null) {
            Iterator itr = list.get(count % list.size());
            if (itr.hasNext()) {
                result = itr.next();
                count++;
                break;
            } else {
                list.remove(count % list.size());
            }
        }
        return result;
    }

    public boolean hasNext() {
        boolean result = false;
        while(list.size() > 0) {
            Iterator itr = list.get(count % list.size());
            if(itr.hasNext()) {
                result = true;
                break;
            } else {
                list.remove(count % list.size());
            }
        }
        return result;
    }
}

Result:
======
rri.hasNext() = true
rri.next() = 20
rri.hasNext() = true
rri.next() = 10
rri.next() = 1
rri.next() = 21
rri.next() = 11
rri.next() = 22
rri.next() = 23
rri.hasNext() = true
rri.next() = 24
rri.hasNext() = false

package ru.vitvlkv.collections;

import java.util.*;

public class RoundRobinCompositeIterator<E> implements Iterator<E> {

    private List<Iterator<E>> iterators;
    private Iterator<Iterator<E>> i;
    private Iterator<E> iterator;

    public RoundRobinCompositeIterator(Iterator<E> ...iterators) {
        if (iterators.length == 0) {
            throw new IllegalArgumentException("At least one iterator should be given");
        }
        this.iterators = new LinkedList<>();
        Arrays.stream(iterators)
                .filter(it -> it.hasNext())
                .forEach(it -> this.iterators.add(it));
        incCurrent();
        skipUntilHasNext();
    }

    @Override
    public boolean hasNext() {
        return !iterators.isEmpty() && iterator.hasNext();
    }

    @Override
    public E next() {
        if (iterators.isEmpty()) {
            throw new NoSuchElementException();
        }
        E result = iterator.next();
        incCurrent();
        skipUntilHasNext();
        return result;
    }

    private void skipUntilHasNext() {
        while (!iterators.isEmpty() && !iterator.hasNext()) {
            i.remove();
            incCurrent();
        }
    }

    private void incCurrent() {
        if (i == null || !i.hasNext()) {
            i = iterators.iterator();
        }
        iterator = i.hasNext() ? i.next() : null;
    }
}