030. Sort Records by Multiple Keys

Interview · Download this solution · All solutions and shared helpers

Problem

Given records represented as (name, score, timestamp) tuples, return a new list sorted by ascending integer score and descending integer timestamp within equal scores. For ties on both keys, preserve original input order. Names are payload and do not affect ordering.

Examples

Example 1

sort_records([("A", 2, 10), ("B", 1, 5), ("C", 2, 20)])
=> [('B', 1, 5), ('C', 2, 20), ('A', 2, 10)]

Score dominates; timestamp resolves the score tie.

Example 2

sort_records([])
=> []

The empty list remains empty.

Example 3

sort_records([("Z", 1, 2), ("A", 1, 2)])
=> [('Z', 1, 2), ('A', 1, 2)]

Names do not break complete-key ties.

Reveal the worked solution and reasoning

Why this mechanism works

A tuple key expresses priority: Python compares the score first, then the negated timestamp. Negation converts descending numeric order into ascending key order. Python's stable sort handles complete-key ties without adding an unintended name-based tie breaker.

State and boundaries

Each record has key (score,-timestamp). Stability preserves relative order for equal keys.

Protocol

Define the two-field key.
Sort records by that key.
Retain the original records as output payload.

Visualization

record (A,2,10) -> key (2,-10)
record (B,1, 5) -> key (1, -5)
record (C,2,20) -> key (2,-20)
order: B, C, A

Python implementation

def sort_records(records):
    return sorted(records, key=lambda record: (record[1], -record[2]))

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

sort_records([("A", 2, 10), ("B", 1, 5), ("C", 2, 20)])

L2 <lambda>: return sorted(records, key=lambda record: (record[1], -record[2]))
record=('A', 2, 10)

L2 <lambda>: return sorted(records, key=lambda record: (record[1], -record[2]))
record=('B', 1, 5)

L2 <lambda>: return sorted(records, key=lambda record: (record[1], -record[2]))
record=('C', 2, 20)

L2 sort_records: return sorted(records, key=lambda record: (record[1], -record[2]))
records=[('A', 2, 10), ('B', 1, 5), ('C', 2, 20)]

Result: [('B', 1, 5), ('C', 2, 20), ('A', 2, 10)]. Score dominates; timestamp resolves the score tie.

sort_records([])

L2 sort_records: return sorted(records, key=lambda record: (record[1], -record[2]))
records=[]

Result: []. The empty list remains empty.

Why the solution is correct

Lexicographic key comparison orders smaller scores first. Equal scores compare negative timestamps, placing larger original timestamps first. Stability leaves complete-key ties in input order, satisfying all three ordering requirements.

Time and space

O(n log n) time and O(n) additional storage for the sorted result and sorting workspace.

Common mistakes

Setting reverse=True reverses the primary score too. Including name in the key silently changes the complete-tie rule.

Reasoning card

State: Each record has key (score,-timestamp). Stability preserves relative order for equal keys.

Invariant: The sort key totally determines required ordering.

Decision to rehearse: Build a complete key whose tuple order matches the specification.

Finish: Retain the original records as output payload

Transfer exercise

Sort timestamps represented by comparable objects that cannot be negated. Use stable sorting passes in the correct order.