我已经多次看到这个算法问题或它的变体,但没有找到或无法确定问题的最佳解决方案。问题是:
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.
您将如何设计一个系统来处理这些要求?
然后是对这个问题的跟进:如果一个队列比另一个慢(数据延迟)怎么办。你会如何处理?
最佳答案
您可以采用与合并排序中的合并算法类似的方式来执行此操作,只是加倍。
我将描述一种算法,在该算法中我选择队列 #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
.
关于algorithm - 对两路数据的操作——设计算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45569947/