Google Interview Question
Country: United States
Interview Type: In-Person
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;
}
}
Looking for interview experience sharing and mentors?
- acoding167 March 15, 2019Visit 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.