algorithm难题面试
我find了这个面试问题，我不能提出比O（N ^ 2 * P）更好的algorithm：
给定P个自然数（1,2,3，…，P）的向量和另一个长度为N的元素来自第一个向量的向量，find第二个向量中最长的子序列，使得所有元素均匀分布（具有相同的频率）。
例如：（1,2,3）和（ 1,2,1,3,2,1,3,1,2,3,1 ）。 最长的子序列在[2,10]区间中，因为它包含了第一个序列中具有相同频率的所有元素（1次出现3次，2次3次，3次3次）。
时间复杂度应该是O（N * P）。
“子序列”通常意味着不连续。 我会假设你的意思是“子列表”。
这里是一个O（NP）algorithm， 假设我们可以散列 （假设不需要;我们可以改为基数sorting）。 扫描arrays保持每个数字的运行总数。 举个例子，
1 2 3 -------- 0 0 0 1 1 0 0 2 1 1 0 1 2 1 0 3 2 1 1 2 2 2 1 1 3 2 1 3 3 2 2 1 4 2 2 2 4 3 2 3 4 3 3 1 5 3 3 现在，通过减去最小元素来标准化每一行。 结果是
0: 000 1: 100 2: 110 3: 210 4: 100 5: 110 6: 210 7: 100 8: 200 9: 210 10: 100 11: 200.
准备两个散列，将每一行映射到它出现的第一个索引和它出现的最后一个索引。 迭代通过钥匙，并采取最大的最后 – 第一个。
000: first is at 0, last is at 0 100: first is at 1, last is at 10 110: first is at 2, last is at 5 210: first is at 3, last is at 9 200: first is at 8, last is at 11
最好的关键是100，因为它的子列表长度为9.子列表是第（1 + 1）个元素到第10个元素。
这是有效的，因为子列表是平衡的，当且仅当它的第一个和最后一个非标准直方图是相同的，直到增加一个常数，当且仅当第一个和最后一个标准化直方图是相同的。
如果内存使用不重要，很容易…
你可以给出matrix维数N*p并且保存在列（i）中对应于多less个元素p在（i）第二个向量中的第一个元素之间寻找的值…
在完成matrix之后，可以search列i中列i中所有元素都不相同的元素。 最大的i是答案。
随机化，你可以把它降到线性时间。 这个想法是用一个随机整数来replace每个P值，使得那些整数和为零。 现在查找两个相等的前缀总和。 这使得一些小错误的机会，我们可以通过检查我们的输出来弥补。
在Python 2.7中：
# input: vec1 = [1, 2, 3] P = len(vec1) vec2 = [1, 2, 1, 3, 2, 1, 3, 1, 2, 3, 1] N = len(vec2) # Choose big enough integer B. For each k in vec1, choose # a random mod-B remainder r[k], so their mod-B sum is 0. # Any P-1 of these remainders are independent. import random B = N*N*N r = dict((k, random.randint(0,B-1)) for k in vec1) s = sum(r.values())%B r[vec1[0]] = (r[vec1[0]]+Bs)%B assert sum(r.values())%B == 0 # For 0<=i<=N, let vec3[i] be mod-B sum of r[vec2[j]], for j<i. vec3 = [0] * (N+1) for i in range(1,N+1): vec3[i] = (vec3[i-1] + r[vec2[i-1]]) % B # Find pair (i,j) so vec3[i]==vec3[j], and ji is as large as possible. # This is either a solution (subsequence vec2[i:j] is uniform) or a false # positive. The expected number of false positives is < N*N/(2*B) < 1/N. (i, j)=(0, 0) first = {} for k in range(N+1): v = vec3[k] if v in first: if k-first[v] > ji: (i, j) = (first[v], k) else: first[v] = k # output: print "Found subsequence from", i, "(inclusive) to", j, "(exclusive):" print vec2[i:j] print "This is either uniform, or rarely, it is a false positive."
这是一个观察：你不能得到一个统一的分布序列，不是P的长度的乘法。 这意味着你只需要检查N ， P ， 2P ， 3P … long – (N/P)^2这样的序列的子序列。
你可以把它降到O（N）时间，通过增强uty的解决scheme，不依赖于P.
对于每一行，不是存储每个元素的标准化计数，而是存储标准化计数的散列，而只保留当前索引的标准化计数。 在每次迭代期间，您需要首先更新归一化计数，如果递增计数的每个递减次数，则计算O（1）的摊销成本。 接下来你重新计算哈希。 这里的关键是哈希需要容易更新之后，正在被哈希的元组的一个元素的增量或减量。
在这个问题的答案中，至less有一种有效的散列方式，具有良好的理论独立性。 请注意，计算指数以确定添加到散列的数量的O（lg P）成本可以通过预先计算指数的模数，用预计算的总运行时间O（P）预先计算，运行时间O（N + P）= O（N）。
