Алгоритм головоломки интервью

Ответ 1

"Подпоследовательность" обычно означает несмежность. Я собираюсь предположить, что вы имели в виду "подсписку".

Здесь используется алгоритм O (N P) , предполагающий, что мы можем hash (предположение не нужно, мы можем вместо этого отсортировать сортировку). Сканируйте массив, сохраняя общее количество для каждого номера. Для вашего примера

  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-м.

Это работает, потому что подсписчик сбалансирован тогда и только тогда, когда его первая и последняя ненормализованные гистограммы совпадают до добавления константы, которая возникает тогда и только тогда, когда первая и последняя нормализованные гистограммы идентичны.

Ответ 2

Если использование памяти не важно, легко...

Вы можете указать размеры матрицы N*p и сохранить в столбце (i) значение, соответствующее количеству элементов p, между (i) элемент во втором векторе...

После завершения матрицы вы можете найти столбец i, что все элементы в столбце i не отличаются друг от друга. Максимальный i - это ответ.

Ответ 3

При рандомизации вы можете получить ее до линейного времени. Идея состоит в том, чтобы заменить каждое из значений 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]]+B-s)%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 j-i 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] > j-i:
            (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."

Ответ 4

Вот замечание: вы не можете получить равномерно распределенную последовательность, которая не является умножением длины P. Это означает, что вам нужно только проверить подпоследовательности N, которые P, 2P, 3P... long - (N/P)^2 такие последовательности.

Ответ 5

Вы можете получить это до O (N) времени, не зависимо от P, увеличивая утиное решение.

Для каждой строки вместо хранения нормализованных счетчиков каждого элемента хранится хэш нормализованных счетчиков, а только сохраняются нормализованные счетчики для текущего индекса. Во время каждой итерации вам нужно сначала обновить нормализованные счета, которые имеют амортизированную стоимость O (1), если каждый декремент счета оплачивается, когда он увеличивается. Затем вы пересчитаете хэш. Ключевым моментом здесь является то, что хэш должен быть легко обновляемым после инкремента или уменьшения одного из элементов хешируемого кортежа.

Как минимум один из способов эффективного хэширования, с хорошими теоретическими гарантиями независимости, показан в ответе на этот вопрос. Обратите внимание, что стоимость O (lg P) для вычисления экспоненты для определения суммы, добавляемой в хеш, может быть устранена путем предварительного вычисления экспонентов по модулю простого числа с полным временем работы O (P) для предвычисления, что дает общую сумму время работы O (N + P) = O (N).