Sort trade executions into a canonical order
Company: Jane Street
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
You are building a small component in a trading system that consumes **trade execution records** from an upstream feed. The records may arrive out of order.
Each trade record has:
- `trade_id` (string, unique)
- `symbol` (string)
- `ts` (integer timestamp in milliseconds)
- `price` (integer, in ticks)
- `qty` (integer, > 0)
- `side` (`"B"` or `"S"`)
**Task**: Implement a function that takes an array of trade records and returns them sorted in a deterministic “canonical” order:
1. Increasing `ts`
2. If `ts` ties, increasing `symbol` (lexicographic)
3. If still tied, increasing `trade_id` (lexicographic)
**Input/Output**:
- Input: list of trade records
- Output: the same records sorted by the rule above
**Constraints** (assume):
- Up to 2e5 trades
- `trade_id` values are unique
- Sorting must be deterministic
**Follow-up** (optional): Describe how you would handle the case where `trade_id` is not guaranteed unique (duplicates/replays).
Quick Answer: This question evaluates a candidate's ability to enforce deterministic ordering and data normalization of time-series trade execution records, testing competencies in multi-key sorting, tie-breaking logic, and performance with large inputs.