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
You want the three biggest orders per region from a feed too large to hold. Bucketing by region and sorting each bucket works, and it holds every row of the busiest region in memory to throw almost all of them away.
Write top_n_per_key(rows, key_field, value_field, n) keeping at most n candidates per key at any moment.
Function to write
top_n_per_key(rows: list[dict], key_field: str, value_field: str, n: int) -> dictA dict from key to the ids of its top rows, best first, with keys in string order.
How to approach it
Work out how much the starter holds for a key with a million rows.
Sample cases
+ 2 held back until you submit
a tie on the boundary
Two rows share the top value, so the earlier one wins — and the unusable value is skipped.
Input
Argument 1
| id | g | v |
|---|---|---|
| a | x | 10 |
| b | x | 30 |
| c | x | 30 |
| d | y | 5 |
| e | x | NaN |
Argument 2
'g'Argument 3
'v'Argument 4
2Returns
{
'x': [
'b',
'c'
],
'y': [
'd'
]
}more asked for than exist
A key with fewer rows than n returns what it has, ordered, with no padding.
Input
Argument 1
| id | g | v |
|---|---|---|
| a | x | 10 |
| b | x | 30 |
| c | x | 30 |
| d | y | 5 |
| e | x | NaN |
Argument 2
'g'Argument 3
'v'Argument 4
9Returns
{
'x': [
'b',
'c',
'a'
],
'y': [
'd'
]
}no rows
An empty feed returns an empty mapping rather than keys with empty lists.
Input
Argument 1
[] (empty list)
Argument 2
'g'Argument 3
'v'Argument 4
2Returns
{}Constraints
{<key as a string>: [<ids, best first>]}.value_field descending. Where values tie, the row that appeared earlier in the feed wins.n candidates per key while scanning. That is the point of the exercise, not an optimisation on top of it.int or a float is skipped, and True is not a number — isinstance(True, int) is True in Python and a flag is not a measurement.n of 0 returns nothing for every key. A key with no usable rows does not appear at all.Worked example
In group x, rows b and c both have a value of 30 and a has 10. Asking for the top 2 must return b then c — b appeared first in the feed, so it wins the tie.
Row e has a value of the string NaN, which is skipped: comparing it with an integer raises TypeError and would take the whole key down. Encoding the tie-break as -index inside the heap entry is what makes the tie resolve the right way round, because a heap keeps its smallest entry at the top.
What this tests
That a heap is the bounded-memory answer to top-N, that a tie-break has to be part of the comparison rather than applied afterwards, and that a single unusable value in a comparison-based algorithm takes the whole group with it.
top_n_per_key(rows: list[dict], key_field: str, value_field: str, n: int) -> dictSubmit 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.