0

私は最近、理論的な C の質問をされましたが、どのようにアプローチするのが最善なのか疑問に思っていました。

10 個の単語が含まれるドキュメントがある場合、重複する単語があるかどうかを判断する最良の方法は何ですか?

これにどのようにアプローチするかについての洞察は素晴らしいでしょう。

4

5 に答える 5

5

キーワードは「10」です。これは、2 つのネストされたループが各単語の前で相互にチェックする最も単純なアプローチでうまくいくことを意味します。その数がたとえば 10000000 の場合、ハッシュ テーブル、ヒープ、または並べ替えられた配列を使用したアプローチが保証されます。ただし、10 ワードしかないので、複雑なものを作成する必要はありません。基本的な C 文字列の読み取り/比較の知識があれば十分です。

于 2012-06-07T21:02:34.590 に答える
2

このような理論的な面接の質問は、常に少数 (10 語など) を扱います。ただし、数字は何の意味もありません。一般的な形で問題を本当に考えることができる候補者と、インターネットで見つけた決まった面接の質問に対する決まった答えを単に吐き出すだけの候補者を区別するためにあります。

最高のソフトウェア ハウスは、スケーラブルなソリューションのみを優先します。したがって、答えが単純で、あらゆるサイズの問題 (この場合は文書) に対応できるものであれば、面接で最高点を獲得できます。したがって、並べ替え、ループ内のループ、O(n^2) の複雑さはすべて忘れてください。最先端のソフトウェア企業の面接で、このようなソリューションを提示した場合、失敗するでしょう。

特定の質問は、 Hash Tablesについて知っているかどうかを確認することです。この問題に対する最も効率的な解決策は、次のように疑似コードで記述できます。 

1. Initialise a new hash table.
   For each word in the document...
2.     Generate a hash key for the word.
3.     Lookup the word in the hash table using the key. If it is found,
4.         Increment the count for the word.
       Otherwise,
5.         Store the new word in table and set its count to one.


上記のソリューションの最も重要な利点は 、ドキュメントを 1 回スキャンするだけで済むことです。単語をメモリに読み込んでから処理すること (2 回のスキャン)、ループ内のループ (多くのスキャン)、並べ替え (さらに多くのパス) はありません。ドキュメントを 1 回パスした後、ハッシュ テーブルのキーを読み取ると、各単語のカウントから、各単語がドキュメントに出現した回数が正確にわかります。カウントが 1 より大きい単語はすべて重複です。

このソリューションの秘密は、ハッシュ テーブルの使用です。ハッシュ キーの生成 (ステップ 2)、キー ルックアップ (ステップ 3)、およびキー ストレージ (ステップ 5) は、ほぼ一定時間の操作として実装できます。これは、入力セットのサイズ (単語数) が大きくなっても、これらのステップにかかる時間はほとんど変わらないことを意味します。これは、ドキュメントの 10 番目の単語であろうと、1000 万番目の単語であろうと、その単語をハッシュ テーブルに挿入する (または検索する) のにかかる時間は、ほぼ同じであることを意味します。この場合、さらにステップ 5 で各単語の頻度のカウントを保持します。値の増分は、非常に効率的な固定時間操作であることが知られています。

この問題を解決するには、ドキュメント内のすべての単語を少なくとも 1 回スキャンする必要があります。私たちのソリューションは各単語を正確に1 回処理し、すべての単語の処理にかかる時間はほぼ同じ非常に短い一定時間であるため、ソリューションは最適に実行され、線形にスケーリングされ、 O(n) のパフォーマンスが得られます(簡単に言うと、1,000,000 単語の処理には約 1000 時間かかります)。 1000 語を処理するよりも 30 倍長い)。全体として、問題に対するスケーラブルで効率的なソリューション

于 2012-06-13T09:41:42.800 に答える
0

個々の単語の長さは「小さい」可能性が高いため、基数ソートhttp://en.wikipedia.org/wiki/Radix_sortから始めます。これには、O（nk）時間がかかります。ここで、kは最大単語長です。この場合、最初に単語を長さ（最大n個）に従って別々のリストに並べ替えることをお勧めします。

重複のみに関心があるため、長さ1の任意のリスト（このステップまたは後続のステップ）を破棄できます。

リストごとに、各リストメンバーの最後の文字を比較し、表示された個別の文字ごとに新しい単語のリストを作成し（単語がすべてASCII文字であると仮定すると、最大26個）、最後の文字を切り捨てます。ここでも、長さ1のリストを破棄し、新しいリストを再帰的に並べ替えます。

最悪の場合（LSD基数ソートを想定すると、すべての単語は同じ長さで、最初の文字のみが異なります）、O（nk）時間が得られます。最良の場合（すべての単語の長さが異なる）、O（n）時間が得られます。実際のケースでは、おそらくO（nk）時間よりも大幅に改善されるため、ソリューションはより長い単語リストにうまくスケールアップする必要があります。

于 2012-06-08T15:44:32.007 に答える
0
  1. scanf を使用して単語を文字列の配列に読み込みます
  2. 各単語について、strncmp を使用して、リストの後半にある他の単語と比較します

速度とスペースの最適化がありますが、私は (通常) 単純化のために最適化します。

于 2012-06-07T21:02:18.083 に答える
0

大規模な実装では、ハッシュ テーブルを使用して衝突をチェックできます

小さな n (例: n = 10) の場合、要素を調べて配列に追加できます。各要素について、配列をチェックして、重複しているかどうかを確認します。

配列のチェックは O(n) で、10 個の要素のそれぞれを調べるのは O(n) です。これはネストされたループで簡単に実装できるため、O(n^2) 時間の複雑さで実行できます。n の値がこのように小さい場合、パフォーマンスへの影響は無視できるため、これで十分です。

于 2012-06-07T23:54:28.690 に答える