10

この質問は、Googleのインタビューで私に尋ねられました。私はそれをすることができましたO（n * n）...私はより良い時間にそれをすることができますか？文字列は1と0でのみ形成できます。

意味：

XとYは、0または1で形成される文字列です。

D(X,Y)= XとYの両方から最初に共通するものを削除します。次に、両方の文字列から残りの長さを追加します。

例えば

D(1111, 1000)=最初のアルファベットのみが一般的です。したがって、残りの文字列は111＆000です。したがって、結果length("111")＆length("000")= 3 + 3 = 6

D(101, 1100)=最初の2つのアルファベットのみが一般的です。したがって、残りの文字列は01＆100です。したがって、結果length("01")＆length("100")= 2 + 3 = 5

そのようなクレイジーな距離が直線的になることを知るのは明らかです。O（m）。

今の質問は

n個の入力が与えられた場合、次のように言います

1111
1000
101
1100

可能な最大の狂気の距離を見つけてください。

nは入力文字列の数です。mは、入力文字列の最大長です。

O（n 2 * m）の解は非常に簡単です。それはより良い方法で行うことができますか？mが固定されていると仮定しましょう。O（n ^ 2）よりもうまくこれを行うことができますか？

4

6 に答える 6

22

文字列をツリーに配置します。0 は左に移動し、1 は右に移動することを意味します。たとえば

1111
1000
101
1100

のようなツリーになります

        Root
             1
          0     1
         0 1*  0  1
        0*    0*    1*

* は、要素がそこで終了することを意味します。このツリーの構築には明らかにO(n m).

ここで、ツリーの直径(2 つのノード間の最長パス。「クレイジー ディスタンス」と同じもの) を見つける必要があります。そこに示されている最適化されたアルゴリズムは、ツリー内の各ノードに 1 回ヒットします。min(n m, 2^m)そのようなノードはせいぜいあります。

したがって、 の場合n m < 2^m、アルゴリズムはO(n m)です。

場合n m > 2^m(そして必然的に入力を繰り返した場合)、アルゴリズムはまだO(n m)最初のステップからです。

これは、一般的なアルファベットの文字列でも機能します。文字を含むアルファベットの場合、-ary ツリーがk構築されます。この場合、実行時間は同じ理由で O(nm) のままですが、メモリは何倍も必要です。kk

于 2013-02-25T08:14:03.383 に答える
4

これは、文字列の各ビットがパス (左 0、右 1) をエンコードするバイナリ ツリーを作成することで、O(nm) 時間で可能になると思います。次に、O(n) 時間で実行できるツリーのノード間の最大距離を見つけます。

于 2013-02-25T08:14:13.787 に答える
1

これは私の解決策です、私はそれがうまくいくと思います：

  1. すべての文字列から二分木を作成します。ツリーは次のように構築されます。すべてのラウンドで、文字列を選択してツリーに追加します。したがって、あなたの例では、ツリーは次のようになります。

                      <root>
          <1>            <empty>
 <1>            <0>

    <1> <0> <1> <0> <1> <0> <0>

したがって、ルートからリーフへの各パスは文字列を表します。

  1. これで、2枚の葉の間の距離が2本の弦の間の距離になります。クレイジーな距離を見つけるには、このグラフの直径を見つける必要があります。これは、dfsまたはbfsで簡単に行うことができます。

このアルゴリズムの全体的な複雑さは、O（n * m）+ O（n * m）= O（n * m）です。

于 2013-02-25T08:21:25.727 に答える
0

この問題は「2 つの文字列のプレフィックスを見つける」のようなものだと思います。trie ( http://en.wikipedia.org/wiki/Trie ) を使用して検索を高速化できます。

3日前にGoogleの電話面接がありましたが、失敗したかもしれません...

幸運を祈ります

于 2014-05-05T07:40:53.097 に答える
0

コードの複雑さなしに、反復によって同じ大きな計算の複雑さが得られる場合に、ツリーを使用する理由がわかりません。とにかく、ここに私のバージョンのjavascript O(mn)があります

var len = process.argv.length -2; // in node first 2 arguments are node and program file
var input = process.argv.splice(2);
var current;
var currentCount = 0;
var currentCharLoc = 0;
var totalCount = 0;
var totalComplete = 0;
var same = true;
while ( totalComplete < len ) {
        current = null;
        currentCount = 0;
        for ( var loc = 0 ; loc < len ; loc++) {
                if ( input[loc].length === currentCharLoc) {
                        totalComplete++;
                        same = false;
                } else if (input[loc].length > currentCharLoc) {
                        currentCount++;
                        if (same) {
                                if ( current === null ) {
                                        current = input[loc][currentCharLoc];
                                } else {
                                        if (current !== input[loc][currentCharLoc]) {
                                                same = false;
                                        }
                                }
                        }
                }
        }
        if (!same) {
                totalCount += currentCount;
        }
        currentCharLoc++;
}

console.log(totalCount);
于 2015-03-19T05:38:40.443 に答える