在无限数据流中查找特定时间戳

Question

这是一个面试问题： 假设您有无限量的排序数据进来，实现一种查找特定时间戳的方法。

我能想到的是将数据保存在日志文件或类似的东西中，并使用sed命令来查找特定时间戳的日志条目。 我不知道我的想法是否正确。 其他解决方案？

Answer 1

这似乎是一个开放式问题。您的解决方案是将数据保存在日志文件中，但数据量无限，那么您还需要一个不切实际的磁盘空间量。该问题可能应该按照以下方式进行分析。

乍一看，随着无限的数据流进入，它没有说明它的到来率是多少。假设速率为每秒r，并且您每秒只能检查n时间戳。如果r < = n，这不是很有趣。

如果r> n，则只能在每个r/n整数中检查一个。那意味着你需要维护一个大小为r/n的缓冲区。输入排序的事实意味着您可以检查缓冲区的末尾并查看所需的时间戳是否在范围内。如果是，则通过缓冲区并确定所需的时间戳。

采访提示：这些问题往往是开放式的，以判断你的思维过程。如果没有详细说明（就像它在这里），你应该要求澄清。