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

Question

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

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

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

000-->999

现在我在考虑，我认为不可能想出一个常数时间的算法。是吗？

Answer 1

你轻松地离开了，你可能不想为一个量化员不懂基本算法的对冲基金工作：-）

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

不过，顺便说一句，对于固定的输入大小，名义上的O(n)算法将是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)]

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

当然，由于GIL，不在一个Python解释器中，但是您可以将字符串拆分为类似的部分(vv指示的重叠是允许正确处理边界区域所必需的）：

    vv
123412  vv
    123451
        5123456

您可以将这些分解出来，以分离员工，然后将结果组合在一起。

输入的拆分和输出的组合可能会用小字符串（甚至可能是百万位数的字符串）淹没任何保存，但对于更大的数据集，这很可能会有所不同。当然，我通常的口头禅“衡量，不要猜测”也适用于这里。

例如，下面的C代码运行在与早期Python代码相同的硬件上，在0.6秒内处理1亿个数字，与Python代码处理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;
}