Google Interview Question
Country: United States
Interview Type: In-Person
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to 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 G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.
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;
}
}
}
Too complex impl presented, we can do much simpler:
def Sample : {
$$ : def(){
$.its = list([0:random(4) + 1 ]) ->{
l = list([0:random(5)]) ->{ random(100) }
println(l)
l.iterator()
}
$.index = -1
},
hasNext : def(){
while ( !empty($.its) ) {
$.index = ($.index + 1) % size( $.its )
it = $.its[$.index]
if ( it.hasNext ) { return true }
$.its.remove( $.index )
$.index -= 1
}
false
},
next : def(){ return $.its[ $.index].next() }
}
s = new ( Sample )
while ( s.hasNext() ){
printf(' %s ', s.next())
}
println()
- aonecoding February 27, 2017