Katkat
Back

Sort trade executions into a canonical order

Jane StreetSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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