2

this is a type of question I usually encounter when doing SWE Internship OA for Trading/Payment Services companies: given a list of transactions of the form "Action-Customer ID-Transaction ID-Amount", we are asked to process them and return a list of actions to take or the amount of money remained.

Here is a specific example. Input is a list of string, with the form "Action-Order ID-Price-Amount-Buy/Sell" with only 2 actions SUB (Submit) and CXL (Cancel).

  • For Buy, Higher price has higher priority while for Sell, lower price has higher priority. If for the same Buy or Sell category, the prices are similar then the string came earlier has higher priority.
  • If price of buy >= price of sell, then two orders are matched and Amount = min(Amount of Sell, Amount of Buy), Buy or Sell will be decided accordingly.
  • If an order has already been filled, it will not be cancelled.
  • If Order ID in CXL action does not exist, there will be no effect (no error).

We are asked to return a list of actions to take, output should be a list of strings with the following format: "Order ID-Buy/Sell-Amount to Buy/Sell"

Input and output examples:

Input: ["SUB-hghg-10-400-B", "SUB-abab-15-500-B", "SUB-abcd-10-400-S"]

Output: ["abcd-S-400"]

Explanation: "abab" has higher Buy price than "hghg" even though it came later, so it will be processed first. Amount of abab = 500, Amount of abcd = 400 => Amount = 400

Input: ["SUB-hghg-10-400-B", "CXL-hghg"]

Output: []

Explanation: do nothing because the order was cancelled before it is filled.

I have attempted the problem using hash maps but it gets too complicated for me. Before, I also encountered a similar problem but the difference is that the Cancel will remove the order regardless of whether it has been filled or not, and in that case I use a LinkedList to keep track of the orders.

I want to ask if there are any general approaches to optimally solve these kinds of problems. I have wandered LeetCode for some time, practicing some Medium questions but have not encountered this problem type. If there is any typical data structure to efficiently store the information of each order, I would like to know also. I have also searched the Internet for some keywords like algorithmic trading, algorithms to process payments/transactions but I have not found anything useful yet. Any help is greatly appreciated!

Thank you so much for reading my lengthy post.

Improve this question
4
  • The question could use a little bit more clarity. Two things I'm not too sure about are 1. What happens to the order that isn't chosen when matching? Does it simply disappear or is it still considered for other matches? 2. If there's a cancellation request, do we not remove the request if, according to our priority rules, the request is filled after the cancellation request? Commented Dec 22, 2020 at 15:18
  • 1. For the order that is not chosen when matching, then it will remain (like still remain in the queue) and awaits incoming order. If higher priority is done matching, then it can be matched. Ultimately if the lower priority cannot be matched and there is also no cancellation request of that order, it simply remains there 2. Take example 1 in my question for better clarity, if the input is ["SUB-hghg-10-400-B", "SUB-abab-15-500-B", "SUB-abcd-10-400-S", "CXL-abcd"] instead, then the output is still the same as before, since order abcd has been filled. I hope my comment clears ur unsureness. Commented Dec 22, 2020 at 19:49
  • Thanks for explaining; 1. makes sense but 2. is a bit unclear. Consider this as an input: ["SUB-aaaa-10-100-B", "SUB-bbbb-5-9-S", "SUB-cccc-4-111-S", "CXL-aaaa", "SUB-dddd-20-200-B"]. Now in the first iteration, we match dddd with with cccc and cccc is left in the queue (dddd is added to output). In the second iteration, do we match cccc with aaaa or is aaaa canceled? As we can see, both orders aaaa and cccc come before the CXL, but we did technically handle an order after the CXL because of how the priority specification. Should aaaa be canceled at this point? Commented Dec 22, 2020 at 21:13
  • For your input, first since price of aaaa = 10 > price of bbbb = 5, then aaaa and bbbb are matched, 9 bbbb will be added to output and there remains 91 aaaa in the queue. Afterwards, price of aaaa = 10 > price of cccc and they are matched, afterwards there are 20 cccc left and 0 aaaa so CXL has no effect. Afterwards, price of dddd = 20 > cccc so ultimately in the queue there are only 180 dddd. Note that priority is only considered if there is multiple Buy before 1 Sell or vice versa. We process one by one, not a list at once. I hope my comment makes sense. Commented Dec 24, 2020 at 0:14

1 Answer 1

Reset to default
1

So your input is a series of submitted orders and cancels and your output is a sequence of the trades that happen when orders are matched, right?

I'd approach the problem as follows: Create an order book data structure that contains all open (unmatched) oders, buys and sells separately, ordered by price.

Init: The order book is of course initialized empty. Initialize your list of resulting trades empty as well.

Loop: Then process the incoming requests (submit or cancel) one by one and apply them to the order book. This will either add the order to the book or the order matches one or more other orders and a new trade is generated. Append the resulting trade to your trades list.

That's it basically. However, please note that matching a new order with the book is not completely trivial. One order in the book may only be matched partially and remain in the book or the new order will only be matched partially and the rest amount has to be added to the book. I'd recommend to write unit tests for the single step so you are sure your orders are sorted and matched as intended.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.