Sort trade executions into a canonical order

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).

Part 1: Sort trade executions into canonical order

You are given a list of trade execution records from an upstream feed. The records may arrive out of order. Each trade record is a dictionary with the fields: trade_id (string, unique), symbol (string), ts (integer timestamp in milliseconds), price (integer), qty (integer), and side ("B" or "S"). Return the records sorted into a deterministic canonical order: first by increasing ts, then by increasing symbol lexicographically, and finally by increasing trade_id lexicographically.

Constraints

• 0 <= len(trades) <= 200000
• trade_id values are unique
• qty > 0 for every trade
• side is either "B" or "S"
• Timestamps and prices fit in standard integer ranges

Examples

Example 1

Input: [{'trade_id': 'T3', 'symbol': 'MSFT', 'ts': 1002, 'price': 330, 'qty': 5, 'side': 'S'}, {'trade_id': 'T1', 'symbol': 'AAPL', 'ts': 1000, 'price': 150, 'qty': 10, 'side': 'B'}, {'trade_id': 'T2', 'symbol': 'AAPL', 'ts': 1001, 'price': 151, 'qty': 3, 'side': 'S'}]
Output: [{'trade_id': 'T1', 'symbol': 'AAPL', 'ts': 1000, 'price': 150, 'qty': 10, 'side': 'B'}, {'trade_id': 'T2', 'symbol': 'AAPL', 'ts': 1001, 'price': 151, 'qty': 3, 'side': 'S'}, {'trade_id': 'T3', 'symbol': 'MSFT', 'ts': 1002, 'price': 330, 'qty': 5, 'side': 'S'}]

Explanation: The records are primarily ordered by timestamp: 1000, then 1001, then 1002.

Example 2

Input: [{'trade_id': 'T2', 'symbol': 'MSFT', 'ts': 1000, 'price': 330, 'qty': 2, 'side': 'B'}, {'trade_id': 'T1', 'symbol': 'AAPL', 'ts': 1000, 'price': 150, 'qty': 1, 'side': 'S'}, {'trade_id': 'T3', 'symbol': 'AAPL', 'ts': 1000, 'price': 151, 'qty': 1, 'side': 'B'}]
Output: [{'trade_id': 'T1', 'symbol': 'AAPL', 'ts': 1000, 'price': 150, 'qty': 1, 'side': 'S'}, {'trade_id': 'T3', 'symbol': 'AAPL', 'ts': 1000, 'price': 151, 'qty': 1, 'side': 'B'}, {'trade_id': 'T2', 'symbol': 'MSFT', 'ts': 1000, 'price': 330, 'qty': 2, 'side': 'B'}]

Explanation: All timestamps are equal, so sort by symbol. Within AAPL, sort by trade_id.

Hints

1. Python's sorting supports tuple keys, which is useful for multi-level ordering.
2. Only ts, symbol, and trade_id affect the order; the other fields should be carried along unchanged.

Part 2: Handle non-unique trade_id values (duplicates/replays)

In this version, the upstream feed may replay the same trade more than once, so trade_id is no longer guaranteed to be unique. Treat any later record with a trade_id that has already appeared as a duplicate replay and ignore it. Keep only the first occurrence of each trade_id, then return the remaining records in the same canonical order as Part 1: increasing ts, then increasing symbol, then increasing trade_id.

Constraints

• 0 <= len(trades) <= 200000
• qty > 0 for every trade
• side is either "B" or "S"
• Duplicate trade_id values should be treated as replays
• If multiple records share a trade_id, keep the first one from the input and ignore the rest

Examples

Example 1

Input: [{'trade_id': 'T2', 'symbol': 'AAPL', 'ts': 1001, 'price': 151, 'qty': 3, 'side': 'S'}, {'trade_id': 'T1', 'symbol': 'AAPL', 'ts': 1000, 'price': 150, 'qty': 10, 'side': 'B'}, {'trade_id': 'T2', 'symbol': 'AAPL', 'ts': 1001, 'price': 151, 'qty': 3, 'side': 'S'}, {'trade_id': 'T3', 'symbol': 'MSFT', 'ts': 1002, 'price': 330, 'qty': 5, 'side': 'S'}]
Output: [{'trade_id': 'T1', 'symbol': 'AAPL', 'ts': 1000, 'price': 150, 'qty': 10, 'side': 'B'}, {'trade_id': 'T2', 'symbol': 'AAPL', 'ts': 1001, 'price': 151, 'qty': 3, 'side': 'S'}, {'trade_id': 'T3', 'symbol': 'MSFT', 'ts': 1002, 'price': 330, 'qty': 5, 'side': 'S'}]

Explanation: The second T2 is a replay, so it is ignored. Then the remaining trades are sorted canonically.

Example 2

Input: [{'trade_id': 'T1', 'symbol': 'MSFT', 'ts': 1005, 'price': 330, 'qty': 4, 'side': 'B'}, {'trade_id': 'T2', 'symbol': 'AAPL', 'ts': 1000, 'price': 150, 'qty': 1, 'side': 'S'}, {'trade_id': 'T1', 'symbol': 'AAPL', 'ts': 999, 'price': 100, 'qty': 9, 'side': 'S'}, {'trade_id': 'T3', 'symbol': 'GOOG', 'ts': 1001, 'price': 2800, 'qty': 2, 'side': 'B'}]
Output: [{'trade_id': 'T2', 'symbol': 'AAPL', 'ts': 1000, 'price': 150, 'qty': 1, 'side': 'S'}, {'trade_id': 'T3', 'symbol': 'GOOG', 'ts': 1001, 'price': 2800, 'qty': 2, 'side': 'B'}, {'trade_id': 'T1', 'symbol': 'MSFT', 'ts': 1005, 'price': 330, 'qty': 4, 'side': 'B'}]

Explanation: Even though the later T1 has different contents, it is still treated as a replay. Keep the first T1 only.

Hints

1. Scan the input once and remember which trade_id values you have already seen.
2. After filtering replays, you can reuse the same sorting rule as in Part 1.