# The Priority Queue

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

Canonical URL: <https://datadriven.io/problems/the_priority_queue>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a list of dicts and an ordered list of key names, return the records sorted ascending by the first key, then by the second key for ties, and so on.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **multi-key sorting using tuple-based sort keys**. It checks whether candidates can construct composite sort criteria and apply them cleanly, a common pattern in reporting and query ordering.

---

### Break down the requirements

#### Step 1: Build a sort key from the ordered list of keys

For each record, extract a tuple of values corresponding to the key names in order.

#### Step 2: Sort using the composite key

Python's sort is stable and compares tuples element by element, so a tuple key naturally implements multi-key sorting.

#### Step 3: Return the sorted records

The sorted function returns a new list, leaving the original unchanged.

---

### The solution

**Tuple-based composite sort key**

```python
def multi_sort(records, keys):
    def sort_key(record):
        key_tuple = []
        for k in keys:
            key_tuple.append(record[k])
        return tuple(key_tuple)
    sorted_records = sorted(records, key=sort_key)
    return sorted_records
```

> **Time and Space Complexity**
>
> **Time:** O(n log n * k) where n is the number of records and k is the number of sort keys. Each comparison examines up to k fields.
> 
> **Space:** O(n) for the sorted output.

> **Interviewers Watch For**
>
> Do you use tuple comparison for multi-key sorting? This is the idiomatic Python approach. Candidates who write custom comparison functions (cmp_to_key) are overcomplicating it.

> **Common Pitfall**
>
> Sorting by each key sequentially in separate passes. While this works for ascending order (due to sort stability), it reverses the key priority. The first sort's order can be overwritten by the second.

---

## Common follow-up questions

- What if some keys needed descending order? _(Tests negating numeric values or using `cmp_to_key` for mixed directions.)_
- What if keys had different types (strings and numbers)? _(Tests that Python cannot compare str and int natively, requiring type-aware handling.)_
- How does this relate to SQL ORDER BY with multiple columns? _(Tests the parallel between tuple sort keys and SQL multi-column ordering.)_
- What if the record set were too large to sort in memory? _(Tests external sort algorithms.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_priority_queue)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.