处理事务列表的算法
这是我在为贸易/支付服务公司进行SWE实习时经常遇到的一种问题:给出一份表格"Action-Customer ID-Transaction ID- are“的交易清单，要求我们处理这些交易，并返回要采取的行动或剩余金额的清单。
下面是一个具体的例子。输入是一个字符串列表，其表单为"Action-Order ID-Price- CXL Buy/Sell“，只有两个操作子(提交)和CXL(取消)。
- 对于购买，较高的价格有更高的优先权，而对于销售，低的价格有更高的优先权。如果对于相同的买入或卖出类别，价格是相似的，那么较早出现的字符串具有更高的优先级。如果accordingly.
- If
- ，如果买入>=的价格是卖出的，那么两个订单是匹配的，数量=min(成交量，买入量)，买入或卖出将被确定为一个已被填充的订单，它不会被取消。如果CXL行动中的订单ID不存在，则不会产生任何影响(
)。
我们被要求返回要采取的操作列表，输出应该是具有以下格式的字符串列表："Order ID-Buy/Sell- actions to Buy/Sell“
输入和输出示例：
输入：“SUB 10-400-B”，“15-500-B”，“sub-abd-10-400-S”
输出："abcd-S-400“
说明："abab“有比"hghg”更高的购买价格，即使它来得晚，所以它将首先被处理。abab = 500，abcd = 400 => = 400
输入：“subhghg-10-400-B”，"CXL-hghg“
产出：[]
说明:不要做任何事情，因为订单在填好之前就被取消了。
我尝试过使用散列映射来解决这个问题，但是对我来说太复杂了。在此之前，我也遇到过类似的问题，但不同之处在于，无论订单是否已填充，取消都会删除订单，在这种情况下，我使用LinkedList跟踪订单。
我想问一问，是否有任何一般方法可以最有效地解决这类问题。我在LeetCode上徘徊了一段时间，练习了一些中等的问题，但没有遇到这个问题类型。如果有任何典型的数据结构来有效地存储每个订单的信息，我也想知道。我还在互联网上搜索了一些关键词，比如算法交易，处理支付/交易的算法，但我还没有发现任何有用的东西。任何帮助都是非常感谢的！
非常感谢你阅读了我的长篇文章。
回答 1
Stack Overflow用户
发布于 2020-12-21 18:40:25
因此，您的输入是一系列提交的订单和取消，而您的输出是在订单匹配时发生的一系列交易，对吗？
我会按照以下方式来处理这个问题:创建一个订单数据结构，其中包含所有打开的(无与伦比的)异类，按价格单独买卖。
Init:订单簿当然是空的。初始化结果交易列表也是空的。
循环:然后依次处理传入的请求(提交或取消)，并将它们应用到订单簿中。这将将订单添加到书中，或者订单与一个或多个其他订单相匹配，从而生成一个新的交易。将结果交易附加到您的交易列表中。
基本上就是这样。然而，请注意，与这本书匹配一个新的订单并不是完全微不足道的。书中的一个订单可能只能部分匹配，并保留在书中，否则新订单将只能部分匹配，其余的金额必须添加到书中。我建议为单个步骤编写单元测试，这样您就可以确保您的订单按预期排序和匹配。
https://stackoverflow.com/questions/65387659
复制相似问题
腾讯云开发者
