Merge Hundreds of Paginated Sorted Sources into One Deduplicated Record Stream

You receive records from many independent data sources (hundreds, possibly more). Produce a single stream of records that is globally sorted and contains no duplicates, and emit it through a writer that accepts exactly one record per call. Each source can only be read through offset/limit pagination. Implement the merge against these interfaces: ```python from dataclasses import dataclass @dataclass class Record: id: int # sort key; two records with the same id are duplicates payload: str class Source: def fetch(self, offset: int, limit: int) -> list[Record]: """Return up to `limit` records starting at position `offset`.""" class RecordWriter: def write(self, record: Record) -> None: """Consume one record. Records must arrive in the final output order.""" def merge_sources(sources: list[Source], writer: RecordWriter, page_size: int) -> None: ... ``` ```hint Hold one candidate per source You only ever need to compare the smallest not-yet-written record of each source. Think about which structure returns the minimum of hundreds of candidates cheaply and how a source's candidate is replaced. ``` ```hint Know when a source is done Consider what a page shorter than the requested size tells you, and what you should do with that source afterward. ``` ### Constraints and Clarifications - Working assumption: every source returns its records in ascending `id` order, and ordering the output by `id` is the required global order. - The number of sources can be in the hundreds or more, and the total number of records can be far larger than memory, so the full result must not be accumulated before writing. - Duplicates can occur across sources and within one source. ### Clarifying Questions - Is every source already sorted by `id`, and is the output order defined only by `id`? - When two records share an `id` but carry different payloads, which one should be written? - Can a source return fewer than `limit` records before its end, for example because of a timeout, or does a short page always mean the source is exhausted? - Can a source change while it is being paginated, which would shift offsets? - How should the merge react when one source's fetch fails? ### What a Strong Answer Covers - A k-way merge driven by a min-heap keyed on each source's current record, with a correct tie-break so heap entries are always comparable. - Per-source buffering and on-demand page fetching, with exhaustion detected from a short page and the source removed from the heap. - Deduplication that works across and within sources without storing every id seen. - Memory bounded by the number of sources times the page size, plus time complexity in terms of total records and source count. - Handling of empty sources, fetch failures, and offsets that shift under concurrent writes. ### Follow-up Questions 1. With thousands of sources and slow network fetches, how would you prefetch pages so the writer is not blocked on one source at a time? 2. If the process crashes halfway through, what would you checkpoint so the merge can resume without writing duplicates or skipping records? 3. How would your design change if sources supported cursor-based pagination instead of offsets?