Order Matching Engine Challenge | Quant Interview Prep

Problem Description

Build a high-performance matching engine that processes 1,000,000 orders across ~500 symbols using price-time priority order books.

Your matching engine must:

Maintain separate order books per symbol
Match incoming orders using price-time priority
Execute partial fills when needed
Track matched, unmatched, and partially filled orders
Output 5 aggregate metrics: matched orders, unmatched orders, partial fills, average latency, and total trades

Tier System & Performance Targets

LANGUAGE	GOLD	SILVER	BRONZE
C++ / Rust	< 500ms	< 2000ms	< 10000ms
Java	< 1000ms	< 4000ms	< 15000ms
Python	< 5000ms	< 15000ms	< 60000ms

Evaluation Criteria

Correctness: Your program outputs 5 aggregate values. The first 4 (floats) are compared against the reference with a tolerance of 0.01. The 5th (integer) must match exactly. All 5 must be correct to pass.

Performance: Wall-clock time to process all 1M orders determines tier placement.

Input Format

One line per order: id SIDE qty price priority symbol
Where: id is a positive integer order id, SIDE is BUY or SELL, qty is the order quantity, price is an integer price (in price ticks), priority is a tie-breaker (lower is better), and symbol is the instrument ticker (e.g. AAPL).
Stream length: 1,000,000 orders across ~500 symbols and 1,000 traders in production. Test data is deterministic per seed.

Output Format & Sample

Sample input (first 8 lines, full file linked below):

1 BUY 3380 1973 4 PEP
2 BUY 3666 80 4 COP
3 SELL 495 52 3 ETSY
4 SELL 4598 71 2 CHK
5 SELL 1993 445 3 AMT
6 BUY 886 66 2 EXPR
7 SELL 355 26 2 BILL
8 SELL 2210 394 1 GOEV
... (more)

Expected output for that sample (first 8 lines):

↓ download full sample input | ↓ download expected output

Test your solution locally: ./your_solution < input.txt | diff - output.txt

Common Pitfalls

Maintain a separate book per symbol. All matching is price-time priority within a single symbol; cross-symbol matches don't exist.
Partial fills are required. An incoming BUY at 100 for 50 against a SELL at 100 for 80 matches 50; the SELL stays in the book with 30 left.
Best-bid > ask wins on the incoming side (a BUY at 105 vs an existing SELL at 100 trades at 100, the resting side's price).
Numbers can be large. Use 64-bit ints for cumulative quantities and notional. C++ int overflows at ~2.1B; cumulative qty across 1M orders blows past it.
Symbols are arbitrary strings. Don't assume a max length or fixed alphabet; use a hash map keyed by string.

Performance Tier Thresholds (applied by the grader)

Language	Gold	Silver	Bronze	Tier 4
C++	<500ms	<2000ms	<10000ms	else PASS
Rust	<500ms	<2000ms	<10000ms	else PASS
Java	<1000ms	<4000ms	<15000ms	else PASS
Python	<5000ms	<15000ms	<60000ms	else PASS

Submission Rules

Your program receives input via stdin
Output 5 lines to stdout (4 floats with 6 decimal places, then 1 integer)
Program must complete within 120 seconds
Memory usage must not exceed 1GB
Single-file solutions only
Java class must be named Solution

Starter Templates

C++

#include <cstdio>
#include <map>
#include <vector>
#include <string>
using namespace std;

struct Order {
    int order_id, price, qty, trader_id;
    string side, symbol;
};

int main() {
    // Per-symbol order books: buy_book[symbol] sorted desc by price, sell_book asc
    map<string, map<int, vector<Order>, greater<int>>> buy_book;
    map<string, map<int, vector<Order>>> sell_book;

    long long matched = 0, unmatched = 0, partial = 0, total_trades = 0;
    double total_latency = 0;
    int total_orders = 0;

    int oid, price, qty, tid;
    char side[8], symbol[16];

    while (scanf("%d %s %d %d %d %s", &oid, side, &price, &qty, &tid, symbol) == 6) {
        total_orders++;
        // Implement: match against opposite book using price-time priority
        // Track matched_orders, unmatched_orders, partial_fills, total_trades
    }

    double avg_lat = total_orders > 0 ? total_latency / total_orders : 0.0;
    printf("%.6f\n", (double)matched);
    printf("%.6f\n", (double)unmatched);
    printf("%.6f\n", (double)partial);
    printf("%.6f\n", avg_lat);
    printf("%lld\n", total_trades);
    return 0;
}

Python

import sys
from collections import defaultdict

buy_book = defaultdict(list)   # symbol -> [(price, order_id, qty, trader_id), ...] max-heap
sell_book = defaultdict(list)  # symbol -> [(price, order_id, qty, trader_id), ...] min-heap

matched = 0
unmatched = 0
partial = 0
total_trades = 0
total_latency = 0.0
total_orders = 0

for line in sys.stdin:
    parts = line.strip().split()
    if len(parts) != 6:
        continue
    oid, side, price, qty, tid, symbol = int(parts[0]), parts[1], int(parts[2]), int(parts[3]), int(parts[4]), parts[5]
    total_orders += 1

    # Implement: match against opposite book using price-time priority
    # Track matched, unmatched, partial, total_trades

avg_lat = total_latency / total_orders if total_orders > 0 else 0.0
print(f"{matched:.6f}")
print(f"{unmatched:.6f}")
print(f"{partial:.6f}")
print(f"{avg_lat:.6f}")
print(total_trades)

Rust

use std::io::{self, BufRead, Write, BufWriter};
use std::collections::HashMap;

fn main() {
    let stdin = io::stdin();
    let stdout = io::stdout();
    let mut out = BufWriter::new(stdout.lock());

    let mut matched: i64 = 0;
    let mut unmatched: i64 = 0;
    let mut partial: i64 = 0;
    let mut total_trades: i64 = 0;
    let mut total_latency: f64 = 0.0;
    let mut total_orders: i64 = 0;

    for line in stdin.lock().lines() {
        let line = line.unwrap();
        let parts: Vec<&str> = line.trim().split_whitespace().collect();
        if parts.len() != 6 { continue; }
        let _oid: i32 = parts[0].parse().unwrap();
        let side = parts[1];
        let price: i32 = parts[2].parse().unwrap();
        let qty: i32 = parts[3].parse().unwrap();
        let _tid: i32 = parts[4].parse().unwrap();
        let symbol = parts[5];
        total_orders += 1;

        // Implement: match against opposite book using price-time priority
    }

    let avg_lat = if total_orders > 0 { total_latency / total_orders as f64 } else { 0.0 };
    writeln!(out, "{:.6}", matched as f64).unwrap();
    writeln!(out, "{:.6}", unmatched as f64).unwrap();
    writeln!(out, "{:.6}", partial as f64).unwrap();
    writeln!(out, "{:.6}", avg_lat).unwrap();
    writeln!(out, "{}", total_trades).unwrap();
}

Java

import java.util.*;
import java.io.*;

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long matched = 0, unmatched = 0, partial = 0, totalTrades = 0;
        double totalLatency = 0.0;
        int totalOrders = 0;

        String line;
        while ((line = br.readLine()) != null) {
            String[] parts = line.trim().split("\\s+");
            if (parts.length != 6) continue;
            int oid = Integer.parseInt(parts[0]);
            String side = parts[1];
            int price = Integer.parseInt(parts[2]);
            int qty = Integer.parseInt(parts[3]);
            int tid = Integer.parseInt(parts[4]);
            String symbol = parts[5];
            totalOrders++;

            // Implement: match against opposite book using price-time priority
        }

        double avgLat = totalOrders > 0 ? totalLatency / totalOrders : 0.0;
        System.out.printf("%.6f%n", (double) matched);
        System.out.printf("%.6f%n", (double) unmatched);
        System.out.printf("%.6f%n", (double) partial);
        System.out.printf("%.6f%n", avgLat);
        System.out.printf("%d%n", totalTrades);
    }
}

Order Matching Engine