Interview Question
Java DevelopersCountry: United States
Interview Type: Phone Interview
Use a priority queue and insert elements into the queue as you go along and call next. Posting my solution below in Python:
from queue import PriorityQueue
class SuperIterator:
def __init__(self, iterators):
self.sortedQueue = PriorityQueue()
for iterator in iterators:
self.sortedQueue.put((next(iterator), iterator))
def hasNext(self):
return self.sortedQueue.qsize() != 0
def next(self):
value, iterator = self.sortedQueue.get()
try:
next_value = next(iterator)
self.sortedQueue.put((next_value, iterator))
except StopIteration:
pass
return value
Test code:
# Test code
# Example 1
list1 = [1, 4, 5,20]
list2 = [2,10,12,50]
s = SuperIterator([iter(list1), iter(list2)])
while s.hasNext():
print(s.next(), end=', ')
print()
# Output: 1, 2, 4, 5, 10, 12, 20, 50,
# Example 2
list1 = [12,14,16]
list2 = [4,7,9,50,100]
list3 = [6,8,10,13]
s = SuperIterator([iter(list1), iter(list2), iter(list3)])
while s.hasNext():
print(s.next(), end=', ')
print()
# Output: 4, 6, 7, 8, 9, 10, 12, 13, 14, 16, 50, 100,
import java.util.*;
public class Main {
public static void main(String ... args) {
var superIterator = new SuperIterator<>(
Arrays.asList(
Arrays.asList(1, 4, 5, 20).iterator(),
Arrays.asList(2, 10, 12, 50).iterator(),
Arrays.asList(5, 7, 17, 32).iterator(),
Arrays.asList(7, 16, 28, 40).iterator()
)
);
Collection<Integer> superIteratorSequence = new ArrayList<>();
while (superIterator.hasNext()) {
superIteratorSequence.add(superIterator.next());
}
System.out.println(superIteratorSequence);
// expecting
// [1, 2, 4, 5, 7, 10, 12, 16, 17, 20, 28, 32, 40, 50]
}
}
class SuperIterator<T extends Comparable> {
private final SortedMap<T, Integer> currentValuesMap;
private final ArrayList<Iterator<T>> iterators;
public SuperIterator(Collection<Iterator<T>> iters) {
this.iterators = new ArrayList<>(iters);
this.currentValuesMap = new TreeMap<>();
for (int i = 0; i < iterators.size(); i++) {
Iterator<T> iterator = iterators.get(i);
putNextNonDuplicatingValue(currentValuesMap, iterator, i);
}
int i = 0;
}
public boolean hasNext() {
return !currentValuesMap.isEmpty();
}
public T next() {
if (currentValuesMap.isEmpty()) {
return null;
}
T minValue = currentValuesMap.firstKey();
Integer minValueIteratorIndex = currentValuesMap.remove(minValue);
Iterator<T> minValueIterator = iterators.get(minValueIteratorIndex);
putNextNonDuplicatingValue(currentValuesMap, minValueIterator, minValueIteratorIndex);
return minValue;
}
private void putNextNonDuplicatingValue(
SortedMap<T, Integer> currentValuesMap,
Iterator<T> iterator,
int index
) {
if (iterator.hasNext()) {
T nextValue = iterator.next();
while (currentValuesMap.containsKey(nextValue) && iterator.hasNext()) {
nextValue = iterator.next();
}
currentValuesMap.putIfAbsent(nextValue, index);
}
}
}
import java.util.*;
public class Main {
public static void main(String ... args) {
var superIterator = new SuperIterator<>(
Arrays.asList(
Arrays.asList(1, 4, 5, 20).iterator(),
Arrays.asList(2, 10, 12, 50).iterator(),
Arrays.asList(5, 7, 17, 32).iterator(),
Arrays.asList(7, 16, 28, 40).iterator()
)
);
Collection<Integer> superIteratorSequence = new ArrayList<>();
while (superIterator.hasNext()) {
superIteratorSequence.add(superIterator.next());
}
System.out.println(superIteratorSequence);
// expecting
// [1, 2, 4, 5, 7, 10, 12, 16, 17, 20, 28, 32, 40, 50]
}
}
class SuperIterator<T extends Comparable> {
private final SortedMap<T, Integer> currentValuesMap;
private final ArrayList<Iterator<T>> iterators;
public SuperIterator(Collection<Iterator<T>> iters) {
this.iterators = new ArrayList<>(iters);
this.currentValuesMap = new TreeMap<>();
for (int i = 0; i < iterators.size(); i++) {
Iterator<T> iterator = iterators.get(i);
putNextNonDuplicatingValue(currentValuesMap, iterator, i);
}
int i = 0;
}
public boolean hasNext() {
return !currentValuesMap.isEmpty();
}
public T next() {
if (currentValuesMap.isEmpty()) {
return null;
}
T minValue = currentValuesMap.firstKey();
Integer minValueIteratorIndex = currentValuesMap.remove(minValue);
Iterator<T> minValueIterator = iterators.get(minValueIteratorIndex);
putNextNonDuplicatingValue(currentValuesMap, minValueIterator, minValueIteratorIndex);
return minValue;
}
private void putNextNonDuplicatingValue(
SortedMap<T, Integer> currentValuesMap,
Iterator<T> iterator,
int index
) {
if (iterator.hasNext()) {
T nextValue = iterator.next();
while (currentValuesMap.containsKey(nextValue) && iterator.hasNext()) {
nextValue = iterator.next();
}
currentValuesMap.putIfAbsent(nextValue, index);
}
}
}
This can be done, by maintaining a min heap of elements and its associated iterator index in a struct.
hasNext - returns if there are any elements in min heap
next fetches the top element in minheap , and then grabs its iterator and checks if it has any element if so add it to the minheap.
- Anonymous March 21, 2018