私は最近、このインタビューの質問に出くわしました:
Given a continuous twitter feed, design an algorithm to return the 100 most
frequent words used at this minute, this hour and this day.
word -> count現在の分、時間、日の 3 分ヒープにリンクされたハッシュ マップを持つシステムを考えていました。
すべての受信メッセージはトークン化され、サニタイズされ、単語数がハッシュ マップで更新されます (単語が既にヒープに存在する場合は、ヒープ内のキーが増加します)。
単語のいずれかがヒープに存在しない場合 (およびヒープ サイズ == 100) は、それらfrequency > min valueがヒープに存在するかどうかを確認し、存在する場合は抽出分をヒープに挿入します。
これを行うより良い方法はありますか？
あなたのアルゴリズムは良いスタートですが、正しい結果を生み出すことはできません。問題は、ハッシュテーブルを説明する方法が一方通行であるということです。単語が追加されると、その単語は永久にカウントされたままになります。
説明する方法で編成された1440（24 * 60）ハッシュマップの配列が必要です。word+countこれらは分単位のカウントです。時間と日の合計の2つの追加のハッシュマップが必要です。
ハッシュマップで2つの操作を定義します-addとsubtract、同一の単語のカウントをマージし、カウントがゼロになったときに単語を削除するというセマンティクスを使用します。
1分ごとに新しいハッシュマップを開始し、フィードからカウントを更新します。分の終わりに、そのハッシュマップを現在の分の配列に配置し、それを1時間とその日のローリング合計に追加してから、1時間前のハッシュマップを1時間の現在の合計から減算します。そして、24時間前のハッシュマップを1日の現在の合計から差し引きます。
最後に、ハッシュマップを指定して上位100語を生成する方法が必要です。これは簡単な作業です。エントリの配列にアイテムを追加word+countし、カウントで並べ替えて、上位100を維持します。
dasblinkenlight は、ハッシュ マップからアイテムを除外しないという間違いを指摘しました。
ただし、追加することがもう 1 つあります。実際に分/時間/日を指定して上位 K 語を計算するには、並べ替え (O(nlgn)) よりもパーティション (O(n)) を使用する方が高速です。
HTH。