Design a Lazy Union Iterator for Sorted Inputs

Question

The question asks the candidate to design a Lazy Union Iterator that merges two sorted iterators into a single sorted iterator using lazy evaluation.

Codemia · Accepted Answer

The goal is to create a Lazy Union Iterator that takes two sorted iterators as input and merges them into a single sorted iterator. The iterator must implement two functions: **has_next()** to check if there are more elements and **next()** to return the next smallest element while advancing the respective underlying iterator.

The Lazy Union Iterator will maintain pointers to the current elements of both input iterators. The **has_next()** function will check if either iterator has more elements, while the **next()** function will compare the current elements from both iterators, return the smaller one, and advance the corresponding iterator. This approach ensures that we only access elements as needed, adhering to lazy evaluation.

Here’s a simple implementation in Python:

```python
class LazyUnionIterator:
    def __init__(self, iter1, iter2):
        self.iter1 = iter1
        self.iter2 = iter2
        self.current1 = next(iter1, None)
        self.current2 = next(iter2, None)

def has_next(self):
        return self.current1 is not None or self.current2 is not None

def next(self):
        if not self.has_next():
            raise StopIteration()
        if self.current1 is None:
            value = self.current2
            self.current2 = next(self.iter2, None)
        elif self.current2 is None:
            value = self.current1
            self.current1 = next(self.iter1, None)
        elif self.current1 < self.current2:
            value = self.current1
            self.current1 = next(self.iter1, None)
        else:
            value = self.current2
            self.current2 = next(self.iter2, None)
        return value
```
This implementation uses Python's built-in iterator functionality to manage the current elements.

This implementation efficiently merges two sorted iterators without loading all data into memory, making it suitable for large datasets. However, if we need to merge K sorted iterators, we can use a min-heap to keep track of the smallest elements across all iterators, which allows for efficient merging in O(N log K) time, where N is the total number of elements.

Design a Lazy Union Iterator for Sorted Inputs

MongoDB

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

MongoDB Software Engineer Interview Guide

Related Questions

Design a scalable Search System

Design a Video Streaming for Rippling

Design a Load Balancing Service

Design a Image Processing Service

Build a high-throughput Image Processing Pipeline