SimpleCross - a process that matches internal orders
Overview:
* Accept/remove orders as they are entered and keep a book of
resting orders
* Determine if an accepted order would be satisfied by previously
accepted orders (i.e. a buy would cross a resting sell)
* Output (print) crossing events and remove completed (fully filled)
orders from the book
Inputs:
A string of space separated values representing an action. The number of
values is determined by the action to be performed and have the following
format:
ACTION [OID [SYMBOL SIDE QTY PX]]
ACTION: single character value with the following definitions
O - place order, requires OID, SYMBOL, SIDE, QTY, PX
X - cancel order, requires OID
P - print sorted book (see example below)
OID: positive 32-bit integer value which must be unique for all orders
SYMBOL: alpha-numeric string value. Maximum length of 8.
SIDE: single character value with the following definitions
B - buy
S - sell
QTY: positive 16-bit integer value
PX: positive double precision value (7.5 format)
Outputs:
A list of strings of space separated values that show the result of the
action (if any). The number of values is determined by the result type and
have the following format:
RESULT OID [SYMBOL [SIDE] (FILL_QTY | OPEN_QTY) (FILL_PX | ORD_PX)]
RESULT: single character value with the following definitions
F - fill (or partial fill), requires OID, SYMBOL, FILL_QTY, FILL_PX
X - cancel confirmation, requires OID
P - book entry, requires OID, SYMBOL, SIDE, OPEN_QTY, ORD_PX (see example below)
E - error, requires OID. Remainder of line represents string value description of the error
FILL_QTY: positive 16-bit integer value representing qty of the order filled by
this crossing event
OPEN_QTY: positive 16-bit integer value representing qty of the order not yet filled
FILL_PX: positive double precision value representing price of the fill of this
order by this crossing event (7.5 format)
ORD_PX: positive double precision value representing original price of the order (7.5 format)
(7.5 format means up to 7 digits before the decimal and exactly 5 digits after the decimal)
Conditions/Assumptions:
* The implementation should be a standalone Linux console application (include
source files, testing tools and Makefile in submission)
* The use of third party libraries is not permitted.
* The app should respond to malformed input and other errors with a RESULT
of type 'E' and a descriptive error message
* Development should be production level quality. Design and
implementation choices should be documented
* Performance is always a concern in software, but understand that this is an unrealistic test.
Only be concerned about performance where it makes sense to the important sections of this application (i.e. reading actions.txt is not important).
* All orders are standard limit orders (a limit order means the order remains in the book until it
is either canceled, or fully filled by order(s) for its same symbol on the opposite side with an
equal or better price).
* Orders should be selected for crossing using price-time (FIFO) priority
* Orders for different symbols should not cross (i.e. the book must support multiple symbols)
Example session:
INPUT | OUTPUT
============================================================================
"O 10000 IBM B 10 100.00000" | results.size() == 0
"O 10001 IBM B 10 99.00000" | results.size() == 0
"O 10002 IBM S 5 101.00000" | results.size() == 0
"O 10003 IBM S 5 100.00000" | results.size() == 2
| results[0] == "F 10003 IBM 5 100.00000"
| results[1] == "F 10000 IBM 5 100.00000"
"O 10004 IBM S 5 100.00000" | results.size() == 2
| results[0] == "F 10004 IBM 5 100.00000"
| results[1] == "F 10000 IBM 5 100.00000"
"X 10002" | results.size() == 1
| results[0] == "X 10002"
"O 10005 IBM B 10 99.00000" | results.size() == 0
"O 10006 IBM B 10 100.00000" | results.size() == 0
"O 10007 IBM S 10 101.00000" | results.size() == 0
"O 10008 IBM S 10 102.00000" | results.size() == 0
"O 10008 IBM S 10 102.00000" | results.size() == 1
| results[0] == "E 10008 Duplicate order id"
"O 10009 IBM S 10 102.00000" | results.size() == 0
"P" | results.size() == 6
| results[0] == "P 10009 IBM S 10 102.00000"
| results[1] == "P 10008 IBM S 10 102.00000"
| results[2] == "P 10007 IBM S 10 101.00000"
| results[3] == "P 10006 IBM B 10 100.00000"
| results[4] == "P 10001 IBM B 10 99.00000"
| results[5] == "P 10005 IBM B 10 99.00000"
"O 10010 IBM B 13 102.00000" | results.size() == 4
| results[0] == "F 10010 IBM 10 101.00000"
| results[1] == "F 10007 IBM 10 101.00000"
| results[2] == "F 10010 IBM 3 102.00000"
| results[3] == "F 10008 IBM 3 102.00000"
So, for the example actions.txt, the desired output from the application with the below main is:
F 10003 IBM 5 100.00000
F 10000 IBM 5 100.00000
F 10004 IBM 5 100.00000
F 10000 IBM 5 100.00000
X 10002
E 10008 Duplicate order id
P 10009 IBM S 10 102.00000
P 10008 IBM S 10 102.00000
P 10007 IBM S 10 101.00000
P 10006 IBM B 10 100.00000
P 10001 IBM B 10 99.00000
P 10005 IBM B 10 99.00000
F 10010 IBM 10 101.00000
F 10007 IBM 10 101.00000
F 10010 IBM 3 102.00000
F 10008 IBM 3 102.00000
clang >= 14.0
Would have liked to use more C++20
features but compiler supports are a little painful for some new features
make all
./SimpleCross [file]
The matching engine is consisted of several parts
- A parser that parses inputs and errs on malformed inputs
- A global singleton logger that logs to output
- A orderbook that matches incoming orders
The orderbook consists of a MegaBook
that indexes each ticker symbol to their respective OrderBook
class with an
unordered_map
. It also holds a global hashtable of orders already seen. A brief overview of the OrderBook
class:
- Two BSTs (ask and bid) that maps from price to a list of orders (FIFO price level)
- Two
unordered_map
that maps from price to a pointer to list of orders (respective price levels) - A
unordered_map
that maps from order id to their respective iterators in the price level lists
Time complexity for actions
- Insert:
O(logn)
to travel down the BSTs. But this can be improved toO(1)
if the price level already exists - Cancel:
O(1)
to find the respective iterator and delete from list, and alsoO(logn)
to remove fromMegaBook
If the occurence of depleted price levels on cancel is small, then we can consider the cost to be very small as well. - Print:
O(n)
to print out every order
This is definitely not the most space efficient solution, since we need O(2n + m + k)
for bookkeeping (n
is the
number of orders, m
is the number of prices and k
is the number of symbols), and an additional O(m + k)
to store
the ask and bid trees. But it should be amply fast to process large number of orders if space is less of a concern.
Some thoughts for improvements:
- Make each price level a vector, might be better for cache locality
- Instead of hashing the ticker string each time, map it into a unique integer that use that to index into a vector that stores the bookkeeping
Testings
- Malformed inputs (test1.txt)
- No mactch (test2.txt)
- One quote partial match (test3.txt)
- One quote fully match (test4.txt)
- Multiple quotes fully match (test5.txt)
- Different symbols match (test6.txt)
- Duplicate and cancel order id test (test7.txt)
There is also a python fuzzer in generator.py
that generates random orders for stress testing.