its*_*vid 137 python algorithm number-theory data-structures
几个月前我在纽约接受了一家对冲基金公司的采访,不幸的是,我没有获得数据/软件工程师的实习机会.(他们还要求解决方案使用Python.)
我几乎搞砸了第一个面试问题......
问题:给定一个百万个数字的字符串(例如Pi),写一个函数/程序,返回所有重复的3位数字和大于1的重复次数
例如:如果字符串是:123412345123456那么函数/程序将返回:
123 - 3 times
234 - 3 times
345 - 2 times
我在面试失败后没有给我解决方案,但他们确实告诉我,解决方案的时间复杂度始终为1000,因为所有可能的结果都在:
000 - > 999
既然我正在考虑它,我认为不可能提出一个恒定的时间算法.是吗？
pax*_*blo 167
你被从轻发落了,你可能不希望被工作了对冲基金在金融工程师不懂基本的算法:-)
如果在这种情况下,您需要至少访问一次每个元素,则无法处理任意大小的数据结构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秒.
而且,如果他们需要更好的东西,有办法将这种东西并行化,这可以大大加快速度.
当然不是在单个 Python解释器中,由于GIL,但是你可以将字符串拆分成类似的东西(需要重叠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;
}
rcg*_*ldr 78
不可能有恒定的时间.所有100万个数字至少需要查看一次,因此这是O(n)的时间复杂度,在这种情况下n = 100万.
对于简单的O(n)解决方案,创建一个大小为1000的数组,表示每个可能的3位数的出现次数.一次前进1位,第一个索引== 0,最后一个索引== 999997,并增加数组[3位数字]以创建直方图(每个可能的3位数字的出现次数).然后输出计数> 1的数组的内容.
Dan*_*iel 14
简单的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.
Pad*_*118 14
对于我在下面给出的答案,一百万是小的.期望您必须能够在面试中运行解决方案,而不会暂停,然后以下工作在不到两秒钟内完成并提供所需的结果:
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)
希望面试官会寻找标准库集合的使用.计数器类.
我写了一篇博文,附有更多解释.
Pau*_*zer 10
这是"共识"O(n)算法的NumPy实现:随你走过所有三元组和bin.通过在遇到说"385"时完成分箱,将一个加到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