python - structures - 给定一百万个数字的字符串,返回所有重复的3位数字




python leetcode (9)

- 从C.的角度讲 - 你可以有一个int 3-d数组结果[10] [10] [10]; - 从第0位到第4位,其中n是字符串数组的大小。 - 在每个位置,检查当前,下一个和下一个下一个。 - 将cntr增加为resutls [current] [next] [next's 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)时间,没有涉及比较。 - 你可以通过分区数组和计算分区周围的匹配来运行一些并行的东西。

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

我几乎搞砸了第一个面试问题......

问题:给定一个百万个数字的字符串(例如Pi),写一个函数/程序,返回所有重复的3位数字和大于1的重复次数

例如:如果字符串是: 123412345123456 那么函数/程序将返回:

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

我在面试失败后没有给我解决方案,但他们确实告诉我,解决方案的时间复杂度始终为1000,因为所有可能的结果都在:

000 - > 999

既然我正在考虑它,我认为不可能提出一个恒定的时间算法。 是吗?


不可能有恒定的时间。 所有100万个数字至少需要查看一次,因此这是O(n)的时间复杂度,在这种情况下n = 100万。

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


图像作为答案:

看起来像一个滑动窗口。


对于我在下面给出的答案,一百万是小的。 期望您必须能够在面试中运行解决方案,而不会暂停,然后以下工作在不到两秒钟内完成并提供所需的结果:

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)

希望面试官会寻找标准库集合的使用。计数器类。

并行执行版本

我写了 一篇博文 ,附有更多解释。


根据我的理解,你无法在一个恒定的时间内获得解决方案。 至少需要一次通过百万位数字(假设它是一个字符串)。 您可以对百万个长度数字的数字进行3位滚动迭代,如果已经存在,则将散列密钥的值增加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的键。


正如另一个答案中所提到的,你不能在恒定时间内完成这个算法,因为你必须至少看n个数字。 线性时间是您可以获得的最快速度。

但是,该算法可以在O(1) 空间中完成 。 您只需要存储每个3位数的计数,因此您需要一个包含1000个条目的数组。 然后,您可以在中输入号码。

我的猜测是,当他们给你解决方案时,面试官是错误的,或者当他们说“恒定空间”时你听错了“恒定时间”。


这是“共识”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

这是我的答案:

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

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




number-theory