Code RoomExternal sort run lengths
HardPrep Room Coding #4874

External sort run lengths

CodingAlgorithms & data structuresSenior–Staff~38 min

A log compactor sorts a file far larger than memory by writing sorted runs to disk first. It holds memory_slots records at a time. It fills memory from the front of records, then repeatedly writes out the smallest record in memory that is not below the last record it wrote in the current run, and every write is followed at once by reading the next unread record into the slot that just freed. When memory holds nothing that qualifies, the run is closed, a new one opens, and every held record becomes eligible again. Records are integers and may repeat. Return the length of each run in the order the runs are written. Return an empty list for no records or for memory_slots below 1.

Implement
spill_run_lengths(records: list[int], memory_slots: int) → list[int]
Examples
in[[5,1,9,3,7,2,8],3]out[6,1]
in[[4,3,2,1],2]out[2,2]
in[[1,2,3,4,5,6],2]out[6]
What a strong answer looks like

State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.

0:00 of about 38 min
InputExpectedGot
[[5,1,9,3,7,2,8],3][6,1]not run yetsample
[[4,3,2,1],2][2,2]not run yetsample
[[1,2,3,4,5,6],2][6]not run yetsample