Google Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
I was asked similar question in one of the interview. I think you can implement the same with some modification.
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
public class UnionIterator implements Iterator<String> {
Collection<Iterator<String>> c;
public UnionIterator(Collection<Iterator<String>> c) {
this.c=c;
}
@Override
public boolean hasNext() {
if(!c.isEmpty()){
for (Iterator iterator = c.iterator(); iterator.hasNext();) {
Iterator<String> iterator2 = (Iterator<String>) iterator.next();
if(iterator2.hasNext()){
return true;
}
}
}
return false;
}
@Override
public String next() {
for (Iterator iterator = c.iterator(); iterator.hasNext();) {
Iterator<String> iterator2 = (Iterator<String>) iterator.next();
if(iterator2.hasNext()){
return iterator2.next();
}
}
return null;
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
public static void main(String[] args) {
List l1 = new ArrayList<String>();
List l2 = new ArrayList<String>();
l1.add("abc");l1.add("def");
l2.add("fer");l2.add("hgy");
Collection<Iterator<String>> ct = new ArrayList<Iterator<String>>();
ct.add(l1.iterator());
ct.add(l2.iterator());
UnionIterator ut = new UnionIterator(ct);
while(ut.hasNext()){
System.out.println(ut.next());
}
}
}
I initially thought of using a circular array and keeping a pointer to the current iterator, but this Iterator of Iterators is nicer.
In your implementation above, every call to hasNext() increments the union iterator (not a desired side effect).
You would need to somehow get the next Iterator in the collection without actually incrementing the union iterator's pointer, or move that pointer back one step after you're done with hasNext(). But don't think you can reverse with an Iterator. You can however use a ListIterator instead for that.
Actually hasNext() instantiates a new iterator using Collection c, and calling next() on the iterator for c only increments the iterator for the collection itself, not the union iterator, so this is not an issue since these iterators do not share common state. However I see a major issue with the next() function because it will instantiate a new iterator over Collection c each time it is called, which will always return the next element from whichever iterator comes first instead of alternating between different iterators in c. Instead the iterator in the next() function should be a member variable of UnionIterator that keeps track of which iterator we returned the last element from.
Actually the hasNext() function does not increment the union iterator. It instantiates a new iterator from the collection of iterators, which does not have shared state because it advances over the collection. However the union iterator's next() function will not work because it instantiates a new iterator over the collection each time it is called, which will result in it always removing the next element from the first iterator with another element. Instead this iterator should be a member variable so that the union iterator can track the current iterator in the collection and get the next element from the next iterator.
Actually the hasNext() function does not increment the union iterator. It instantiates a new iterator from the collection of iterators, which does not have shared state because it advances over the collection. However the union iterator's next() function will not work because it instantiates a new iterator over the collection each time it is called, which will result in it always removing the next element from the first iterator with another element. Instead this iterator should be a member variable so that the union iterator can track the current iterator in the collection and get the next element from the next iterator.
Actually the hasNext() function does not increment the union iterator. It instantiates a new iterator from the collection of iterators, which does not have shared state because it advances over the collection. However the union iterator's next() function will not work because it instantiates a new iterator over the collection each time it is called, which will result in it always removing the next element from the first iterator with another element. Instead this iterator should be a member variable so that the union iterator can track the current iterator in the collection and get the next element from the next iterator.
Actually the hasNext() function does not increment the union iterator. It instantiates a new iterator from the collection of iterators, which does not have shared state because it advances over the collection. However the union iterator's next() function will not work because it instantiates a new iterator over the collection each time it is called, which will result in it always removing the next element from the first iterator with another element. Instead this iterator should be a member variable so that the union iterator can track the current iterator in the collection and get the next element from the next iterator.
You can try writting something like this...
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
public class UnionIterator implements Iterator<String> {
Collection<Iterator<String>> c;
public UnionIterator(Collection<Iterator<String>> c) {
this.c=c;
}
@Override
public boolean hasNext() {
if(!c.isEmpty()){
for (Iterator iterator = c.iterator(); iterator.hasNext();) {
Iterator<String> iterator2 = (Iterator<String>) iterator.next();
if(iterator2.hasNext()){
return true;
}
}
}
return false;
}
@Override
public String next() {
for (Iterator iterator = c.iterator(); iterator.hasNext();) {
Iterator<String> iterator2 = (Iterator<String>) iterator.next();
if(iterator2.hasNext()){
return iterator2.next();
}
}
return null;
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
public static void main(String[] args) {
List l1 = new ArrayList<String>();
List l2 = new ArrayList<String>();
l1.add("abc");l1.add("def");
l2.add("fer");l2.add("hgy");
Collection<Iterator<String>> ct = new ArrayList<Iterator<String>>();
ct.add(l1.iterator());
ct.add(l2.iterator());
UnionIterator ut = new UnionIterator(ct);
while(ut.hasNext()){
System.out.println(ut.next());
}
}
}
Simple Solution - create new List and pack into it with proper order:
package google.task;
import java.util.*;
public class IteratorOfIterators {
public static void main(String[] args) {
List<String> l1 = new LinkedList<>();
List<String> l2 = new LinkedList<>();
l1.add("abc");l1.add("def");l2.add("fer");l2.add("hgy");
Iterator<?> ct[] = {l1.iterator(),l2.iterator()} ;
Iterator<String> iterator = new IteratorOfIterators((Iterator<String>[])ct).getIterator();
while (iterator.hasNext()){
System.out.println(iterator.next()+" ");
}
}
List<String> newList = new LinkedList<>();
IteratorOfIterators(Iterator<String>[] its) {
boolean isEmpty = false;
while (!isEmpty) {
isEmpty = true;
for (Iterator<String> it : its) {
if (it.hasNext()) {
newList.add(it.next());
isEmpty = false;
}
}
}
}
public Iterator<String> getIterator() {
return newList.iterator();
}
}
public class CustomIterator<T> {
private Iterator<T> [] iterators;
private int currentIterator = 0;
private int size = 0;
public CustomIterator(Iterator<T> [] itrs){
this.iterators = itrs;
this.size = itrs.length;
}
public boolean hasNext(){
int incrementSize = 0;
while(incrementSize < this.size && !((Iterator<T>)iterators[currentIterator%size]).hasNext()){
currentIterator++;
incrementSize++;
}
if(incrementSize == size)
return false;
return ((Iterator<T>)iterators[currentIterator%size]).hasNext();
}
public T next(){
T currNode = null;
if(this.hasNext()){
currNode = ((Iterator<T>)iterators[currentIterator%size]).next();
currentIterator++;
}
return currNode;
}
}
public class Node{
int value;
Node(int value){
this.value = value;
}
}
public static void main(String [] args){
IteratorPractice ip = new IteratorPractice();
Set<Node> a = new LinkedHashSet<Node>();
a.add(ip.new Node(1));a.add(ip.new Node(6));
Set<Node> b = new LinkedHashSet<Node>();
b.add(ip.new Node(2));b.add(ip.new Node(7));b.add(ip.new Node(10));
Set<Node> c = new LinkedHashSet<Node>();
c.add(ip.new Node(3));c.add(ip.new Node(8));
Set<Node> d = new LinkedHashSet<Node>();
d.add(ip.new Node(4));
Set<Node> e = new LinkedHashSet<Node>();
e.add(ip.new Node(5));e.add(ip.new Node(9));e.add(ip.new Node(12));
Iterator<Node> [] itrs = new Iterator[5];
itrs[0] = a.iterator();
itrs[1] = b.iterator();
itrs[2] = c.iterator();
itrs[3] = d.iterator();
itrs[4] = e.iterator();
CustomIterator<Node> test = ip.new CustomIterator<Node>(itrs);
while(test.hasNext()){
System.out.println(test.next().value);
}
}
Get the elements from each iterator in the input array one at a time, each time checking if you still can use that iterator(using hasNext). Store them in an ArrayList. Instantiate an iterator over this list of combined elements and use it to serve the next element every time.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
public class CustomIterator implements Iterator<Integer>{
ArrayList<Integer> listOfCombinedElements = new ArrayList<>();
Iterator<Integer> combinedIterator;
public CustomIterator(Iterator<Integer>[] input) {
while(elementsLeft(input)) {
for(Iterator i: input) {
if(i.hasNext()){
listOfCombinedElements.add((Integer) i.next());
}
}
}
combinedIterator = listOfCombinedElements.iterator();
}
private boolean elementsLeft(Iterator[] input) {
boolean answer = false;
for(Iterator i: input){
if(i.hasNext()) {
return true;
}
}
return answer;
}
@Override
public boolean hasNext() {
return combinedIterator.hasNext();
}
@Override
public Integer next() {
return combinedIterator.next();
}
@Override
public void remove() {
}
public static void main(String[] args) {
ArrayList<Integer> a = new ArrayList<>(Arrays.asList(10, 20));
ArrayList<Integer> b = new ArrayList<>(Arrays.asList(30));
ArrayList<Integer> c = new ArrayList<>(Arrays.asList(40, 50, 60));
Iterator<Integer>[] input = new Iterator[] {a.iterator(), b.iterator(), c.iterator()};
CustomIterator customIterator = new CustomIterator(input);
while(customIterator.hasNext()) {
System.out.println(customIterator.next());
}
}
}
-- Output --
10
30
40
20
50
60
simple groovy solution:
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
Iterator A = ['a1','a2'].iterator()
Iterator B = ['b1'].iterator()
Iterator C = ['c1','c2','c3'].iterator()
List iteratorList = [A,B,C]
Iterator combinedIterator = combineIterators(iteratorList)
while(combinedIterator.hasNext()){//print them out!
println combinedIterator.next()
}
//This is where the majic happens
Iterator combineIterators(List<Iterator> theList){
List responseList = []
//if any of them has a next element, then keep going
while(theList.find{it.hasNext()}){
for(Iterator iterator : theList){
if(iterator.hasNext()){
responseList << iterator.next()
}
}
}
return responseList.iterator()
}
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
Iterator A = ['a1','a2'].iterator()
Iterator B = ['b1'].iterator()
Iterator C = ['c1','c2','c3'].iterator()
List iteratorList = [A,B,C]
Iterator combinedIterator = combineIterators(iteratorList)
while(combinedIterator.hasNext()){//print them out!
println combinedIterator.next()
}
//This is where the majic happens
Iterator combineIterators(List<Iterator> theList){
List responseList = []
//if any of them has a next element, then keep going
while(theList.find{it.hasNext()}){
for(Iterator iterator : theList){
if(iterator.hasNext()){
responseList << iterator.next()
}
}
}
return responseList.iterator()
}
This is an implementation written in Java style Groovy. Since this a Software Engineer in Test interview, I am also pasting a lot of unit tests :)
class MultiIterator extends Specification {
@Unroll
def "given the collections #collections, MultiIterator should iterate over the following elements: #elements"(List<Collection> collections, List elements) {
given:
List<Iterator> iterators = collections.collect{ it.iterator() }
and:
MultiIteratorImpl multiIterator = new MultiIteratorImpl(iterators)
when:
List iteratedElements = []
while(multiIterator.hasNext()) {
iteratedElements << multiIterator.next()
}
then:
iteratedElements == elements
where:
collections | elements
[] | []
[[1], [2]] | [1, 2]
[[1, 2], [3, 4]] | [1, 2, 3, 4]
[[1, 2], [3, 4], [5,6]] | [1, 2, 3, 4, 5, 6]
[[], [], []] | []
[[1, 2, 3], []] | [1, 2, 3]
[[], [1, 2, 3], []] | [1, 2, 3]
[[null], [1, 2, 3]] | [null, 1, 2, 3]
}
def "should not iterate twice if the same iterator is used twice"() {
given:
List list = [1, 2]
and:
Iterator iterator = list.iterator()
and:
MultiIteratorImpl multiIterator = new MultiIteratorImpl([iterator, iterator])
expect:
multiIterator.next() == 1
multiIterator.next() == 2
multiIterator.hasNext() == false
}
@Unroll
def "should not create a multi iterator with the invalid iterators: #iterators"() {
when:
new MultiIteratorImpl(iterators)
then:
thrown IllegalArgumentException
where:
iterators << [
null,
[null],
[[1,2,3].iterator(), null, [4,5,6].iterator()]
]
}
def "should remove elements of collections"() {
given:
List listA = [1,2,3]
List listB = []
List listC = [4,5,6]
and:
List<Iterator> iterators = [listA.iterator(), listB.iterator(), listC.iterator()]
and:
MultiIteratorImpl multiIterator = new MultiIteratorImpl(iterators)
expect:
multiIterator.hasNext() == true
multiIterator.next() == 1
multiIterator.next() == 2
multiIterator.remove()
multiIterator.next() == 3
multiIterator.next() == 4
multiIterator.remove()
multiIterator.next() == 5
multiIterator.hasNext() == true
and:
listA == [1,3]
listB == []
listC == [5,6]
}
public class MultiIteratorImpl<T> implements Iterator<T> {
private List<Iterator<T>> iterators;
private int current = 0;
public MultiIteratorImpl(List<Iterator<T>> iterators) {
if(iterators == null) {
throw new IllegalArgumentException("Iterators should not be null");
}
for(Iterator<T> i : iterators) {
if(i == null) {
throw new IllegalArgumentException("Iterators should not be null");
}
}
this.iterators = iterators;
}
public boolean hasNext() {
moveToNextIteratorWithElements();
return (current < iterators.size());
}
public T next() {
if(hasNext() == false) {
// What is the right exception to be thrown here?
throw new IllegalStateException("There are no more elements");
}
return iterators[current].next();
}
public void remove() {
if(hasNext() == false) {
// What is the right exception to be thrown here?
throw new IllegalStateException("There are no more elements");
}
iterators[current].remove();
}
private void moveToNextIteratorWithElements() {
while(current < iterators.size() && iterators[current].hasNext() == false) {
current++;
}
}
}
}
A much simpler version.
import java.util.*;
class ListOfIterator{
static class CombinedIterator implements Iterator {
List<Iterator<String>> itList;
int curList = 0;
int listSize = 0;
CombinedIterator() {
itList = new ArrayList<Iterator<String>>();
}
void add(Iterator<String> it){
itList.add(it);
listSize ++;
}
public boolean hasNext() {
while(listSize != 0) {
if(itList.get(curList).hasNext()) {
return true;
} else {
itList.remove(curList);
listSize--;
}
}
return false;
}
public void remove(){}
public String next() {
String nextItem = itList.get(curList).next();
curList++;
if(curList == listSize)
curList = 0;
return nextItem;
}
}
public static void main(String args[]) {
List<String> list1 = new ArrayList<String>();
list1.add("a1");
list1.add("a2");
list1.add("a3");
List<String> list2 = new ArrayList<String>();
list2.add("b1");
list2.add("b2");
List<String> list3 = new ArrayList<String>();
list3.add("c1");
list3.add("c2");
list3.add("c3");
list3.add("c4");
CombinedIterator cIt = new CombinedIterator();
cIt.add(list1.iterator());
cIt.add(list2.iterator());
cIt.add(list3.iterator());
while(cIt.hasNext()) {
System.out.println(cIt.next());
}
}
}
I tried this and tested it. It works
import java.util.ArrayList;
import java.util.ListIterator;
import java.util.NoSuchElementException;
/**
*
* Write a method that combines an array of iterators into a new one, such that, e.g. for input [A B C] where:
A.next() returns a1, a2, respectively;
B.next() returns b1;
C.next() returns c1, c2, c3, respectively;
The new iterator will return elements in this order: a1 b1 c1 a2 c2 c3.
* ****/
public class CombineIterators {
public static void main(String[] args){
ArrayList<Integer> A = new ArrayList<Integer>();
ArrayList<Integer> B = new ArrayList<Integer>();
ArrayList<Double> C = new ArrayList<Double>();
ArrayList<Object> r = new ArrayList<Object>();
A.add(1);
A.add(3);
A.add(5);
A.add(7);
A.add(9);
B.add(2);
B.add(4);
B.add(6);
C.add(1.5);
C.add(2.5);
C.add(4.5);
C.add(3.5);
C.add(5.5);
C.add(6.5);
System.out.println(A.toString());
System.out.println(B.toString());
System.out.println(C.toString());
ListIterator<Integer> Ai = A.listIterator();
ListIterator<Integer> Bi = B.listIterator();
ListIterator<Double> Ci = C.listIterator();
while(Ai.hasNext() || Bi.hasNext() || Ci.hasNext()){
try{
r.add(Ai.next());
r.add(Bi.next());
r.add(Ci.next());
}catch(NoSuchElementException e){
try{
r.add(Bi.next());
}catch(NoSuchElementException e1){
try{
r.add(Ci.next());
}catch(NoSuchElementException e2){
e2.getMessage();
}
}
}
}
System.out.println(r.toString());
}
}
I tested this and tried it. It works!
import java.util.ArrayList;
import java.util.ListIterator;
import java.util.NoSuchElementException;
/**
*
* Write a method that combines an array of iterators into a new one, such that, e.g. for input [A B C] where:
A.next() returns a1, a2, respectively;
B.next() returns b1;
C.next() returns c1, c2, c3, respectively;
The new iterator will return elements in this order: a1 b1 c1 a2 c2 c3.
* ****/
public class CombineIterators {
public static void main(String[] args){
ArrayList<Integer> A = new ArrayList<Integer>();
ArrayList<Integer> B = new ArrayList<Integer>();
ArrayList<Double> C = new ArrayList<Double>();
ArrayList<Object> r = new ArrayList<Object>();
A.add(1);
A.add(3);
A.add(5);
A.add(7);
A.add(9);
B.add(2);
B.add(4);
B.add(6);
C.add(1.5);
C.add(2.5);
C.add(4.5);
C.add(3.5);
C.add(5.5);
C.add(6.5);
System.out.println(A.toString());
System.out.println(B.toString());
System.out.println(C.toString());
ListIterator<Integer> Ai = A.listIterator();
ListIterator<Integer> Bi = B.listIterator();
ListIterator<Double> Ci = C.listIterator();
while(Ai.hasNext() || Bi.hasNext() || Ci.hasNext()){
try{
r.add(Ai.next());
r.add(Bi.next());
r.add(Ci.next());
}catch(NoSuchElementException e){
try{
r.add(Bi.next());
}catch(NoSuchElementException e1){
try{
r.add(Ci.next());
}catch(NoSuchElementException e2){
e2.getMessage();
}
}
}
}
System.out.println(r.toString());
}
}
C# has the operator "yield" that we can use in method to combines the enumerators and returns the values as a single enumerator.
public IEnumerator<int> CombineIterators(IEnumerator<int>[] iterators)
{
bool[] used = new bool[iterators.Length];
int count = iterators.Length;
int index = 0;
while (count > 0)
{
if (!used[index])
{
used[index] = !iterators[index].MoveNext();
if (used[index])
count--;
else
yield return iterators[index].Current;
}
index = (index + 1) % iterators.Length;
}
}
public class CustomIterator implements Iterator<String> {
Iterator[] iters;
int pos;
public CustomIterator(Iterator[] iters) {
this.iters = iters;
pos = 0;
}
public boolean hasNext() {
for (Iterator iter : iters) {
if (iter.hasNext())
return true;
}
return false;
}
public String next() {
if (pos == iters.length)
pos = 0;
for (int i = pos; i < iters.length; i++) {
pos++;
if (iters[i].hasNext())
return (String) iters[i].next();
}
return null;
}
public static void main(String[] args) {
ArrayList<String> a = new ArrayList<String>();
ArrayList<String> b = new ArrayList<String>();
ArrayList<String> c = new ArrayList<String>();
a.add("a1");
a.add("a2");
b.add("b1");
c.add("c1");
c.add("c2");
c.add("c3");
Iterator[] iters = { a.iterator(), b.iterator(), c.iterator() };
CustomIterator customIterator = new CustomIterator(iters);
while (customIterator.hasNext()) {
System.out.println(customIterator.next());
}
}
}
- srterpe May 01, 2015