The Priority Queue

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4

Problem

You're putting an HR export into a stable reporting order: a list of records, each a dict carrying the same fields, plus an ordered list of field names keys. Return a new list sorted ascending by the first key, breaking ties with the next key, and so on down the list.

When two things tie, something has to break the deadlock.

Example 1

Input:

records = [{"dept":"eng","score":90},{"dept":"eng","score":80},{"dept":"hr","score":85}], keys = ["dept","score"]

Output:

[{"dept":"eng","score":80},{"dept":"eng","score":90},{"dept":"hr","score":85}]

Example 2

Input:

records = [{"name":"Mia","level":3},{"name":"Ada","level":3}], keys = ["name"]

Output:

[{"name":"Ada","level":3},{"name":"Mia","level":3}]

Worked solution and explanation

What this really is

Strip the costume and this is sort by several columns at once, the same thing SQL's ORDER BY a, b, c does. Everyone reaches for a sort; what separates people is HOW they combine the keys. The trap is sorting in a loop, one key per pass: get that wrong and the priority inverts, because the LAST pass wins, so you'd actually have to walk the keys in reverse for it to even work, and most candidates don't. The clean move is one sort with a single composite key: a tuple of the values in key order. Python compares tuples left to right, so the first key dominates and a later key only matters when everything before it ties, which is exactly the requirement.

Sequential passes (fragile)
Sort by key[0], then sort again by key[1]. The second sort reorders everything by key[1], and only stability keeps key[0] as the tie-breaker. To get the intended priority you must sort the keys in REVERSE order, which is exactly the detail people forget.
One composite key (correct)
Build a tuple per record and sort once. The first element dominates, the rest break ties in order. The priority is explicit in the tuple and there is no ordering-of-passes gotcha to get wrong.

Building it

Step 1: Turn the key list into a value tuple per record

For a record, pull record[k] for each k in keys, in order, into a tuple. That single object encodes the full ranking rule for that record.

Step 2: Hand the tuple to sorted as the key function

sorted is stable and compares the tuple keys element by element, so the composite key gives ascending multi-key order without any extra work.

Step 3: Return the new list

sorted produces a fresh list and leaves records untouched, which is what the caller of a reporting helper expects.

Composite tuple sort key
def sort_by_multiple_keys(records, keys):
    return sorted(records, key=lambda record: tuple(record[k] for k in keys))

One pass, one key function. The tuple carries the whole priority order.

Common follow-up questions