Algoritmo intervista di puzzle

Question

Ho trovato questa domanda intervista, e non riuscivo a trovare un algoritmo migliore di O (N^2 * P):

Dato un vettore di numeri naturali P (1,2 , 3, ..., P) ed un altro vettore di lunghezza N i cui elementi sono dal primo vettore, per sottosequenza più lungo del secondo vettore, in modo che tutti gli elementi sono distribuiti uniformemente (hanno la stessa frequenza).

Esempio: (1,2,3) e (1, 2,1,3,2,1,3,1,2,3, 1). La sottosequenza più lunga è nell'intervallo [2,10], perché contiene tutti gli elementi della prima sequenza con la stessa frequenza (1 appare tre volte, 2 tre volte e 3 tre volte).

La complessità tempo dovrebbe essere O (N * P).

Answer 1

"Subsequence" di solito significa non contigui. Immaginerò che intendevi "sublimare".

Ecco un algoritmo O (N P) supponendo che possiamo hash (supposizione non necessaria, possiamo invece ordinare invece). Scansiona l'array mantenendo un totale parziale per ogni numero. Per il tuo esempio,

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 

Ora, normalizzare ogni riga sottraendo l'elemento minimo. Il risultato è

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

Preparare due hash, mappando ciascuna fila al primo indice in cui appare e l'ultimo indice in cui appare. Scorri i tasti e prendi quello con l'ultimo massimo - prima.

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 chiave migliore è 100, dal suo elenco secondario ha lunghezza 9. La sottolista è il (1 + 1) esimo elemento al 10 °.

Questo funziona perché una sottolista è bilanciata se e solo se il suo primo e l'ultimo istogramma non normalizzato sono uguali fino all'aggiunta di una costante, che si verifica se e solo se il primo e l'ultimo istogramma normalizzato sono identici.

Answer 2

Ecco un'osservazione: non è possibile ottenere una sequenza uniformemente distribuito che non è una moltiplicazione di P di lunghezza. Ciò implica che si deve solo controllare i sub-sequenze di N che sono P, 2P, 3P ... Long - (N/P)^2 tali sequenze.

Answer 3

Se l'utilizzo della memoria non è importante, è facile ...

Si può dare la dimensione della matrice N*p e salvare nella colonna (i) il valore corrispondente al numero di elementi p sta cercando tra (i) primo elemento del secondo vettore ...

Dopo aver completato la matrice, è possibile cercare per la colonna i che tutti gli elementi nella colonna i non sono diversi. Il massimo i è la risposta.

Answer 4

Con randomizzazione, si può ottenere fino al tempo lineare. L'idea è di sostituire ciascuno dei valori P con un numero intero casuale, tale che tali numeri interi si sommano a zero.Ora cerca due somme di prefisso uguali. Ciò consente alcune piccole possibilità di falsi positivi, che potremmo porre rimedio controllando il nostro output.

In 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 5

È possibile ottenere questo fino a O (n), senza alcuna dipendenza da P, migliorando la soluzione di uty.

Per ogni riga, invece di memorizzare i conteggi normalizzati di ciascun elemento, memorizzare un hash dei conteggi normalizzati mantenendo solo i conteggi normalizzati per l'indice corrente. Durante ogni iterazione, è necessario prima aggiornare i conteggi normalizzati, che ha un costo ammortizzato di O (1) se viene pagato ogni decremento di un conteggio quando viene incrementato. Quindi ricalcoli l'hash. La chiave qui è che l'hash deve essere facilmente aggiornabile dopo un incremento o decremento di uno degli elementi della tupla che viene sottoposta a hash.

Almeno un modo per eseguire questo hashing in modo efficiente, con buone garanzie di indipendenza teorica è mostrato nella risposta a this question. Si noti che il costo di O (lg P) per calcolare l'esponenziale per determinare la quantità da aggiungere all'hash può essere eliminato precalcolando il modulo esponenziale il primo con un tempo di esecuzione totale di O (P) per il precomputo, dando un totale tempo di esecuzione di O (N + P) = O (N).