1

Ok、

たくさんのインタビューでこの質問を受けてきましたが、それを解決するには助けが必要だと思います.

文字列配列として言うか、ファイルから読み取るURLがたくさんあります。ファイル内の上位 10 の最も頻繁な URL のように、最も読まれた上位 10 の URL を取得する必要があります。

私のアプローチは次のとおりです。

         Read them into a String Array, 
         Iterate through each String/URL,
             At every Iteration, put them into Hashtable, incrementing the count.
         Iterate again and find feed the scores into an array
         Sort and find the top 10 scores OR use max-heap to get the top 10.
         Iterate again and remove the URL's with the top 10 scores.

これは非常に悪い答えですか？誰かがこれについてさらに助けてくれますか?

4

3 に答える 3

3

最小限のメモリと、基本的に無制限のサイズのファイルでこれを行うことができます。

Use the OS-supplied sort utility to sort the URLs on disk
Create a priority queue (binary heap, for example)
For each URL in the file
    if the URL is the same as the previous URL
        increase count
    else
        AddToQueue(previous_url, count)
        previous_url = current_url
        count = 1
EndFor
AddToQueue(previous_url, count)

この時点で、最も訪問された上位 10 個の URL が優先キューに入れられます。

関数は次のAddToQueueようになります。

AddToQueue(url, count)
    if (queue.Count < 10)
        add new url with count to queue
    else if (count > top_of_queue.count)
        remove top URL from queue
        add new url with count to queue

すべての URL をロードするのに十分なメモリがある場合は、それらを配列にロードして並べ替えることができます。ただし、すべての URL に対して十分なメモリがある場合は、辞書ベースのアプローチの方がおそらく高速です。

于 2013-09-22T00:10:38.513 に答える
0

まず、余分なメモリを不必要に使用していることに注意してください。すべてを配列に読み込み、その配列を繰り返し処理してすべてをハッシュ テーブルに挿入するのはなぜですか? そうする非常に強い理由がない限り、それを読みながらハッシュテーブルに入れる必要があります。

これにより、配列の必要性がなくなり、メモリ使用量が O(n) 減少します。他の手順はかなり合理的に聞こえます。上位 10 のスコアの 10 エントリの配列を維持するというアイデアは優れたアプローチですが、効率的に行うにはどうすればよいかという問題が生じます。

また、ハッシュ テーブルを使用すると実装上の問題が発生する可能性があります。通常は組み込みライブラリにあるものに依存しすぎています。インタビューのために、おそらくより良いアプローチは、各ノードが文字列とその文字列の出現回数（および左右のノードへのポインター）を含む構造を保持するバイナリ検索ツリーにすべてを読み取ることです。二分探索木を使用すると、文字列が O(log(n)) 時間で存在するかどうかを確認できます。すべてを読み込んでツリーに配置したら、シェルソートでツリーをソートできます。シェルソートは、大量の障害を迅速に排除する傾向があるため、この演習に適しています。このソリューションは O(nlog(n)) 時間で実行されます。

面接担当者がハッシュ テーブルの使用に問題がない場合は、ツリーを実装する価値はないかもしれませんが、「ハッシュ テーブルを使用します」と言うと、もちろんハッシュを実装しない限り、自分自身を撃つことができます。テーブル。それは本当に文脈に依存します。

于 2013-09-21T19:26:39.040 に答える