algorithm - 意味 - アマゾンのインタビューprob




デジタルアルゴリズム (2)

動的に変化している単語の大きなファイルがあります。 我々は継続的にいくつかの単語をそれに追加しています。 あなたはどのようにして各瞬間のトップ10のトレンドワードを追跡しますか?

この質問をブログで見つけましたが、答えがわかりませんでした。 答えは次のとおりです。hash table + min-heap

ハッシュテーブルではなく、最小ヒープ部分ではなく、誰かが私を助けることができる理由は理解できますか?


あなただけのトップ10を維持したい場合は、最大ヒープの使用はやり過ぎです。 ソートされた配列に10個のエントリを保持すると、より簡単で早くなります。

並べ替えには、配列の末尾から始まる挿入並べ替えを使用します。 必要に応じて、候補者がすでに上位10位に位置し、そのポジションを更新しているかどうかを確認する必要があります。


もしそれがtop 10 trending wordsあれば、 hash-tableと共にmax-heap使うべきです。

新しい単語がファイルに追加されると:

  • x.key=wordx.count=1新しい要素xCreate
  • hash-table Add xAdd hash-tableO(1)
  • max-heap Add xAdd max-heapO(lgn)

既存の単語がファイルに追加されると:

  • hash-table xFind hash-tableO(1)
  • x.countx.count++ Updatex.count++

top 10 trending wordsを検索する必要がある場合は、次のようにします。

  • max-heapから10回Extract max-heap10*O(lgn)=O(10*lgn)=O(lgn)

ご覧のとおり、必要な操作はすべて最大O(lgn)で行われます。





algorithm