Algoritmo entrevista rompecabezas

Question

encontré esta pregunta de la entrevista, y no podía llegar a un algoritmo mejor que O (N^2 * P):

Dado un vector de números naturales P (1,2 , 3, ..., P) y otro vector de longitud N cuyos elementos son del primer vector, encuentre la subsecuencia más larga en el segundo vector, de modo que todos los elementos estén uniformemente distribuidos (tengan la misma frecuencia).

Ejemplo: (1,2,3) y (1, 2,1,3,2,1,3,1,2,3, 1). La subsecuencia más larga está en el intervalo [2,10], porque contiene todos los elementos de la primera secuencia con la misma frecuencia (1 aparece tres veces, 2 tres veces y 3 tres veces).

La complejidad del tiempo debe ser O (N * P).

Answer 1

"Subsecuencia" generalmente significa no contiguo. Voy a suponer que querías decir "sublista".

Aquí hay un algoritmo O (N P) suponiendo que podemos hash (suposición no es necesaria, podemos ordenar radix en su lugar). Escanee la matriz manteniendo un total acumulado para cada número. Para su ejemplo,

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 

Ahora, normalice cada fila restando el elemento mínimo. El resultado es

0: 000 
1: 100 
2: 110 
3: 210 
4: 100 
5: 110 
6: 210 
7: 100 
8: 200 
9: 210 
10: 100 
11: 200. 

preparar dos hashes, la cartografía de cada fila para el primer índice en el que aparece, el último índice en el que aparece. Itera a través de las teclas y toma la que tenga el máximo, el último - primero.

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 

La mejor clave es 100, ya que su sublista tiene longitud 9. La lista secundaria es la (1 + 1) -ésimo elemento de la 10a.

Esto funciona porque una sublista está balanceada si y solo si su primer y último histograma no normalizado son los mismos hasta agregar una constante, lo que ocurre si y solo si el primer y último histograma normalizado son idénticos.

Answer 2

Aquí hay una observación: no se puede obtener una secuencia uniformemente distribuida que no sea una multiplicación de P de longitud. Esto implica que solo tiene que comprobar las subsecuencias de N que son P, 2P, 3P ... long - (N/P)^2 tales secuencias.

Answer 3

Si el uso de la memoria no es importante, es fácil ...

Usted puede dar a las dimensiones de la matriz N*p y guardar en la columna (i) el valor correspondiente a la cantidad de elementos p está buscando entre (i) primer elemento en el segundo vector ...

Después de completar la matriz, puede buscar en la columna i que todos los elementos en la columna i no son diferentes. El máximo i es la respuesta.

Answer 4

Con aleatorización, puede bajarlo al tiempo lineal. La idea es reemplazar cada uno de los valores P con un entero aleatorio, de modo que esos enteros sumen a cero.Ahora busque dos sumas de prefijo que sean iguales. Esto permite una pequeña posibilidad de falsos positivos, que podríamos remediar comprobando nuestra salida.

En Python 2.7: tiempo

# 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." 

Answer 5

Usted puede conseguir esto a O (N), sin dependencia de P mediante la mejora de la solución de UTY.

Para cada fila, en lugar de almacenar los recuentos normalizados de cada elemento, almacene un hash de los recuentos normalizados, manteniendo solo los recuentos normalizados para el índice actual. Durante cada iteración, primero necesita actualizar los recuentos normalizados, que tienen un costo amortizado de O (1) si se paga cada disminución de un recuento cuando se incrementa. A continuación, vuelve a calcular el hash. La clave aquí es que el hash necesita ser fácilmente actualizable luego de un incremento o disminución de uno de los elementos de la tupla que se está procesando.

Al menos una forma de hacer esto de manera eficiente, con buenas garantías de independencia teórica se muestra en la respuesta al this question. Obsérvese que el costo de O (lg P) para calcular la exponencial para determinar la cantidad que se agregará al hash puede eliminarse precomputando el módulo exponencial en primo con un tiempo de ejecución total de O (P) para la precomputación, dando un total tiempo de ejecución de O (N + P) = O (N).