Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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<>();

List<Integer> l2 = new ArrayList<>();

List<Integer> l3 = new ArrayList<>();

List<Iterator> input = new ArrayList<>();
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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
Arrays.stream(iterators)
.filter(it -> it.hasNext())
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;
}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.