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

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.

Read the full Jane Street Software Engineer interview experience this question came from

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

  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

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

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

  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.

Community answers

Answer by aninhquangthang

#include using namespace std; class Solution { public: string __solve(const string& input) { struct Trade { long long ts; string symbol, trade_id, raw; }; vector trade_exec; for (size_t p = 0; (p = input.find('{', p)) != string::npos;) { size_t e = input.find('}', p); string cur = input.substr(p, e - p + 1); p = e + 1; auto str = & { size_t q = cur.find('"' + key + '"'); q = cur.find('"', cur.find(':', q)) + 1; return cur.substr(q, cur.find('"', q) - q); }; auto number = & { size_t q = cur.find('"' + key + '"'); q = cur.find(':', q) + 1; return stoll(cur.substr(q)); }; trade_exec.push_back({number("ts"), str("symbol"), str("trade_id"), cur}); } sort(trade_exec.begin(), trade_exec.end(), & { return tie(a.ts, a.symbol, a.trade_id) < tie(b.ts, b.symbol, b.trade_id); }); string answer = "["; for (size_t i = 0; i < trade_exec.size(); i++) { if (i) answer += ","; answer += trade_exec[i].raw; } return answer + "]"; } };

Answer by nguyenanhtien2005x

#include #include #include class Solution { public: // A trade record mixes strings and numbers, so no single C++ container can // hold one and the auto-marshaller has nothing to build. input is the JSON // array of trades; return the JSON array in the order the problem asks for. std::string __solve(const std::string& input) { // Write your solution here struct Trade { int ts; std::string symbol, trade_id, raw; }; std::vector trades; for (size_t l = input.find("{"); l != std::string::npos; l = input.find("{", l + 1)) { size_t r = input.find("}", l); Trade trade; trade.raw = input.substr(l, r - l + 1); auto stringVal = & -> std::string { size_t pos = input.find(key, l); pos += key.length() + 4; size_t fn = input.find("'", pos); return input.substr(pos, fn - pos); }; auto intVal = & -> int { size_t pos = input.find(key, l); pos += key.length() + 4; size_t fn = input.find(",", pos); return stoi(input.substr(pos, fn - pos)); }; trade.ts = intVal("ts"); trade.symbol = stringVal("symbol"); trade.trade_id = stringVal("trade_id"); trades.push_back(trade); } std::sort(trades.begin(), trades.end(), & { return tie(x.ts, x.symbol, x.trade_id) < tie(y.ts, y.symbol, y.trade_id); }); std::string result; for (Trade &trade : trades) { if (!result.empty()) { result += ","; } result += trade.raw; } return "[" + result + "]"; } };

Loading coding console...