Entretien d'algorithme

Question

J'ai trouvé cette interview en question, et je ne pouvais pas venir avec un algorithme de mieux que O(N^2 * P):

Étant donné un vecteur de P nombres naturels (1,2,3,...,P) et un vecteur de longueur N dont les éléments sont du premier vecteur, à trouver la plus longue sous-suite dans le deuxième vecteur tel que tous les éléments sont distribués de manière uniforme (ont la même fréquence).

Exemple : (1,2,3) et (1,2,1,3,2,1,3,1,2,3,1). La plus longue sous-suite est dans l'intervalle [2,10], car il contient tous les éléments de la première séquence avec la même fréquence (1 apparaît trois fois, 2 fois, trois fois, et 3 trois fois).

La complexité du temps devrait être O(N * P).

Answer 1

"La" signifie généralement non contigus. Je vais supposer que vous avez voulu dire "sous-liste".

Voici un O(N P) algorithme en supposant que l'on peut hachage (hypothèse qui n'est pas nécessaire; on peut radix de tri à la place). Analyse le tableau en gardant un total cumulé pour chaque numéro. Pour ton exemple,

  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

Maintenant, la normalisation de chaque ligne par la soustraction de l'élément minimum. Le résultat est

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

Préparer deux hachages, la cartographie de chaque ligne dans le premier index dans lequel il apparaît et le dernier index dans lequel il apparaît. Itérer sur les touches et de prendre celui avec le maximum de dernier - premier.

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 meilleure clé est de 100, depuis sa sous-liste a une longueur de 9. La sous-liste de l ' (1+1)ème élément de la 10e.

Cela fonctionne parce qu'un sous-liste est équilibré si et seulement si son premier et dernier unnormalized histogrammes sont les mêmes jusqu'à l'ajout d'une constante, ce qui se produit si et seulement si la première et la dernière forme d'histogrammes normalisés sont identiques.

Answer 2

Si l'utilisation de la mémoire n'est pas important, c'est facile...

Vous pouvez donner la matrice de dimensions N*p et l'enregistrer dans la colonne (i) la valeur correspond à la manière dont de nombreux éléments p est à la recherche entre (i)le premier élément dans le second vecteur...

Après l'achèvement de la matrice, vous pouvez rechercher colonne i que tous les éléments de la colonne i ne sont pas différents. Le maximum i est la réponse.

Answer 3

Avec la randomisation, vous pouvez le réduire au temps linéaire. L'idée est de remplacer chacune des P valeurs par un entier aléatoire, tel que la somme de ces entiers soit égale à zéro. Recherchez maintenant deux sommes de préfixe égales. Cela laisse une petite chance de faux positifs, auxquels nous pourrions remédier en vérifiant notre sortie.

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

Voici un constat: vous ne pouvez pas obtenir une séquence uniformément distribuée qui ne soit pas une multiplication de longueur P . Cela implique que vous ne devez vérifier que les sous-séquences de N qui sont P , 2P , 3P ... long - (N/P)^2 telles séquences.

Answer 5

Vous pouvez obtenir cette baisse à O(N) du temps, avec une dépendance sur P par le renforcement de la uty de la solution.

Pour chaque ligne, au lieu de stocker l'normalisé le nombre de chaque élément, de stocker une table de hachage de l'normalisé compte tout en ne conservant que les normalisé compte pour l'indice actuel. Lors de chaque itération, vous devez d'abord mettre à jour le normalisée compte, ce qui a un coût non amorti O(1) si chaque décrémentation d'un compteur est payé quand il est incrémenté. Ensuite, vous recalculer la valeur de hachage. La clé ici est que le hachage doit être facilement mis à jour à la suite d'une incrémentation ou de décrémentation de l'un des éléments du tuple qui est haché.

Au moins une façon de faire de hachage de manière efficace, avec une bonne théorique de l'indépendance des garanties est indiqué dans la réponse à cette question. Notez que le O(lg P) de coûts pour le calcul de l'exponentielle pour déterminer le montant à ajouter à la valeur de hachage peut être éliminé par precomputing les exponentielles modulo, le premier avec un temps de fonctionnement total de O(P) pour le précalcul, donnant un temps de fonctionnement total de O(N + P) = O(N).