Merge K sorted log files lazily

Python data engineering interview problem. Difficulty: intermediate. Pattern: Heaps. About 16 minutes. Part of the Pro drill bank.

Merge multiple sorted log streams into a single generator yielding items in timestamp order. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

Implement merge_k_logs(streams: list) as a generator that accepts streams, where each stream is an iterable yielding (timestamp, message) tuples in ascending timestamp order. Yield tuples (timestamp, message) merged in overall ascending timestamp order. The solution must be lazy: do not load all stream elements into a single list at once. Streams may have different lengths and may run out at different times.

Requirements

  • Operate lazily using iterators and generator yielding.
  • Output must be strictly ascending by timestamp.

Constraints

  • 0 <= len(streams) <= 100
  • Each stream yields (int, str) tuples sorted by timestamp.

Examples

Input: list(merge_k_logs([[(10, 'start'), (30, 'error')], [(20, 'login'), (40, 'logout')]])) Output: [(10, 'start'), (20, 'login'), (30, 'error'), (40, 'logout')] The two streams are interleaved by timestamp in order.

Topics: lakebench, python, priority-queue, generators.

More Python interview questions · All interview problems · Learn data engineering

intermediate

Merge K sorted log files lazily

Interview-style drill: Merge multiple sorted log streams into a single generator yielding items in timestamp order.

Implement `merge_k_logs(streams: list)` as a generator that accepts `streams`, where each stream is an iterable yielding `(timestamp, message)` tuples in ascending timestamp order. - Yield tuples `(timestamp, message)` merged in overall ascending timestamp order. - The solution must be lazy: do not load all stream elements into a single list at once. - Streams may have different lengths and may run out at different times.