给定一百万个数字的字符串，返回所有重复的3位数字

Question

几个月前，我在纽约采访了一家对冲基金公司，不幸的是，我没有得到作为数据/软件工程师的实习机会。（他们还要求解决方案使用Python）

我在第一个面试问题上搞砸了。。。

Question: Given a string of a million numbers (Pi for example), write a function/program that returns all repeating 3 digit numbers and number of repetition greater than 1

例如：如果字符串是：123412345123456，则函数/程序将返回：

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

在我面试失败后，他们没有给我解决方案，但他们告诉我，解决方案的时间复杂度恒定为1000，因为所有可能的结果都在以下之间：

000-->；999

现在我在想，我不认为有可能想出一个恒定时间的算法。它是？

Answer 1

你很容易就放弃了，你可能不想为一家对冲基金工作，因为那里的量子人不懂基本算法：-）

在O(1)中处理任意大小的数据结构的方法是no如果，在本例中，您需要至少访问每个元素一次。在本例中，最好的是O(n)，其中n是字符串的长度。

Although, as an aside, a nominal O(n) algorithm will be O(1) for a fixed input size so, technically, they may have been correct here. However, that's not usually how people use complexity analysis.

在我看来，你可以在很多方面给他们留下深刻印象。

首先，告诉他们，除非你使用上面给出的“可疑”推理，否则在O(1)中做这件事是不可能的。

其次，通过提供python代码来展示您的精英技能，例如：

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)]

当然，您也可以将输出格式修改为您想要的任何格式。

最后，告诉他们，几乎可以肯定的是，O(n)解决方案存在no问题，因为上面的代码在不到半秒的时间内就可以为一百万个数字字符串提供结果。因为10000000个字符串需要3.5秒，10000000个字符需要36秒，所以它看起来也很线性。

而且，如果他们需要比这更好的东西，有很多方法可以将这类东西并行，从而大大加快速度。

当然，由于GIL的原因，不在一个单独的Python解释器中，但是您可以将字符串拆分成类似的内容（需要由vv指示的重叠来允许正确处理边界区域）：

    vv
123412  vv
    123451
        5123456

你可以把这些分给不同的工人，然后把结果合并起来。

输入的拆分和输出的组合可能会用小字符串（甚至可能是一百万个数字字符串）淹没任何存储，但对于更大的数据集，这很可能会产生影响。当然，我常用的格言“量度，别猜”适用于这里。

---

这个咒语也适用于其他可能性，例如完全绕过Python，使用一种可能更快的不同语言。

例如，下面的C代码运行在与前面的Python代码相同的硬件上，它在0.6秒内处理a100million位，与Python代码处理onemillion的时间大致相同。换句话说，要快得多：

#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;
}

Answer 2

简单的O（n）解决方案是计算每个3位数：

for nr in range(1000):
    cnt = text.count('%03d' % nr)
    if cnt > 1:
        print '%03d is found %d times' % (nr, cnt)

这将搜索100万个数字1000次。

只遍历一次数字：

counts = [0] * 1000
for idx in range(len(text)-2):
    counts[int(text[idx:idx+3])] += 1

for nr, cnt in enumerate(counts):
    if cnt > 1:
        print '%03d is found %d times' % (nr, cnt)

计时显示，仅在索引上迭代一次的速度是使用count的两倍。

Answer 3

恒定的时间是不可能的。所有100万位数字都需要至少查看一次，所以这是O（n）的时间复杂度，在这种情况下n=100万。

对于简单的O（n）解决方案，创建一个1000大小的数组，该数组表示每个可能的3位数的出现次数。每次前进1位，第一个索引==0，最后一个索引==99999 7，并递增数组[3位数字]以创建直方图（每个可能的3位数字的出现次数）。然后输出计数为1的数组内容。