First round phone screen. I got asked an Iterator question, and I failed because I didn't practice enough.
I'm sharing the question for everyone. Overall I thought the interview experience was pretty good. The interviewer was really nice and gave me hints, and I feel like their company culture is good too, and the work-life balance is good as well.
Implement a UnionIterator class that takes two strictly sorted iterators and produces a new iterator with the following properties:
- The new iterator contains the union of the elements from both input iterators. If an element appears in both inputs, it appears only once in the new iterator.
- The elements in the new iterator are also strictly sorted.
- Avoid using too much memory when the input iterators contain many elements.
Example 1
Iterator 1: 2, 4, 6, 8, 10
Iterator 2: 1, 2, 3, 5, 8, 13
Output: 1, 2, 3, 4, 5, 6, 8, 10, 13
Example 2
Iterator 1: apple, banana, orange, tree
Iterator 2: apple, tree, zoo
Output: apple, banana, orange, tree, zoo
Example 3
Iterator 1: -10, -9, -5, -1, 0, 2, 4
Iterator 2: -9, -5, -3, -2, 0, 1, 2
Output: -10, -9, -5, -3, -2, -1, 0, 1, 2, 4
Example 4
Iterator 1: 1, 2, 3
Iterator 2: (empty)
Output: 1, 2, 3
The input iterators follow this interface:
- hasNext() returns true if the iteration has more elements.
- next() returns the next element in the iteration (an int or a string).
UnionIterator should take the two iterators in its constructor and implement the same two methods, hasNext() and next().
At first I approached this like a linked list problem, and only later realized it was different. Here is how I'd solve it: cache one current value for each of the two iterators. On every next(), compare the two cached values and return the smaller one, advancing only the corresponding iterator. If the two values are equal, return it only once and advance both iterators, which takes care of the dedup. This only needs two extra stored values, so the space complexity is O(1).
Discussion
Loading comments…