Katkat
Back

Merge K timestamped lists with timestamp coalescing

CitadelSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently merge multiple sorted streams of data and aggregate values associated with the same timestamp.

Problem Statement

You are given a list of K data streams. Each stream consists of a list of objects, where each object contains a timestamp and a value. Each individual stream is sorted by timestamp in ascending order. Within a stream, timestamps are unique.

Your task is to implement a function that merges these K streams into a single list, sorted by timestamp. If multiple streams contain the same timestamp, you must aggregate their values into a list for that timestamp.

Function Signature

def merge_streams(streams: list[list[dict]]) -> list[dict]:
    # streams is a list of lists: [[{'timestamp': 1, 'value': 'a'}, ...], [...]]
    # returns a list: [{'timestamp': 1, 'value': ['a', 'b']}, ...]

Constraints

  • K streams, total number of elements N across all streams.
  • Each stream is sorted by timestamp.
  • Memory should be managed efficiently, avoiding full concatenation followed by sorting.

Example

Input:

streams = [
    [{'timestamp': 1, 'value': 'A'}, {'timestamp': 3, 'value': 'B'}],
    [{'timestamp': 1, 'value': 'C'}, {'timestamp': 2, 'value': 'D'}]
]

Output:

[
    {'timestamp': 1, 'value': ['A', 'C']},
    {'timestamp': 2, 'value': ['D']},
    {'timestamp': 3, 'value': ['B']}
]

Edge Cases

  • Empty input list of streams.
  • Streams with different lengths.
  • No overlapping timestamps across streams.

Hints

Hint 1

Consider using a min-heap to keep track of the smallest current timestamp across all streams.

Hint 2

When popping from the heap, check if the timestamp matches the one just processed to decide whether to append to an existing entry or create a new one.

Hint 3

Ensure your heap stores the current index of the stream it came from so you can efficiently pull the next element from that specific stream.

Follow-up questions

  • What is the time complexity of your solution in terms of N and K?
  • How would your approach change if the streams were extremely large and couldn't fit into memory (e.g., provided as iterators)?
  • If you needed to maintain a rolling sum of values instead of a list of values, how would you update your data structures?