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

Each line contains an order:

ORDER_ID SIDE PRICE QUANTITY TRADER_ID SYMBOL

Where:

ORDER_ID: Unique integer identifier (1 to 1M)
SIDE: BUY or SELL
PRICE: Integer price (1 to 10000)
QUANTITY: Integer shares (1 to 10000)
TRADER_ID: Trader identifier (1 to 1000)
SYMBOL: Stock symbol (e.g., AAPL, MSFT, etc.)

Output Format

Output exactly 5 lines to stdout:

MATCHED_ORDERS
UNMATCHED_ORDERS
PARTIAL_FILLS
AVG_LATENCY
TOTAL_TRADES

Where:

MATCHED_ORDERS: Number of fully matched orders (float, 6 decimal places)
UNMATCHED_ORDERS: Number of orders that received no fills (float, 6 decimal places)
PARTIAL_FILLS: Number of partially filled orders (float, 6 decimal places)
AVG_LATENCY: Average order processing latency (float, 6 decimal places)
TOTAL_TRADES: Total number of executed trades (integer, no decimals)

Example

Input

1 BUY 100 10 5 AAPL
2 SELL 100 5 7 AAPL
3 BUY 101 20 3 AAPL
4 SELL 99 15 1 AAPL
5 BUY 99 10 2 AAPL

Output

Line 1: 3 orders were fully matched. Line 2: 2 orders received no fills. Line 3: 1 order was partially filled. Line 4: Average processing latency. Line 5: Total executed trades (integer).

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