Google Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
static class InterleaveIterator<E> implements Iterator<E>
{
ArrayList<Iterator<E>> iters;
Iterator<Iterator<E>> iterIter;
int cur;
public InterleaveIterator(ArrayList<Iterator<E>> iters)
{
this.iters=iters;
iterIter=iters.iterator();
cur=-1;
for(int i=0;i<iters.size();i++)
{
if(iters.get(i).hasNext())
{
cur=i;
break;
}
}
}
@Override
public boolean hasNext()
{
return cur!=-1;
}
@Override
public E next()
{
E ret=iters.get(cur).next();
for(int i=0;i<iters.size();i++)
{
int j=(cur+1+i)%iters.size();
if(iters.get(j).hasNext())
{
cur=j;
return ret;
}
}
cur=-1;
return ret;
}
}
public class InterleaveIterator<T> implements Iterator<T>
{
List<Iterator> iq;
int index;
public InterleaveIterator(List<Iterator> ilist)
{
index = 0;
iq = ilist;
}
@Override
public boolean hasNext() {
boolean has = false;
for (Iterator i : iq)
{
has |= i.hasNext();
}
return has;
}
@Override
public T next() {
Iterator itr = iq.get(index);
while (!itr.hasNext())
{
advIndex();
itr = iq.get(index);
}
T val = (T)itr.next();
advIndex();
return val;
}
void advIndex()
{
index = (index < iq.size()-1) ? index+1 : 0;
}
}
public class InterleaveIterators<E> implements Iterator<E>{
public int cursor;
public ArrayList<Iterator<E>> list = null;
public InterleaveIterators(){
list = new ArrayList<Iterator<E>>();
cursor=0;
}
public void addIterator(Iterator<E> it){
list.add(it);
}
@Override
public boolean hasNext(){
int cnt = 0;
if (list==null || list.isEmpty())
return false;
boolean hasNext = list.get(cursor).hasNext();
//iterate till hasNext is false and there are more elements to iterate in next iterator
while (!hasNext && cnt < list.size()-1){
cursor++;
//for interleaving
if(cursor == list.size())
cursor=0;
hasNext = list.get(cursor).hasNext();
if(hasNext)
break;
else
cnt++;
}
return hasNext;
}
public E next(){
int current = cursor;
cursor++;
//for interleaving
if(cursor == list.size())
cursor = 0;
return list.get(current).next();
}
public void remove() {
throw new UnsupportedOperationException();
}
public static void main(String[] args){
ArrayList<Integer> i1 = new ArrayList<Integer>();
i1.add(1);
i1.add(2);
i1.add(3);
i1.add(4);
i1.add(5);
ArrayList<Integer> i2 = new ArrayList<Integer>();
i2.add(11);
i2.add(12);
i2.add(13);
ArrayList<Integer> i3 = new ArrayList<Integer>();
i3.add(111);
i3.add(112);
i3.add(113);
i3.add(114);
i3.add(115);
i3.add(116);
i3.add(117);
i3.add(118);
InterleaveIterators<Integer> iter = new InterleaveIterators<Integer>();
iter.addIterator(i1.iterator());
iter.addIterator(i2.iterator());
iter.addIterator(i3.iterator());
while(iter.hasNext()){
System.out.print(iter.next() + " ");
}
}
}
import java.util.*;
public class InterleaveIterators<E> implements Iterator<E>{
public int cursor;
public ArrayList<Iterator<E>> list = null;
public InterleaveIterators(){
list = new ArrayList<Iterator<E>>();
cursor=0;
}
public void addIterator(Iterator<E> it){
list.add(it);
}
@Override
public boolean hasNext(){
int cnt = 0;
if (list==null || list.isEmpty())
return false;
boolean hasNext = list.get(cursor).hasNext();
//iterate till hasNext is false and there are more elements to iterate in next iterator
while (!hasNext && cnt < list.size()-1){
cursor++;
//for interleaving
if(cursor == list.size())
cursor=0;
hasNext = list.get(cursor).hasNext();
if(hasNext)
break;
else
cnt++;
}
return hasNext;
}
public E next(){
int current = cursor;
cursor++;
//for interleaving
if(cursor == list.size())
cursor = 0;
return list.get(current).next();
}
public void remove() {
throw new UnsupportedOperationException();
}
public static void main(String[] args){
ArrayList<Integer> i1 = new ArrayList<Integer>();
i1.add(1);
i1.add(2);
i1.add(3);
i1.add(4);
i1.add(5);
ArrayList<Integer> i2 = new ArrayList<Integer>();
i2.add(11);
i2.add(12);
i2.add(13);
ArrayList<Integer> i3 = new ArrayList<Integer>();
i3.add(111);
i3.add(112);
i3.add(113);
i3.add(114);
i3.add(115);
i3.add(116);
i3.add(117);
i3.add(118);
InterleaveIterators<Integer> iter = new InterleaveIterators<Integer>();
iter.addIterator(i1.iterator());
iter.addIterator(i2.iterator());
iter.addIterator(i3.iterator());
while(iter.hasNext()){
System.out.print(iter.next() + " ");
}
}
}
The same question was asked in my phone interview.
import java.util.*;
public class InterleaveIterators<E> implements Iterator<E>{
public int cursor;
public ArrayList<Iterator<E>> list = null;
public InterleaveIterators(){
list = new ArrayList<Iterator<E>>();
cursor=0;
}
public void addIterator(Iterator<E> it){
list.add(it);
}
@Override
public boolean hasNext(){
int cnt = 0;
if (list==null || list.isEmpty())
return false;
boolean hasNext = list.get(cursor).hasNext();
//iterate till hasNext is false and there are more elements to iterate in next iterator
while (!hasNext && cnt < list.size()-1){
cursor++;
//for interleaving
if(cursor == list.size())
cursor=0;
hasNext = list.get(cursor).hasNext();
if(hasNext)
break;
else
cnt++;
}
return hasNext;
}
public E next(){
int current = cursor;
cursor++;
//for interleaving
if(cursor == list.size())
cursor = 0;
return list.get(current).next();
}
public void remove() {
throw new UnsupportedOperationException();
}
public static void main(String[] args){
ArrayList<Integer> i1 = new ArrayList<Integer>();
i1.add(1);
i1.add(2);
i1.add(3);
i1.add(4);
i1.add(5);
ArrayList<Integer> i2 = new ArrayList<Integer>();
i2.add(11);
i2.add(12);
i2.add(13);
ArrayList<Integer> i3 = new ArrayList<Integer>();
i3.add(111);
i3.add(112);
i3.add(113);
i3.add(114);
i3.add(115);
i3.add(116);
i3.add(117);
i3.add(118);
InterleaveIterators<Integer> iter = new InterleaveIterators<Integer>();
iter.addIterator(i1.iterator());
iter.addIterator(i2.iterator());
iter.addIterator(i3.iterator());
while(iter.hasNext()){
System.out.print(iter.next() + " ");
}
}
}
As input has different types of iterator, So can not make it generic.
import java.util.Arrays;
import java.util.Iterator;
/**
* Created by Akshay on 5/27/2016.
*/
public class InterLeaveIterator implements Iterator {
private Iterator<?>[] iterators;
private int currentIndex;
public InterLeaveIterator(Iterator<?>... iterators) {
this.iterators = iterators;
if (iterators.length == 0) {
throw new IllegalArgumentException();
}
currentIndex = -1;
}
public boolean hasNext() {
boolean hasNext = false;
for (int i = 0; i < iterators.length; i++) {
currentIndex = ++currentIndex % iterators.length;
hasNext = iterators[currentIndex].hasNext();
if (hasNext)
return true;
}
return hasNext;
}
public Object next() {
Object o = iterators[currentIndex].next();
return o;
}
public void remove() {
}
public static void main(String a[]) {
Iterator iterator =
new InterLeaveIterator(
Arrays.asList(new Integer[]{1, 2, 3, 4, 5, 6}).iterator(),
Arrays.asList(new String[]{"a", "b", "c"}).iterator(),
Arrays.asList(new Double[]{1.1, 1.2, 1.3, 1.4}).iterator()
);
while (iterator.hasNext()) {
System.out.println(iterator.next().toString());
}
}
}
package test;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
public class InterleaveIterator<E> implements Iterator<E> {
List<Iterator<E>> listIterator = null;
int rows = 0;
int columns = 0;
int totalListsOfIterator = -1;
E next;
Iterator<E> iterator ;
int maximunSizeList = 5;
InterleaveIterator(List<Iterator<E>> listIter){
listIterator = listIter;
totalListsOfIterator = listIterator.size();
}
public static void main(String[] args) {
Collection<Object> listIntegers = new ArrayList<Object>();
listIntegers.add(1);
listIntegers.add(2);
listIntegers.add(3);
listIntegers.add(4);
List listTwo = new ArrayList<String>();
listTwo.add("Str1");
listTwo.add("Str2");
listTwo.add("Str3");
listTwo.add("Str4");
listTwo.add("Str5");
ArrayList<Object> i3 = new ArrayList<Object>();
i3.add(111);
i3.add(112);
i3.add(113);
i3.add(114);
i3.add(115);
i3.add(116);
i3.add(117);
i3.add(118);
List<Iterator<Object>> listIterator = new ArrayList<Iterator<Object>>();
listIterator.add(listIntegers.iterator());
listIterator.add(listTwo.iterator());
listIterator.add(i3.iterator());
InterleaveIterator<Object> interleaveIterator = new InterleaveIterator<Object>(listIterator);
while (interleaveIterator.hasNext()){
Object object = interleaveIterator.next();
System.out.println(object);
}
}
@Override
public boolean hasNext() {
boolean hasNext = false;
if (columns < totalListsOfIterator ){
iterator = listIterator.get(columns++);
if ( iterator.hasNext() ){
next = iterator.next();
hasNext = true;
}else{
while ( columns < totalListsOfIterator ){
iterator = listIterator.get(columns++);
if ( iterator.hasNext() ){
next = iterator.next();
hasNext = true;
break;
}
}
}
}
if (columns == totalListsOfIterator){
columns = 0;
}
return hasNext;
}
@Override
public E next() {
iterator.remove();
return next;
}
@Override
public void remove() {
iterator.remove();
}
}
- guilhebl May 18, 2016