algorithm - 处理交易列表的算法

Question

这是我在为交易/支付服务公司进行 SWE 实习 OA 时经常遇到的一种问题：给定一个“操作-客户 ID-交易 ID-金额”形式的交易列表，我们被要求处理它们并返回一个要采取的行动清单或剩余的金额。

这是一个具体的例子。输入是一个字符串列表，形式为“操作-订单 ID-价格-金额-买入/卖出”，只有 2 个操作 SUB（提交）和 CXL（取消）。

• 对于买入，较高的价格具有较高的优先级，而对于卖出，较低的价格具有较高的优先级。如果对于相同的买入或卖出类别，价格相似，则较早出现的字符串具有更高的优先级。
• 如果买价 >= 卖价，则两个订单匹配，Amount = min(Amount of Sell, Amount of Buy)，买或卖将相应决定。
• 如果订单已经成交，则不会被取消。
• 如果 CXL 操作中的订单 ID 不存在，则不会生效（无错误）。

我们被要求返回一个要执行的操作列表，输出应该是一个字符串列表，格式如下：“订单 ID-Buy/Sell-Amount to Buy/Sell”

输入输出示例：

输入：[“SUB-hghg-10-400-B”，“SUB-abab-15-500-B”，“SUB-abcd-10-400-S”]

输出：[“abcd-S-400”]

解释：“abab”的买入价比“hghg”高，虽然它来得晚，所以会先处理。abab 数量 = 500，abcd 数量 = 400 => 数量 = 400

输入：["SUB-hghg-10-400-B", "CXL-hghg"]

输出： []

解释：什么都不做，因为订单在成交之前就被取消了。

我曾尝试使用哈希映射来解决这个问题，但它对我来说太复杂了。之前，我也遇到过类似的问题，但不同的是，无论订单是否已成交，取消都会删除订单，在这种情况下，我使用 LinkedList 来跟踪订单。

我想问是否有任何通用方法可以优化解决这些问题。我在 LeetCode 上闲逛了一段时间，练习了一些 Medium 题，但没有遇到过这种题型。如果有任何典型的数据结构可以有效地存储每个订单的信息，我也想知道。我还在互联网上搜索了一些关键字，如算法交易、处理支付/交易的算法，但我还没有找到任何有用的东西。任何帮助是极大的赞赏！

非常感谢您阅读我的长篇文章。

标签： algorithmdata-structuresalgorithmic-trading

Answer 1

所以你的输入是一系列提交和取消的订单，你的输出是订单匹配时发生的一系列交易，对吧？

我将按如下方式解决问题：创建一个订单簿数据结构，其中包含所有打开的（不匹配的）订单，分别买卖，按价格排序。

Init：订单簿当然初始化为空。也将您的结果交易列表初始化为空。

循环：然后将传入的请求（提交或取消）一一处理并应用到订单簿中。这会将订单添加到账簿或订单匹配一个或多个其他订单并生成新交易。将生成的交易附加到您的交易列表中。

基本上就是这样。但是，请注意，将新订单与图书匹配并非易事。账簿中的一个订单可能仅部分匹配并保留在账簿中，或者新订单将仅部分匹配且必须将剩余金额添加到账簿中。我建议为单个步骤编写单元测试，以便确保您的订单按预期排序和匹配。