在無限數據流中查找特定時間戳

Question

這是一個面試問題： 假設您有無限量的排序數據進來，實現一種查找特定時間戳的方法。

我能想到的是將數據保存在日誌文件或類似的東西中，並使用sed命令來查找特定時間戳的日誌條目。 我不知道我的想法是否正確。 其他解決方案？

Answer 1

這似乎是一個開放式問題。您的解決方案是將數據保存在日誌文件中，但數據量無限，那麼您還需要一個不切實際的磁盤空間量。該問題可能應該按照以下方式進行分析。

乍一看，隨着無限的數據流進入，它沒有說明它的到來率是多少。假設速率爲每秒r，並且您每秒只能檢查n時間戳。如果r < = n，這不是很有趣。

如果r> n，則只能在每個r/n整數中檢查一個。那意味着你需要維護一個大小爲r/n的緩衝區。輸入排序的事實意味着您可以檢查緩衝區的末尾並查看所需的時間戳是否在範圍內。如果是，則通過緩衝區並確定所需的時間戳。

採訪提示：這些問題往往是開放式的，以判斷你的思維過程。如果沒有詳細說明（就像它在這裏），你應該要求澄清。