How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Jane Street.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Jane Street during technical interviews.

Sort trade executions into a canonical order | Jane Street Coding Question

Quick Overview

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.

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.

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

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'}]

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

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'}]

Expected 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

Python's sorting supports tuple keys, which is useful for multi-level ordering.
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

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'}]

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

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'}]

Expected 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

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

Loading coding console...