algorithm - tarda - Algoritmo rompecabezas entrevista

puzzle numerico 3x3 java

Question

Encontré esta pregunta de la entrevista y no pude encontrar un algoritmo mejor que O (N ^ 2 * P):

Dado un vector de P números naturales (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 manera que todos los elementos estén distribuidos uniformemente (tienen 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" usualmente significa no contiguo. Voy a asumir que te referías a "sublista".

Aquí hay un algoritmo O (NP) que asume que podemos hacer hash (suposición que no es necesario; en su lugar, podemos clasificar por radix). Escanee la matriz manteniendo un total acumulado para cada número. Para tu 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, normaliza 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.

Prepare dos hashes, asignando cada fila al primer índice en el que aparece y el último índice en el que aparece. Iterar a través de las teclas y tomar la una con el último ú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 la longitud 9. La sublista es el elemento (1 + 1) al décimo.

Esto funciona porque una lista secundaria está balanceada si y solo si su primer y último histogramas no normalizados 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 puede obtener una secuencia distribuida uniformemente que no sea una multiplicación de P en longitud. Esto implica que solo tiene que verificar las subsecuencias de N que son P , 2P , 3P ... largas - (N/P)^2 secuencias de este tipo.

Answer 3

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

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

Answer 4

Puede reducir esto a O (N), sin depender de P al mejorar la solución de uty.

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

En la respuesta a esta pregunta se muestra al menos una forma de hacer este hash de manera eficiente, con buenas garantías teóricas de independencia. Tenga en cuenta que el costo de O (lg P) para calcular la exponencial para determinar la cantidad que se debe agregar al hash puede eliminarse precomputando el módulo primo exponencial 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).

Answer 5

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

Puede dar a las dimensiones de la matriz N*p y guardar en la columna (i) el valor correspondiente a cuántos elementos p está mirando entre (i) primer elemento en el segundo vector ...

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