algorithm - 对两路数据的操作——设计算法

Question

我已经多次看到这个算法问题或它的变体，但没有找到或无法确定问题的最佳解决方案。问题是:

You are given two queues where each queue contains {timestamp, price} pair. You have to print "price 1, price 2" pair for all those timestamps where abs(ts1-ts2) <= 1 second where ts1 and price1 are from the first queue and ts2 and price2 are from the second queue.

您将如何设计一个系统来处理这些要求？

然后是对这个问题的跟进:如果一个队列比另一个慢(数据延迟)怎么办。你会如何处理？

Answer 1

您可以采用与合并排序中的合并算法类似的方式来执行此操作，只是加倍。

我将描述一种算法，在该算法中我选择队列 #1 作为我的“主队列”。这只会提供部分解决方案；之后我会解释如何完成它。

在任何时候，您都会在内存中保留每个队列中的一个条目。每当您认为两个条目相隔不到一秒的条件时，打印出它们的价格。无论您是否这样做，您都会丢弃时间戳较短的那个并获得下一个。如果在任何时候来自队列 #1 的时间戳低于来自队列 #2 的时间戳，则丢弃来自队列 #1 的条目，直到情况不再如此。如果它们都有相同的时间戳，打印出来并从队列#1 中取出一个。重复直到完成。

这将打印出所有的“price1 , price2 ” 对应的 ts1 对和 ts2坚持认为0 <= ts1 - ts2 <= 1 .

现在，对于另一半，只在这一次选择队列 #2 作为您的“主队列”(即做我刚才所说的所有事情，数字 1 和 2 颠倒) - 除了不要打印出对相同的时间戳，因为您已经在第一部分打印了它们。

这将打印出所有的“price1 , price2 ” 对应的 ts1 对和 ts2坚持认为0 < ts2 - ts1 <= 1 ，这就像说 0 > ts1 - ts2 >= -1 .

您将一起获得 -1 <= ts1 - ts2 <= 1 的所有情况的打印输出，即其中 abs(ts1 - ts2) <= 1 .