[解決済み] 100万個の数字の文字列が与えられたとき、繰り返される3桁の数字をすべて返す。

質問

数ヶ月前にニューヨークのヘッジファンド会社の面接を受けましたが、残念ながらデータ/ソフトウェアエンジニアとしてのインターンシップのオファーはもらえませんでした。(彼らはまた、Pythonで解決することを求めました)。

最初の面接の問題でかなり失敗してしまいました...。

質問です。100万個の数字の文字列（例えば円周率）が与えられたら、3桁の数字の繰り返しとその数を 3桁の数字の繰り返しをすべて返す関数/プログラムを書いてください。 が1より大きい場合。

例：文字列が 123412345123456 であった場合、関数/プログラムは以下を返します。

123 - 3 times
234 - 3 times
345 - 2 times

面接に落ちた後、解答は教えてもらえませんでしたが、解答のための時間複雑性は、すべての可能な結果の間にあるので、1000の定数であると言われました。

000 --> 999

今考えてみると、定数時間のアルゴリズムは思いつかないような気がします。そうなんでしょうか？

どのように解決するのですか？

軽く済ませたあなたは、おそらく
はありません。 基本的なアルゴリズムも理解できないようなヘッジファンドで働きたくはないでしょう。）

そこには いいえ で任意のサイズのデータ構造を処理する方法はありません。 O(1) にある任意の大きさのデータ構造を処理する方法はありません。 この場合のように、すべての要素を少なくとも一度は訪れる必要がある場合は その ベスト を期待することができます。 O(n) で、この場合 n は文字列の長さである。

とはいえ、余談ですが、名目上の O(n) アルゴリズム は である O(1) になります。ですから、技術的には正しいかもしれません。しかし、これは通常、人々が複雑性分析を使用する方法ではありません。

あなたは多くの方法で彼らを感心させることができたようです。

まず、それが ではなく で可能です。 O(1) を使用しない限りは不可能です。

第二に、以下のようなPythonicなコードを提供することで、あなたのエリートスキルを示すことです。

inpStr = '123412345123456'

# O(1) array creation.
freq = [0] * 1000

# O(n) string processing.
for val in [int(inpStr[pos:pos+3]) for pos in range(len(inpStr) - 2)]:
    freq[val] += 1

# O(1) output of relevant array values.
print ([(num, freq[num]) for num in range(1000) if freq[num] > 1])

これは出力されます。

[(123, 3), (234, 3), (345, 2)]

は、もちろん出力形式を自由に変更することができます。

そして最後に、ほぼ確実に no の問題がないことを伝えることです。 O(n) の問題ではありません。上記のコードでは、100万桁の文字列の結果を0.5秒以下で提供しています。10,000,000 文字の文字列は 3.5 秒、100,000,000 文字の文字列は 36 秒かかるので、かなりリニアにスケールするようです。

そして、もし彼らが が必要な場合 を必要とする場合、この種のものを並列化する方法があり、大幅にスピードアップできます。

の中ではなく シングル GILの関係でもちろんPythonインタプリタですが、文字列を次のように分割することができます（オーバーラップは、表示された vv は境界部分を適切に処理できるようにするために必要です)。

    vv
123412  vv
    123451
        5123456

これらを別々のワーカーにファームアウトして、後で結果を組み合わせることができます。

入力の分割と出力の結合は、小さな文字列 (場合によっては 100 万桁の文字列も) では節約できないかもしれませんが、はるかに大きなデータセットでは、十分に違いが出るかもしれません。私のいつものマントラである 測定しろ、推測するな。 は、もちろんここでも適用されます。

このマントラは、次のような場合にも適用されます。 その他 例えば、Python を完全に回避して、より高速な別の言語を使用することも可能です。

例えば、次のCコードは、先のPythonコードと同じハードウェア上で実行され、Pythonコードに含まれる 百 これは Python コードが処理した時間とほぼ同じ時間です。 1 100万桁を処理したのとほぼ同じ時間です。言い換えれば 大いに より速いのです。

#include <stdio.h>
#include <string.h>

int main(void) {
    static char inpStr[100000000+1];
    static int freq[1000];

    // Set up test data.

    memset(inpStr, '1', sizeof(inpStr));
    inpStr[sizeof(inpStr)-1] = '\0';

    // Need at least three digits to do anything useful.

    if (strlen(inpStr) <= 2) return 0;

    // Get initial feed from first two digits, process others.

    int val = (inpStr[0] - '0') * 10 + inpStr[1] - '0';
    char *inpPtr = &(inpStr[2]);
    while (*inpPtr != '\0') {
        // Remove hundreds, add next digit as units, adjust table.

        val = (val % 100) * 10 + *inpPtr++ - '0';
        freq[val]++;
    }

    // Output (relevant part of) table.

    for (int i = 0; i < 1000; ++i)
        if (freq[i] > 1)
            printf("%3d -> %d\n", i, freq[i]);

    return 0;
}