Loadingone moment…
Sign in to run and submit your work
Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.
or
CODE WORKSPACE
Each worker writes its output sorted by timestamp, and the publish step needs one globally sorted file. The current implementation concatenates every shard and sorts, which works in the test fixture and fails on the cluster because the shards together are two hundred gigabytes.
Write merge_shards(shards, key_field, limit). Each shard is already sorted.
Function to write
merge_shards(shards: list[list[dict]], key_field: str, limit: int | None) -> list[dict]One globally sorted list of row copies, at most limit long, stable across and within shards.
How to approach it
Prime a heap with the head of each shard; every pop pushes that shard's next row.
Sample cases
+ 2 held back until you submit
four shards, one empty
Three shards interleave, three rows tie on the same timestamp, and one shard has nothing in it.
Input
Argument 1
[
[
{
'id': 'a1',
'ts': '09:00'
},
{
'id': 'a2',
'ts': '09:05'
},
{
'id': 'a3',
'ts': '09:30'
}
],
[
{
'id': 'b1',
'ts': '09:01'
},
{
'id': 'b2',
'ts': '09:05'
},
{
'id': 'b3',
'ts': '10:00'
}
],
[],
[
{
'id': 'c1',
'ts': '08:30'
},
{
'id': 'c2',
'ts': '09:05'
}
]
]Argument 2
'ts'Argument 3
None
Returns
| id | ts |
|---|---|
| c1 | 08:30 |
| a1 | 09:00 |
| b1 | 09:01 |
| a2 | 09:05 |
| b2 | 09:05 |
| c2 | 09:05 |
| a3 | 09:30 |
| b3 | 10:00 |
only the first few
A limit stops the merge early, which is the whole reason to merge rather than sort.
Input
Argument 1
[
[
{
'id': 'a1',
'ts': '09:00'
},
{
'id': 'a2',
'ts': '09:05'
},
{
'id': 'a3',
'ts': '09:30'
}
],
[
{
'id': 'b1',
'ts': '09:01'
},
{
'id': 'b2',
'ts': '09:05'
},
{
'id': 'b3',
'ts': '10:00'
}
],
[],
[
{
'id': 'c1',
'ts': '08:30'
},
{
'id': 'c2',
'ts': '09:05'
}
]
]Argument 2
'ts'Argument 3
3Returns
| id | ts |
|---|---|
| c1 | 08:30 |
| a1 | 09:00 |
| b1 | 09:01 |
no shards
Nothing to merge returns an empty list without touching the heap.
Input
Argument 1
[] (empty list)
Argument 2
'ts'Argument 3
None
Returns
[] (empty list)
Constraints
key_field, compared as text.limit caps the number of rows returned. None means no cap, and a limit of zero returns nothing.Worked example
Three rows share the timestamp 09:05 — one in each non-empty shard. They come out in shard order, so a2 before b2 before c2. Without the shard index in the comparison, Python would try to order the row dicts themselves to break the tie and raise a TypeError, which is a strange error to debug from a merge.
The limit is why this is a merge rather than a sort. Asking for the first 3 rows touches four rows in total — one per shard to prime the heap, then one more as each is consumed — where sorting first reads all eight and then discards five. On two hundred gigabytes that difference is the whole job.
What this tests
That sortedness is a resource. A heap of k entries turns k sorted streams into one with memory proportional to the number of shards rather than to the data, which is the same idea behind an external sort and a log-structured merge.
merge_shards(shards: list[list[dict]], key_field: str, limit: int | None) -> list[dict]Submit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.
This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.