## Interview Question for Java Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

``````private class minHeapElement {
int index;
int value;
}
PriorityQueue<minHeapElement> minHeap = new PriorityQueue(iters.size(), (a,b)-> a.value-b.value );``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

This is just "merge k sorted arrays". Use merge sort.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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,``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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()) {
}
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);
}
}

}

Comment hidden because of low score. Click to expand.
0

``````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()) {
}
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);
}
}

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.