6

私の大学は終わったので、仕事を得るために面接の準備を始めました.面接の準備中にこの面接の質問に出くわしました.

  1. 10000個のASCII文字列のセットがあります（ファイルからロードされます）
  2. stdin から文字列を入力します。
  3. (2) の入力と同じ異なる文字 (順序に関係なく) を含む (1) の文字列のサブセットを (stdout に) 返す擬似コードを記述します。時間を最適化します。
  4. この関数を繰り返し呼び出す必要があるとします。文字列配列は一度初期化してメモリに格納すればOKです。10000 個の文字列すべてをループする必要があるソリューションは避けてください。

この問題を解決するための一般的な疑似コード/アルゴリズムのようなものを誰かに教えてもらえますか? 解決策を考えて頭を悩ませています。私はほとんど Java に精通しています。

4

3 に答える 3

6

これが O(1) アルゴリズムです!

初期化:

探す：

  • ソース文字列の初期化と同じ入力文字列の並べ替え
  • 文字を使用してソース文字列トライをたどり、最後のノードで、そこで参照されているすべての単語を返します
于 2012-11-16T22:48:36.610 に答える
0

彼らは時間を最適化すると言っているので、スペースを好きなだけ乱用しても安全だと思います。

その場合、10000 個の文字列に対して初期パスを実行し、10000 個に存在する一意の文字のそれぞれからインデックス (インデックスのセットではなく) へのマッピングを作成できます。そうすれば、どのセットに文字「x」が含まれているかという質問をマッピングに尋ねることができます。このマッピングを M> と呼びます (順序: O(nm) n が文字列の数で m が文字列の最大長の場合)

再び時間をかけて最適化するには、stdin 入力文字列を一意の文字に減らし、それらをキュー Q に入れることができます (順序 O(p)、p は入力文字列の長さです)。

S と言う新しい素集合を開始します。次に、S = Q.extractNextItem とします。

これで、残りの一意の文字をループして、それらすべてを含むセットを見つけることができます。

While (Q は空ではありません) (ループ O(p)) {

S = S は Q.extractNextItem と交差します (素集合の実装に応じて O(1) に近い)

}

出来上がり、S を返します。

合計時間: O(mn + p + p*1) = O(mn + p)

（まだ早朝ですが、時間分析が正しかったことを願っています）

于 2012-11-16T22:54:43.757 に答える
0

ボヘミアンが言うように、トライ木は間違いなく行くべき道です!

これは、アドレス帳の検索が電話で機能する方法のように思えます。数字のパンチを開始し、数字の表現と、数字が表す 3 つの文字 (国際文字を使用している場合は実際にはそれ以上) のいずれかに基づいて、アドレス帳をフィルター処理します。

于 2012-11-16T23:09:09.467 に答える