Merge Sorted Arrays, Then Scale to Huge Files and a Global Sort of N Files

Start with an easy coding task: merge two sorted sequences of integers into one sorted sequence. The interviewer then scales the same task up twice, and those follow-ups are about external-memory and distributed processing rather than about the merge loop itself: first the two inputs are huge files that do not fit in memory, and the output does not fit either; then there are N such files that must be sorted globally and stored. ### Constraints and Clarifications - Duplicates are kept: an integer that appears three times across the inputs appears three times in the output. - In Parts 2 and 3, "does not fit in memory" applies to every input and to the output. You may assume enough disk space for the output plus temporary files unless you say otherwise. - Pseudocode is acceptable for Parts 2 and 3 if the I/O behaviour is clear. ### Clarifying Questions - What is the record format in the files (one integer per text line, fixed-width binary records, or key-value lines), and which field is the sort key? - In Part 3, is each of the N files already sorted, or can they be in any order? - Is Part 3 on one machine, or can the work be spread over a cluster? Where must the result live (local disk, a distributed file system, object storage)? - Must records with equal keys keep a particular relative order? - Roughly how large are N, a single file, and available memory? ### Part 1 — Merge two sorted arrays Implement: ```python def merge_sorted(a: list[int], b: list[int]) -> list[int]: ``` Both inputs are sorted in non-decreasing order. Return one list, sorted in non-decreasing order, containing every element of both inputs. For example, `a = [1, 3, 5, 5]` and `b = [2, 5, 6]` give `[1, 2, 3, 5, 5, 5, 6]`. ```hint Handle the boundaries Decide what happens when the two current elements are equal, and what happens once one input runs out. ``` #### What This Part Should Cover - A linear-time merge with correct handling of ties, empty inputs and leftover elements - Time and space complexity ### Part 2 — Two sorted files that do not fit in memory The two inputs are now very large sorted files on disk, and the merged output is too large to hold in memory as well. Describe, and sketch in code, how you produce the merged output file. State how much memory you use, how many times each byte is read and written, and what happens if the process dies halfway through. ```hint What must be resident Ask how much of each input the merge actually needs in memory at any moment, and what that means for how you read and write. ``` #### What This Part Should Cover - Streaming reads and writes with bounded memory - Buffer sizing and the I/O access pattern - Crash safety of the output and checks on the inputs ### Part 3 — Globally sorting and storing N large files There are now N large files. How do you produce a globally sorted result, and how do you store it so that it is useful to whoever reads it next? ```hint Split the problem by scale Treat one machine and many machines separately; with many machines, the key question is how to decide which machine owns which records. ``` #### Clarifying Questions for this Part - Will readers scan the whole result in order, or mostly look up individual keys or key ranges? - Does the output have to be one physical file, or is an ordered set of files acceptable? #### What This Part Should Cover - Combining many sorted inputs efficiently, and producing sorted runs when inputs are unsorted - The number of passes and total I/O as data grows relative to memory - A distributed approach that keeps partitions balanced - An output layout and metadata that make the result readable and verifiable ### What a Strong Answer Covers - A correct two-pointer merge with ties, empty inputs and tails handled - Bounded-memory streaming with sequential I/O and sensible buffering - The multi-way merge and external sort cost model (comparisons, passes, bytes moved) - Range partitioning across machines, including how split points are chosen and how skew is handled - Failure handling: atomic outputs, restartable work, and validation that inputs are actually sorted ### Follow-up Questions - One key accounts for a third of all records. What happens to your partitioning in Part 3, and how do you fix it? - While merging, keep only the newest version of each key (records carry a version number). What changes? - A worker crashes after producing half of its partition. How do you resume without redoing or duplicating work? - Readers mostly request key ranges. What index would you store next to the sorted output, and how big is it?