Google | Onsite | Merge K Sorted Iterators
Sithis
19621
GoogleAmazonUberIteratorOnsiteInterview

Given a list of k sorted 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, 5, 9], [], [4, 10]]);
itr.hasNext(); // true
itr.next(); // 2
itr.next(); // 4
itr.next(); // 5
itr.next(); // 9
itr.next(); // 10
itr.hasNext(); // false
itr.next(); // error
Solution

Java solution using PriorityQueue and PeekingIterator: https://leetcode.com/playground/Eu9epFf5

class MergingIterator implements Iterator<Integer> {
    private final Queue<PeekingIterator> queue;

    public MergingIterator(List<Iterator<Integer>> iterators) {
        queue = new PriorityQueue<>(iterators.size(), (i1, i2) -> Integer.compare(i1.peek(), i2.peek()));
        for (Iterator<Integer> iterator : iterators) {
            if (iterator.hasNext()) {
                queue.add(new PeekingIterator(iterator));
            }
        }
    }

    public boolean hasNext() {
        return !queue.isEmpty();
    }
    
    public Integer next() {
        PeekingIterator nextIter = queue.remove();
        Integer next = nextIter.next();
        if (nextIter.hasNext()) {
            queue.add(nextIter);
        }
        return next;
    }
}

Related problems:

Comments (30)