问题：给定一百万个数字的字符串，返回所有重复的3位数字
几个月前，我在纽约接受了一家对冲基金公司的采访，不幸的是，我没有获得数据/软件工程师的实习机会。（他们还要求解决方案使用Python。）
我几乎搞砸了第一次面试的问题…
问题：给定一百万个数字的字符串（例如，Pi），编写一个函数/程序，该函数/程序返回所有重复的3位数字，并且重复次数大于1
例如：如果字符串为：123412345123456则函数/程序将返回：
123 - 3 times
234 - 3 times
345 - 2 times在面试失败后，他们没有给我解决方案，但他们确实告诉我，解决方案的时间复杂度恒定为1000，因为所有可能的结果都介于：
000-> 999
现在我正在考虑它，我认为不可能提出一个恒定时间算法。是吗？
回答 0
您轻轻松松下手，您可能不想在对量子点不了解基本算法的对冲基金中工作：-)
在这种情况下，如果您需要至少访问一次每个元素，则无法处理任意大小的数据结构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)]尽管您当然可以将输出格式修改为所需的任何格式。
最后，通过告诉他们解决方案几乎没有问题O(n)，因为上面的代码在不到半秒钟的时间内即可提供一百万个数字字符串的结果。它似乎也线性地缩放，因为一个10,000,000个字符的字符串需要3.5秒，而一个100,000,000个字符的字符串需要36秒。
而且，如果他们需要的更好，则可以采用多种方法并行化此类内容，从而可以大大加快这种处理速度。
当然，由于GIL的缘故，不在单个 Python解释器中，但是您可以将字符串拆分成类似的字符（vv为了正确处理边界区域，必须用表示的重叠）：
vv
123412 vv
123451
5123456您可以将它们种出以分开工作，然后再合并结果。
输入的拆分和输出的合并很可能会用小字符串（甚至可能是百万位数字的字符串）淹没任何节省的时间，但是，对于更大的数据集，这很可能会有所作为。当然，我通常的口号是：“不要猜测”。
此口头禅也适用于其他可能性，例如完全绕过Python并使用可能更快的其他语言。
例如，以下C代码，在相同的硬件作为较早Python代码运行，处理一个百在0.6秒万位，大致为Python代码处理的相同的时间量之一百万。换句话说，多速度快：
#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;
}回答 1
固定时间是不可能的。所有一百万个数字都需要至少被查看一次，因此这是时间复杂度O（n），在这种情况下，n =一百万。
对于简单的O（n）解决方案，创建一个大小为1000的数组，该数组表示每个可能的3位数字的出现次数。一次前进1位数字，第一个索引== 0，最后一个索引== 999997，并递增array [3位数字]以创建直方图（每个可能的3位数字出现的次数）。然后输出计数> 1的数组内容。
回答 2
一百万对于我在下面给出的答案来说很小。只期望您必须能够不间断地在面试中运行解决方案，然后以下操作将在不到两秒钟的时间内完成并给出所需的结果：
from collections import Counter
def triple_counter(s):
c = Counter(s[n-3: n] for n in range(3, len(s)))
for tri, n in c.most_common():
if n > 1:
print('%s - %i times.' % (tri, n))
else:
break
if __name__ == '__main__':
import random
s = ''.join(random.choice('0123456789') for _ in range(1_000_000))
triple_counter(s)希望访问者可以使用标准库collections.Counter类。
并行执行版本
我为此写了一篇博客文章，并提供了更多解释。
回答 3
简单的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。
回答 4
这是“共识” O（n）算法的NumPy实现：遍历所有三元组和bin。通过遇到“ 385”，将bin加到bin [3,8,5]（这是一个O（1）操作）中来完成合并。垃圾箱排列成一个10x10x10立方体。由于合并已完全矢量化，因此代码中没有循环。
def setup_data(n):
import random
digits = "0123456789"
return dict(text = ''.join(random.choice(digits) for i in range(n)))
def f_np(text):
# Get the data into NumPy
import numpy as np
a = np.frombuffer(bytes(text, 'utf8'), dtype=np.uint8) - ord('0')
# Rolling triplets
a3 = np.lib.stride_tricks.as_strided(a, (3, a.size-2), 2*a.strides)
bins = np.zeros((10, 10, 10), dtype=int)
# Next line performs O(n) binning
np.add.at(bins, tuple(a3), 1)
# Filtering is left as an exercise
return bins.ravel()
def f_py(text):
counts = [0] * 1000
for idx in range(len(text)-2):
counts[int(text[idx:idx+3])] += 1
return counts
import numpy as np
import types
from timeit import timeit
for n in (10, 1000, 1000000):
data = setup_data(n)
ref = f_np(**data)
print(f'n = {n}')
for name, func in list(globals().items()):
if not name.startswith('f_') or not isinstance(func, types.FunctionType):
continue
try:
assert np.all(ref == func(**data))
print("{:16s}{:16.8f} ms".format(name[2:], timeit(
'f(**data)', globals={'f':func, 'data':data}, number=10)*100))
except:
print("{:16s} apparently crashed".format(name[2:]))毫不奇怪，在大型数据集上，NumPy比@Daniel的纯Python解决方案要快一点。样本输出：
# n = 10
# np 0.03481400 ms
# py 0.00669330 ms
# n = 1000
# np 0.11215360 ms
# py 0.34836530 ms
# n = 1000000
# np 82.46765980 ms
# py 360.51235450 ms回答 5
我将解决以下问题：
def find_numbers(str_num):
final_dict = {}
buffer = {}
for idx in range(len(str_num) - 3):
num = int(str_num[idx:idx + 3])
if num not in buffer:
buffer[num] = 0
buffer[num] += 1
if buffer[num] > 1:
final_dict[num] = buffer[num]
return final_dict应用于示例字符串，将生成：
>>> find_numbers("123412345123456")
{345: 2, 234: 3, 123: 3}该解决方案在O（n）中运行，因为n是提供的字符串的长度，并且我认为这是您可以获得的最佳结果。
回答 6
根据我的理解，您无法在固定时间内获得解决方案。至少需要通过一百万个数字（假设它是一个字符串）。您可以对百万个长度数字的位数进行三位数的滚动迭代，如果哈希键已经存在，则将其增加1；如果哈希密钥不存在，则创建一个新的哈希键（由值1初始化）。词典。
该代码将如下所示：
def calc_repeating_digits(number):
hash = {}
for i in range(len(str(number))-2):
current_three_digits = number[i:i+3]
if current_three_digits in hash.keys():
hash[current_three_digits] += 1
else:
hash[current_three_digits] = 1
return hash您可以筛选出项值大于1的键。
回答 7
如另一个答案中所述，您不能在固定时间内执行此算法，因为您必须查看至少n位数字。线性时间是最快的。
但是，该算法可以在O（1）空间中完成。您只需要存储每个3位数字的计数，因此您需要一个包含1000个条目的数组。然后，您可以输入号码。
我的猜测是，当面试官给您解决方案时，他们会误以为是，或者当他们说“恒定空间”时，您会误以为“恒定时间”。
回答 8
这是我的答案：
from timeit import timeit
from collections import Counter
import types
import random
def setup_data(n):
digits = "0123456789"
return dict(text = ''.join(random.choice(digits) for i in range(n)))
def f_counter(text):
c = Counter()
for i in range(len(text)-2):
ss = text[i:i+3]
c.update([ss])
return (i for i in c.items() if i[1] > 1)
def f_dict(text):
d = {}
for i in range(len(text)-2):
ss = text[i:i+3]
if ss not in d:
d[ss] = 0
d[ss] += 1
return ((i, d[i]) for i in d if d[i] > 1)
def f_array(text):
a = [[[0 for _ in range(10)] for _ in range(10)] for _ in range(10)]
for n in range(len(text)-2):
i, j, k = (int(ss) for ss in text[n:n+3])
a[i][j][k] += 1
for i, b in enumerate(a):
for j, c in enumerate(b):
for k, d in enumerate(c):
if d > 1: yield (f'{i}{j}{k}', d)
for n in (1E1, 1E3, 1E6):
n = int(n)
data = setup_data(n)
print(f'n = {n}')
results = {}
for name, func in list(globals().items()):
if not name.startswith('f_') or not isinstance(func, types.FunctionType):
continue
print("{:16s}{:16.8f} ms".format(name[2:], timeit(
'results[name] = f(**data)', globals={'f':func, 'data':data, 'results':results, 'name':name}, number=10)*100))
for r in results:
print('{:10}: {}'.format(r, sorted(list(results[r]))[:5]))数组查找方法非常快（甚至比@ paul-panzer的numpy方法还快！）。当然，它作弊是因为它在完成后并未在技术上完成，因为它正在返回生成器。它也不必检查每次迭代是否已经存在该值，这可能会有所帮助。
n = 10
counter 0.10595780 ms
dict 0.01070654 ms
array 0.00135370 ms
f_counter : []
f_dict : []
f_array : []
n = 1000
counter 2.89462101 ms
dict 0.40434612 ms
array 0.00073838 ms
f_counter : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
f_dict : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
f_array : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
n = 1000000
counter 2849.00500992 ms
dict 438.44007806 ms
array 0.00135370 ms
f_counter : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]
f_dict : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]
f_array : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]回答 9
图片作为答案：
看起来像一个滑动窗口。
Image as answer:
Looks like a sliding window.
回答 10
这是我的解决方案：
from collections import defaultdict
string = "103264685134845354863"
d = defaultdict(int)
for elt in range(len(string)-2):
d[string[elt:elt+3]] += 1
d = {key: d[key] for key in d.keys() if d[key] > 1}在for循环中具有一些创造力（例如，带有True / False / None的附加查找列表），您应该可以摆脱最后一行，因为您只想创建一个字典，直到我们访问该点为止。希望能帮助到你 ：）
回答 11
-从C角度讲。-您可以得到一个int 3-d数组结果[10] [10] [10]; -从第0个位置转到第n-4个位置，其中n是字符串数组的大小。-在每个位置上，检查当前，下一个和下一个下一个。-将cntr增加为resutls [current] [next] [next的下一个] ++；-打印的值
results[1][2][3]
results[2][3][4]
results[3][4][5]
results[4][5][6]
results[5][6][7]
results[6][7][8]
results[7][8][9]-现在是O（n）时间，不涉及比较。-您可以在此处运行一些并行的东西，方法是对数组进行分区并计算分区之间的匹配项。
回答 12
inputStr = '123456123138276237284287434628736482376487234682734682736487263482736487236482634'
count = {}
for i in range(len(inputStr) - 2):
subNum = int(inputStr[i:i+3])
if subNum not in count:
count[subNum] = 1
else:
count[subNum] += 1
print count
