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.
