Katkat
Back

Implement iterator merging lists with filtering

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a stateful iterator that performs a multi-way merge on sorted streams while applying filtering and deduplication logic on the fly.

Problem Statement

Implement an iterator class FilteredMergeIterator that takes a list of iterators and a blocked_ids set. The input iterators are guaranteed to be sorted in ascending order. Your iterator should yield elements in non-decreasing order while satisfying the following rules:

  1. Skip any element that exists in the blocked_ids set.
  2. Do not yield the same value consecutively (i.e., remove duplicates).
  3. Use O(K) extra space where K is the number of input iterators.

Interface

class FilteredMergeIterator:
    def __init__(self, iterators: List[Iterator[int]], blocked_ids: Set[int]):
        # Initialize the state

    def has_next(self) -> bool:
        # Returns true if there is a next element

    def next(self) -> int:
        # Returns the next valid element

Example

Input: iter1 = [1, 2, 4], iter2 = [2, 3, 5], blocked_ids = {3}

Output: 1, 2, 4, 5

Explanation:

  • 1 is taken from iter1.
  • 2 is taken from iter1 (duplicate 2 from iter2 is ignored).
  • 3 is skipped because it is in blocked_ids.
  • 4 is taken from iter1.
  • 5 is taken from iter2.

Constraints

  • Number of iterators: 1 <= K <= 1000
  • Elements: Integers within standard integer range.
  • Efficiency: The next() call should be efficient, ideally O(log K) using a heap.

Hints

Hint 1

Use a min-heap to keep track of the current head of each iterator to determine which value is the smallest.

Hint 2

When popping from the heap, check if the value is in `blocked_ids` before considering it for output.

Hint 3

Keep track of the 'last yielded value' as a member variable to ensure you don't yield the same value twice.

Follow-up questions

  • How would you modify your implementation if the input iterators were not sorted?
  • What changes are needed if the input iterators are very large and you need to minimize memory usage even further?
  • How would you handle a scenario where the `blocked_ids` set is so large that it does not fit into memory?