On Sunday, April 23rd, around 0830 EDT, I started a coding test as a part of an application to Vatic Labs.
As far as I can tell, having read everything pretty carefully and thoroughly, I have made no agreement to not discuss or publish the problem. I am repeating the problem here for the purposes of saving it to my training regimen.
This shall be the first of many, I hope.
There will be no commentary in this post, but future commentary on this problem will refer to this post.
Your program will analyze quotes and trades and output paired trades. A quotes file describes the prices of several stocks over time, and a trades file lists the inidividual transcations a hypothetical trading firm makes in those stocks.
The quotes file contains:
Each line represents a quote update (i.e., BID and ASK prices) of the given SYMBOL, and is effective from the given TIME until there is another update for the same SYMBOL. In the above example, the BID and ASK of 10.05 and 10.06 respectively for symbol ABC is valid for times 1 and 2 but the values change to 10.06 and 10.07 beginning at time 3. TIME will always be an int presented in chronological order.
The BID represents the highest price at which market participants are willing to buy and the ASK represents the lowest price at which market participants are willing to sell. The ASK is always strictly greater than the BID.
The trades file contains:
Each line represents a single trade made by a hypothetical firm. A trade contains the SIDE (whether the firm B(ought) or S(old) the SYMBOL), the PRICE of the transaction, and QUANTITY of shares executed. Again, TIME in this file is chronological.
For each trade, determine the prevailing bid and ask of the execution, as well as the LIQUIDITY tag of the execution. For a B(uy) execution, the LIQUIDITY is P(assive) if the price is at or below the BID or A(ggressive) if the price is at or above the ASK. For a S(ell) execution, the LIQUIDITY is P(assive) if the price is at or above the ASK or A(ggressive) if the price is at or below the BID. As an example, the first ABC and DEF trades above have LIQUIDITY = A and P respectively.
Form opening-closing trade pairs in a first-in-first-out (FIFO) manner.
- Every symbol begins with 0 inventory. The first execution will always be an opening trade as it opens new inventory. With ABC, we see an opening trade that creates net inventory = 500 at time 2.
- If trades occur which increase the magnitude of net inventory (e.g., if another buy were to occur for ABC after the first one) then these new trades are also opening trades and should be maintained in a FIFO structure.
- Any trade that reduces the magnitude of net inventory (e.g., the 200 share sell at time = 4) will be a closing trade and will pair off with the first available opening trade. Whenever this occurs, a "paired trade" record should be generated in the output file. The magnitude paired off will be the minimum of the shares executed by the paired opening and closing trades. In this example, this paired quantity is 200 shares since 200 < 500.
- If the closing trade is smaller than the paired opening trade, then the opening trade's open inventory should be reduced but the trade should maintain its FIFO position. In this example, the first opening ABC trade now holds 300 shares remaining.
- If the closing trade is equal in size to the paired opening trade, then the opening trade is completely consumed.
- If the closing trade is beigger than the paired opening trade, then it consumes the entire opening trade and proceeds to pair against the next opening trades. Note that this means a single closing trade can pair against multiple opening trades. If one closing trade closes 10 opening trades, then this creates 10 separate "paired trades."
- Finally, if the closing trade is bigger than the entire open inventory, whatever is left over from the closing trade actually "flips" the inventory and creates a new opening trade on the opposite side. It will wait until a future closing trade to pair against it. For example, a single Sell trade could close five Buy trades as well be itself an opening Sell trade.
For each paired trade, compute the profit and loss (PNL), which is the product of the paired quantity and the per-share PNL (difference between sell price and buy price).
Write all "paired trades" (in any order) to standard output.
- The firm can sell short in any SYMBOL, i.e., take a negative position.
- If a quote update and trade happen at the same time, the quote update takes precedence.
- There may be some nonzero inventory at the end, i.e., not all trades will be paired. Only print paired trades.
- You may assume that all prices for testing will have at most two decimal places.
- Optimize the code for speed without sacrificing readability.
The output you produce should resemble:
The number of entries in the quotes file is less than 5,000,000.
The number of entries in the trades file is less than 5,000,000.
Time Limit: 20 secs (C++), 60 secs (Python)
Memory Limit: 1 GB
Please submit your code in a single compressed tarball (.tgz or .tar.gz) or zip archive within 24 hours of beginning the coding exercise. Your code will be graded based on correctness, efficiency, and style. We expect the coding and implementation to take between 2-4 hours. Please take as much of the remaining time as you want to test, clean, and document your work appropriately.
Upon submitting, the online judge will compile your code and run your program against a series of large test cases. Compilation erros will be made available to you. If your program terminates unexpectedly, you will be provided with the exit code. When your submission is accepted by the online judge, you have completed the assignment and a human grader will evaluate your implementation. You are allowed an unlimited number of submissions in the 24-hour time span.
We will compile your code using GCC 4.8.2 and run your binary on 64-bit Ubuntu 14.04 LTS. If you choose to develop on an environment different from ours, you are responsible for writing your solution in a portable fashion.
The online judge will extract and compile your code via
g++ -std=c++11 -O3 -o vatic_code_test [all .cpp and .cc source files]
Your binary will be run via
./vatic_code_test [quotes file] [trade file]
We will run your code using Python 2.7 on 64-bit Ubuntu 14.04 LTS
python vatic_code_test.py [quotes file] [trade file]
Please ensure that your script is runnable from the archive root, not from within a subdirectory. Most packages in the Python Standard Library will be available for your use. In addition, we have installed numpy (1.11.1) and pandas (0.19.0). No other third-party packages are allowed.