Interview: Design an iterator for a collection of collections
Solution 1
Here is a possible implementation. Note that I left remove() unimplemented:
public class MultiIterator <T> implements Iterator<T>{
private Iterator<? extends Collection<T>> it;
private Iterator<T> innerIt;
private T next;
private boolean hasNext = true;
public MultiIterator(Collection<? extends Collection<T>> collections) {
it = collections.iterator();
prepareNext();
}
private void prepareNext() {
do {
if (innerIt == null || !innerIt.hasNext()) {
if (!it.hasNext()) {
hasNext = false;
return;
} else
innerIt = it.next().iterator();
}
} while (!innerIt.hasNext());
next = innerIt.next();
}
@Override
public boolean hasNext() {
return hasNext;
}
@Override
public T next() {
if (!hasNext)
throw new NoSuchElementException();
T res = next;
prepareNext();
return res;
}
@Override
public void remove() {
//TODO
}
}
Solution 2
This is an old question, but nowadays (2019) we have JDK8+ goodies. In particular, we have streams, which make this task straightforward:
public static <T> Iterator<T> flatIterator(Collection<Collection<T>> collections) {
return collections.stream()
.filter(Objects::nonNull)
.flatMap(Collection::stream)
.iterator();
}
I'm filtering null
inner collections out, just in case...
EDIT: If you also want to filter null
elements out of the inner collections, just add an extra non-null filter aflter flatMap
:
return collections.stream()
.filter(Objects::nonNull)
.flatMap(Collection::stream)
.filter(Objects::nonNull)
.iterator();
Solution 3
In this post you can see two implementations, the only (minor) difference is that it takes an iterator of iterators instead of a collection of collections.
This difference combined with the requirement to iterate the elements in a round-robin fashion (a requirement that wasn't requested by the OP in this question) adds the overhead of copying the iterators into a list.
The first approach is lazy: it will iterate an element only when this element is requested, the 'price' we have to pay is that the code is more complex because it needs to handle more edge-cases:
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
public class MultiIterator<E> implements Iterator {
List<Iterator<E>> iterators = new LinkedList<>();
Iterator<E> current = null;
public MultiIterator(Iterator<Iterator<E>> iterator) {
// copy the iterators into a list
while (iterator.hasNext()) {
iterators.add(iterator.next());
}
}
@Override
public boolean hasNext() {
boolean result = false;
if (iterators.isEmpty() && (current == null || !current.hasNext())) {
return false;
}
if (current == null) {
current = iterators.remove(0);
}
while (!current.hasNext() && !iterators.isEmpty()) {
current = iterators.remove(0);
}
if (current.hasNext()) {
result = true;
}
return result;
}
@Override
public E next() {
if (current == null) {
try {
current = iterators.remove(0);
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
E result = current.next(); // if this method was called without checking 'hasNext' this line might raise NoSuchElementException which is fine
iterators.add(current);
current = iterators.remove(0);
return result;
}
// test
public static void main(String[] args) {
List<Integer> a = new LinkedList<>();
a.add(1);
a.add(7);
a.add(13);
a.add(17);
List<Integer> b = new LinkedList<>();
b.add(2);
b.add(8);
b.add(14);
b.add(18);
List<Integer> c = new LinkedList<>();
c.add(3);
c.add(9);
List<Integer> d = new LinkedList<>();
d.add(4);
d.add(10);
d.add(15);
List<Integer> e = new LinkedList<>();
e.add(5);
e.add(11);
List<Integer> f = new LinkedList<>();
f.add(6);
f.add(12);
f.add(16);
f.add(19);
List<Iterator<Integer>> iterators = new LinkedList<>();
iterators.add(a.iterator());
iterators.add(b.iterator());
iterators.add(c.iterator());
iterators.add(d.iterator());
iterators.add(e.iterator());
iterators.add(f.iterator());
MultiIterator<Integer> it = new MultiIterator<>(iterators.iterator());
while (it.hasNext()) {
System.out.print(it.next() + ","); // prints: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,
}
}
}
and the second ('greedy' copying of all the elements from all the iterators in the requested order into a list and returning an iterator to that list ):
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class MultiIterator<E> {
Iterator<Iterator<E>> iterator = null;
List<E> elements = new LinkedList<>();
private MultiIterator(Iterator<Iterator<E>> iterator) {
this.iterator = iterator;
}
private void copyElementsInOrder() {
List<Iterator<E>> iterators = new LinkedList<>();
// copy the iterators into a list
while (iterator.hasNext()) {
iterators.add(iterator.next());
}
// go over the list, round-robin, and grab one
// element from each sub-iterator and add it to *elements*
// empty sub-iterators will get dropped off the list
while (!iterators.isEmpty()) {
Iterator<E> subIterator = iterators.remove(0);
if (subIterator.hasNext()) {
elements.add(subIterator.next());
iterators.add(subIterator);
}
}
}
public static <E> Iterator<E> iterator(Iterator<Iterator<E>> iterator) {
MultiIterator<E> instance = new MultiIterator<>(iterator);
instance.copyElementsInOrder();
return instance.elements.iterator();
}
// test
public static void main(String[] args) {
List<Integer> a = new LinkedList<>();
a.add(1);
a.add(7);
a.add(13);
a.add(17);
List<Integer> b = new LinkedList<>();
b.add(2);
b.add(8);
b.add(14);
b.add(18);
List<Integer> c = new LinkedList<>();
c.add(3);
c.add(9);
List<Integer> d = new LinkedList<>();
d.add(4);
d.add(10);
d.add(15);
List<Integer> e = new LinkedList<>();
e.add(5);
e.add(11);
List<Integer> f = new LinkedList<>();
f.add(6);
f.add(12);
f.add(16);
f.add(19);
List<Iterator<Integer>> iterators = new LinkedList<>();
iterators.add(a.iterator());
iterators.add(b.iterator());
iterators.add(c.iterator());
iterators.add(d.iterator());
iterators.add(e.iterator());
iterators.add(f.iterator());
Iterator<Integer> it = MultiIterator.<Integer>iterator(iterators.iterator());
while (it.hasNext()) {
System.out.print(it.next() + ","); // prints: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,
}
}
}
I included a simple 'test' code in order to show the way to use the MultiIterator, this is not always trivial (because of the use of Generics) as you can see on the line:
Iterator<Integer> it = MultiIterator.<Integer>iterator(iterators.iterator());
Solution 4
Here is another implementation:
import java.util.Iterator;
import java.util.NoSuchElementException;
import static java.util.Collections.emptyIterator;
public class Multiterator<E> implements Iterator<E> {
private Iterator<Iterator<E>> root;
private Iterator<E> current;
public Multiterator(Iterator<Iterator<E>> root) {
this.root = root;
current = null;
}
@Override
public boolean hasNext() {
if (current == null || !current.hasNext()) {
current = getNextNonNullOrEmpty(root);
}
return current.hasNext();
}
private Iterator<E> getNextNonNullOrEmpty(Iterator<Iterator<E>> root) {
while (root.hasNext()) {
Iterator<E> next = root.next();
if (next != null && next.hasNext()) {
return next;
}
}
return emptyIterator();
}
@Override
public E next() {
if (current == null) {
throw new NoSuchElementException();
}
return current.next();
}
}
Admin
Updated on June 20, 2022Comments
-
Admin almost 2 years
Design an iterator for a collection of collections in java. The iterator should hide the nesting, allowing you to iterate all of the elements belonging to all of the collections as if you were working with a single collection
-
Yuval Adam almost 14 yearsWhat's there to design? The prototype? The implementation?
-
Admin almost 14 yearsboth, what is the interface, and how would you implement it?
-
Jasper almost 14 yearsIf this is your job interview, why are you posting it here instead of just doing it?
-
Michael Williamson almost 14 yearsI wouldn't design anything myself -- I'd just use Google Collections: guava-libraries.googlecode.com/svn/trunk/javadoc/com/google/… . Having said that, the implementation is pretty straightforward if you really wanted to do it yourself.
-
Guest over 6 years@user399950 is your requirement is something like this -- Collection parent = new ArrayList(); Collection slave1 = new ArrayList(); slave1.add(10); slave1.add(20); Set slave2 = new HashSet(); slave2.add(30); slave2.add(40); parent.add(slave1); parent.add(slave2);
-
-
Kowshik over 11 yearsYour solution doesn't account for nulls in the given collection of collections. Fix: in prepareNext(), the inner loop should continue until it.next() is non-null before doing it.next().iterator(), and it should bail out if there is no non-null collection object left for us to use.
-
toolforger over 5 yearsIt has negative value: It claims that analyzing LinkedList somehow gives you an answer, which it does not (the real challenge is the two-tier implementation, not getting an Iterator out of a Collection).