Given a list of k iterators. Implement MergingIterator to merge them. If you are not familiar with Iterators check similar questions.
class MergingIterator implements Iterator<Integer> {
public MergingIterator(List<Iterator<Integer>> iterators) {
}
public boolean hasNext() {
}
public Integer next() {
}
}Example
MergingIterator itr = new MergingIterator([[2, 11, 9], [4, 10]]);
itr.hasNext(); // true
itr.next(); // 2
itr.next(); // 4
itr.next(); // 11
itr.next(); // 10
itr.next(); // 9
itr.hasNext(); // false
itr.next(); // errorThis is similar to merge K sorted iterator but I am not able to figure out how to do this using Java.
I gave below solution but it does sorting:
class MergingIterator implements Iterator<Integer> {
private final Map<Iterator<Integer>, Integer> curMap;
private final Queue<Iterator<Integer>> iteratorQueue;
public MergingIterator(List<Iterator<Integer>> iterators) {
this.curMap = new HashMap<>();
this.iteratorQueue = new PriorityQueue<>(Comparator.comparingInt(this.curMap::get));
for (Iterator<Integer> iter : iterators) {
if (iter.hasNext()) {
curMap.put(iter, iter.next());
this.iteratorQueue.add(iter);
}
}
}
public boolean hasNext() {
return !iteratorQueue.isEmpty();
}
public Integer next() {
if (iteratorQueue.isEmpty()) {
throw new NoSuchElementException("Iterator is empty");
}
Iterator<Integer> iter = iteratorQueue.poll();
Integer res = curMap.get(iter);
if (iter.hasNext()) {
curMap.put(iter, iter.next());
iteratorQueue.add(iter);
}
return res;
}
}Can someone modify above code, so iterators gets merged not in sorted order?
Comments (4)