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 );

- Anonymous March 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Basmati March 21, 2018 | Flag Reply
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,

- prudent_programmer March 22, 2018 | Flag Reply
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()) {
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);
}
}

}

- Shapovalov.Ivan86 July 22, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

}

- Shapovalov.Ivan86 July 22, 2020 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More