amazon interview prob

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

私はブログでこの質問を見つけましたが、答えを理解できませんでした。答えは：ハッシュテーブル+ミニヒープ

私はハッシュテーブルはなぜミニヒープ部分ではないのか理解していますか？

2012-08-26 rplusg

通常は、各段階で候補の回答があり、それが最小ヒープの回答よりも優れているかどうかを知りたいので、最も高いN個の回答を追跡することが必要です最小ヒープから上位Nの最悪の解を取り除き、候補を挿入します。 - 直感的な - 最大ヒープを持つことは、最高の答えを選ぶことを非常に簡単にしますが、新しい候補の回答を受け入れるかどうかを決めるとき、これはあなたが望むものではありません。（最後に上位N個の回答を抽出すると、最初にN個の回答が抽出されると、最初にN個の回答が抽出されることを忘れないでください）。 – mcdowella

top 10 trending wordsの場合はmax-heapとhash-tableを使用してください。

Createx.key=wordとx.count=1と新しい要素x：新しい単語がそのファイルに追加され

。
Addx~hash-table。 O(1)。
Addx~max-heap。 O(lgn)。 hash-tableで
- Findx：既存の単語がそのファイルに追加され
。 O(1)。
Updatex.count~x.count++。

top 10 trending wordsその後、取得する必要があります：max-heapから

Extract 10回。 10*O(lgn)=O(10*lgn)=O(lgn)。

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

出典

2012-08-27 05:38:02

あなたはminヒープを使いたいでしょう：トップ10にない既存の単語がトップ10になったら、その分を削除すると一貫した時間になります。 – aw626

"最大ヒープでx.countをx.countに更新" - それは 'O（n）'であってはなりませんか？最初に 'max-heap'で' x'を見つけなければなりませんが、どこにあるのかは分かりません。一度それを見つけたら、それをインクリメントしてバブリングすることは 'O（lgn）'操作です。 –

@B-Con： 'max-heap'と' hash-table'は同じ要素 'x'を指しているので、ハッシュテーブルでそれを再度見つける必要はありません。私はそれを修正します、ありがとう。 –

トップ10のみを保持したい場合は、最大ヒープを使用することが過剰です。並べ替えられた配列に10個のエントリを保持する方が簡単で高速になります。

ソートするには、配列の一番下から挿入の並べ替えを使用してください。必要に応じて候補者がすでにトップ10に入っている場合は、そのポジションを更新する必要があります。

出典

2012-08-28 07:05:20 salva

他のエントリを保持しないと、新しいエントリがトップ10になりません。 –

@KarolyHorvath：明らかにエントリあたりのヒット数をカウントするにはまだハッシュテーブルが必要です。私のポイントは、トップ10のエントリを管理するためにmin-heapを使用することは過度のことです。シンプルなソートされた配列はパフォーマンスが向上し、実装もかなりシンプルになります。実際には、増分更新されたトップN（および大規模な関係がない限り）ソートされた配列は、常にmin-heapよりも優れたパフォーマンスを発揮します。 – salva

答えて

関連する問題