PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates competency in designing and implementing event-driven simulators, priority-based matching algorithms, and quota-constrained allocation for a limit order book, participation-rate execution, and multi-client fair-share distribution in the Coding & Algorithms domain.

  • nan
  • Voleon
  • Coding & Algorithms
  • Software Engineer

Simulate an exchange and participation-rate trading

Company: Voleon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: nan

Interview Round: Technical Screen

Implement a simplified trading simulation in **three parts**. ## Part 1 — Process market data / exchange interaction (order book) Design a minimal limit-order-book simulator for a **single symbol**. ### Events Each event is one of: - `NEW orderId side price qty` - `side` is `B` (buy) or `S` (sell) - Add a limit order. - `CANCEL orderId` - Remove the remaining quantity of that order (if it exists). ### Matching rules When a new order arrives, immediately match it against resting orders on the opposite side using: 1. **Price priority**: best price first (highest buy, lowest sell). 2. **Time priority**: FIFO among orders at the same price. A match produces one or more trades. A trade is: - `tradePrice` = resting order’s price - `tradeQty` = min(incomingRemaining, restingRemaining) ### Output For every input event, output the list of trades generated by that event (may be empty). --- ## Part 2 — Execute for one client with participation rate A single client submits a parent order: - `clientId`, `side`, total target quantity `Q`, and participation rate `p` (0 < p <= 1). You also receive a time-ordered stream of **market prints** (executed market volume): - `PRINT t marketQty` At each print, you may execute some quantity for the client, but must satisfy at all times: \[ executedSoFar \le \lfloor p \cdot marketVolumeSoFar \rfloor \] Where `marketVolumeSoFar` is the cumulative sum of `marketQty` from prints up to time `t`. ### Output For each print, output how many shares you execute for the client at that time (0 if none), until the client reaches `Q` or prints end. --- ## Part 3 — Multiple clients and fairness Now there are multiple simultaneous clients, each with `(Q_i, p_i)`. At each `PRINT`, compute executions for all clients such that: 1. For every client `i`: `executed_i <= floor(p_i * marketVolumeSoFar)`. 2. No client executes more than its remaining quantity. 3. Total executed at a print does not exceed that print’s `marketQty`. 4. If there isn’t enough available volume to satisfy everyone’s allowed amount, allocate **fairly** by prioritizing the client(s) with the smallest \[ \frac{executed_i}{Q_i} \] ties broken by smaller `clientId`. ### Task Implement the simulator for all three parts. ### Notes - You may assume all inputs are validly formatted. - You should state and handle edge cases like canceling unknown orders, or `p_i * marketVolumeSoFar` allowing more than remaining.

Quick Answer: This question evaluates competency in designing and implementing event-driven simulators, priority-based matching algorithms, and quota-constrained allocation for a limit order book, participation-rate execution, and multi-client fair-share distribution in the Coding & Algorithms domain.

Part 1: Single-Symbol Limit Order Book

Implement a minimal limit-order-book simulator for one symbol. Each event is either NEW orderId side price qty or CANCEL orderId. NEW adds a limit order after immediately matching it against resting orders on the opposite side. Matching uses price priority first, then FIFO time priority at the same price. A trade price is always the resting order price, and trade quantity is min of incoming remaining quantity and resting remaining quantity. CANCEL removes the remaining quantity of the order if it is still resting; canceling an unknown or already-filled order does nothing.

Constraints

  • 0 <= len(events) <= 100000
  • 1 <= price, qty <= 1000000000
  • orderId contains no whitespace
  • A NEW orderId will not duplicate an orderId that is currently resting
  • CANCEL for an unknown, canceled, or fully-filled order must be ignored
  • The total number of generated trades fits in memory

Examples

Input: ([],)

Expected Output: []

Explanation: No events means no per-event trade lists.

Input: (['NEW b1 B 100 10', 'NEW s1 S 99 4', 'NEW s2 S 100 10', 'NEW b2 B 101 5', 'CANCEL b2'],)

Expected Output: [[], [[100, 4]], [[100, 6]], [[100, 4]], []]

Explanation: Incoming sells trade at resting buy price 100. The final buy fills the remaining resting sell at price 100, then its remaining 1 share is canceled.

Input: (['NEW b1 B 100 5', 'NEW b2 B 100 7', 'NEW s1 S 100 10', 'NEW s2 S 100 2'],)

Expected Output: [[], [], [[100, 5], [100, 5]], [[100, 2]]]

Explanation: b1 and b2 have the same price, so b1 is filled first by FIFO time priority.

Input: (['NEW s1 S 101 5', 'NEW s2 S 100 4', 'NEW s3 S 100 3', 'NEW b1 B 102 7', 'NEW b2 B 101 5'],)

Expected Output: [[], [], [], [[100, 4], [100, 3]], [[101, 5]]]

Explanation: The buy at 102 trades against the lowest sell price 100 first, using FIFO within that price, before any sell at 101.

Input: (['NEW b1 B 100 10', 'CANCEL missing', 'CANCEL b1', 'NEW s1 S 99 5', 'NEW b2 B 100 3'],)

Expected Output: [[], [], [], [], [[99, 3]]]

Explanation: Canceling an unknown order is ignored. The canceled buy b1 is not available to match s1.

Solution

def solution(events):
    from collections import defaultdict, deque
    import heapq

    buy_heap = []
    sell_heap = []
    buy_levels = defaultdict(deque)
    sell_levels = defaultdict(deque)
    orders = {}
    result = []

    def clean_top(side):
        if side == 'B':
            heap = buy_heap
            levels = buy_levels
            while heap:
                price = -heap[0]
                dq = levels[price]
                while dq and dq[0] not in orders:
                    dq.popleft()
                if dq:
                    return price
                heapq.heappop(heap)
                if price in levels and not levels[price]:
                    del levels[price]
            return None
        else:
            heap = sell_heap
            levels = sell_levels
            while heap:
                price = heap[0]
                dq = levels[price]
                while dq and dq[0] not in orders:
                    dq.popleft()
                if dq:
                    return price
                heapq.heappop(heap)
                if price in levels and not levels[price]:
                    del levels[price]
            return None

    for event in events:
        parts = event.split()
        trades = []

        if parts[0] == 'CANCEL':
            order_id = parts[1]
            if order_id in orders:
                del orders[order_id]
            result.append(trades)
            continue

        order_id = parts[1]
        side = parts[2]
        price = int(parts[3])
        remaining = int(parts[4])

        if side == 'B':
            while remaining > 0:
                best_sell = clean_top('S')
                if best_sell is None or best_sell > price:
                    break

                dq = sell_levels[best_sell]
                resting_id = dq[0]
                resting_side, resting_price, resting_qty = orders[resting_id]
                trade_qty = min(remaining, resting_qty)
                trades.append([resting_price, trade_qty])

                remaining -= trade_qty
                resting_qty -= trade_qty
                if resting_qty == 0:
                    del orders[resting_id]
                    dq.popleft()
                else:
                    orders[resting_id] = [resting_side, resting_price, resting_qty]

            if remaining > 0:
                orders[order_id] = [side, price, remaining]
                if not buy_levels[price]:
                    heapq.heappush(buy_heap, -price)
                buy_levels[price].append(order_id)

        else:
            while remaining > 0:
                best_buy = clean_top('B')
                if best_buy is None or best_buy < price:
                    break

                dq = buy_levels[best_buy]
                resting_id = dq[0]
                resting_side, resting_price, resting_qty = orders[resting_id]
                trade_qty = min(remaining, resting_qty)
                trades.append([resting_price, trade_qty])

                remaining -= trade_qty
                resting_qty -= trade_qty
                if resting_qty == 0:
                    del orders[resting_id]
                    dq.popleft()
                else:
                    orders[resting_id] = [resting_side, resting_price, resting_qty]

            if remaining > 0:
                orders[order_id] = [side, price, remaining]
                if not sell_levels[price]:
                    heapq.heappush(sell_heap, price)
                sell_levels[price].append(order_id)

        result.append(trades)

    return result

Time complexity: O((E + T + C) log P) amortized, where E is the number of events, T is the number of trades, C is the number of canceled orders skipped by lazy deletion, and P is the number of distinct active price levels.. Space complexity: O(A + T), where A is the number of resting orders and T is the number of returned trades..

Hints

  1. Maintain one price-priority structure for buys and one for sells, plus FIFO queues for order ids at each price.
  2. For cancellation, lazy deletion is simpler: remove the order id from an active-order map and skip inactive ids when they reach the front of a price queue.

Part 2: Single-Client Participation Rate Executor

A single client submits a parent order with client id, side, target quantity Q, and participation rate p. You receive a time-ordered stream of market prints, each giving market volume at that time. After each print, you should execute as much as possible for the client while always maintaining executedSoFar <= floor(p * marketVolumeSoFar), and without exceeding the target quantity Q.

Constraints

  • 0 <= len(prints) <= 100000
  • 0 <= target_qty <= 1000000000
  • 0 <= marketQty <= 1000000000
  • 0 < participation_rate <= 1
  • prints are already sorted by time
  • participation_rate has at most 6 decimal places if given as a decimal

Examples

Input: ('C1', 'B', 100, 0.1, [[1, 50], [2, 70], [3, 500], [4, 100]])

Expected Output: [5, 7, 50, 10]

Explanation: The cumulative caps are 5, 12, 62, and 72, so each print executes the increase in the cap.

Input: ('C1', 'S', 10, 0.5, [[1, 5], [2, 10], [3, 100], [4, 100]])

Expected Output: [2, 5, 3, 0]

Explanation: The target of 10 is reached at the third print, so the fourth print executes 0.

Input: ('C2', 'B', 5, 0.25, [[1, 1], [2, 2], [3, 1], [4, 20]])

Expected Output: [0, 0, 1, 4]

Explanation: Flooring matters: cumulative volumes 1 and 3 allow 0 shares at 25 percent.

Input: ('C3', 'B', 100, 0.2, [])

Expected Output: []

Explanation: With no prints, there are no execution decisions.

Input: ('C4', 'S', 3, 1.0, [[1, 0], [2, 2], [3, 2]])

Expected Output: [0, 2, 1]

Explanation: At a 100 percent participation rate, the client can follow cumulative market volume, but still cannot exceed the target.

Solution

def solution(client_id, side, target_qty, participation_rate, prints):
    from fractions import Fraction

    rate = Fraction(str(participation_rate))
    market_volume = 0
    executed = 0
    answer = []

    for _, market_qty in prints:
        market_volume += market_qty
        cap = (rate.numerator * market_volume) // rate.denominator
        allowed_now = cap - executed
        if allowed_now < 0:
            allowed_now = 0

        qty = min(target_qty - executed, allowed_now)
        if qty < 0:
            qty = 0

        executed += qty
        answer.append(qty)

    return answer

Time complexity: O(N), where N is the number of prints.. Space complexity: O(N) for the returned list, and O(1) auxiliary space..

Hints

  1. Keep cumulative market volume and cumulative client execution.
  2. At a print, the maximum cumulative client execution is floor(p times cumulative market volume); the new execution is the gap between that cap and what has already been executed, limited by remaining target quantity.

Part 3: Multi-Client Fair Participation Allocator

Multiple clients are active at the same time. Client i has a clientId, target quantity Q_i, and participation rate p_i. At every market print, compute executions for all clients while respecting each client's cumulative cap floor(p_i * marketVolumeSoFar), each client's remaining quantity, and the rule that total execution at that print cannot exceed that print's marketQty. If the print does not have enough volume to satisfy every client's newly allowed quantity, allocate shares fairly by repeatedly choosing the client with the smallest executed_i / Q_i ratio, breaking ties by smaller clientId.

Constraints

  • 0 <= len(clients) <= 100
  • 0 <= len(prints) <= 1000
  • clientId values are unique integers
  • 1 <= targetQty <= 1000000000 for each client
  • 0 <= marketQty and sum of all marketQty values <= 200000
  • 0 < participationRate <= 1
  • participationRate has at most 6 decimal places if given as a decimal

Examples

Input: ([[1, 100, 0.1], [2, 50, 0.2]], [[1, 10], [2, 40]])

Expected Output: [[[1, 1], [2, 2]], [[1, 4], [2, 8]]]

Explanation: At both prints, marketQty is enough to give every client their newly allowed quantity.

Input: ([[1, 10, 1.0], [2, 10, 1.0]], [[1, 3], [2, 1]])

Expected Output: [[[1, 2], [2, 1]], [[1, 0], [2, 1]]]

Explanation: At the first print, ratios start tied, so client 1 gets the first share, client 2 gets the second, and client 1 gets the third. At the next print, client 2 has the lower completion ratio.

Input: ([[1, 100, 1.0], [2, 10, 1.0]], [[1, 5]])

Expected Output: [[[1, 4], [2, 1]]]

Explanation: After one share each, client 1 has a much smaller executed/Q ratio because its target is larger, so it receives the remaining scarce shares.

Input: ([[1, 5, 0.5], [2, 100, 0.5]], [[1, 4], [2, 100]])

Expected Output: [[[1, 2], [2, 2]], [[1, 3], [2, 50]]]

Explanation: Client 1's cumulative cap eventually exceeds its remaining quantity, so it receives only the 3 shares needed to finish.

Input: ([], [[1, 10], [2, 0]])

Expected Output: [[], []]

Explanation: With no clients, each print has an empty allocation list.

Solution

def solution(clients, prints):
    from fractions import Fraction
    import heapq

    clients_sorted = sorted(clients, key=lambda row: row[0])
    n = len(clients_sorted)
    ids = []
    targets = []
    rates = []

    for client_id, target_qty, participation_rate in clients_sorted:
        ids.append(client_id)
        targets.append(target_qty)
        rates.append(Fraction(str(participation_rate)))

    executed = [0] * n
    market_volume = 0
    answer = []

    for _, market_qty in prints:
        market_volume += market_qty
        allowed = [0] * n
        total_allowed = 0

        for i in range(n):
            cap = (rates[i].numerator * market_volume) // rates[i].denominator
            if cap > targets[i]:
                cap = targets[i]
            add = cap - executed[i]
            if add < 0:
                add = 0
            allowed[i] = add
            total_allowed += add

        take = [0] * n

        if total_allowed <= market_qty:
            for i in range(n):
                take[i] = allowed[i]
                executed[i] += allowed[i]
        else:
            heap = []
            for i in range(n):
                if allowed[i] > 0:
                    heapq.heappush(heap, (Fraction(executed[i], targets[i]), ids[i], i))

            remaining_volume = market_qty
            while remaining_volume > 0 and heap:
                _, _, i = heapq.heappop(heap)
                take[i] += 1
                executed[i] += 1
                allowed[i] -= 1
                remaining_volume -= 1

                if allowed[i] > 0:
                    heapq.heappush(heap, (Fraction(executed[i], targets[i]), ids[i], i))

        answer.append([[ids[i], take[i]] for i in range(n)])

    return answer

Time complexity: O(P * C + A log C), where P is the number of prints, C is the number of clients, and A is the number of one-share allocations performed during volume-constrained prints. A is at most the total market volume.. Space complexity: O(P * C) for the returned allocations and O(C) auxiliary space..

Hints

  1. For each print, first compute each client's newly allowed additional quantity from its cumulative cap minus what it has already executed.
  2. When volume is scarce, a min-heap keyed by executed_i / Q_i and then clientId simulates the fair one-share-at-a-time allocation.
Last updated: Jun 13, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Solve classic coding interview problems - Voleon (hard)
  • Count White Balls After K Steps - Voleon (hard)
  • Implement sparse matrix addition and multiplication - Voleon (nan)
  • Count queen attacks on points with blockers - Voleon (nan)
  • Validate whether a binary string is good - Voleon (nan)