Question La question de l'entrevue facile devient plus difficile: les nombres donnés 1..100, trouver le nombre manquant (s)


J'ai eu une expérience d'entretien d'embauche intéressante il y a quelque temps. La question a commencé vraiment facile:

Q1: Nous avons un sac contenant des chiffres 1, 2, 3, ..., 100. Chaque nombre apparaît exactement une fois, il y a donc 100 nombres. Maintenant, un numéro est choisi au hasard dans le sac. Trouvez le nombre manquant.

J'ai entendu cette question d'entrevue avant, bien sûr, alors j'ai très rapidement répondu comme suit:

A1: Eh bien, la somme des nombres 1 + 2 + 3 + … + N est (N+1)(N/2) (voir Wikipedia: somme des séries arithmétiques). Pour N = 100, la somme est 5050.

Ainsi, si tous les numéros sont présents dans le sac, la somme sera exactement 5050. Puisqu'un nombre est manquant, la somme sera inférieure à ceci, et la différence est ce nombre. Nous pouvons donc trouver ce nombre manquant dans O(N) temps et O(1) espace.

À ce stade, je pensais que j'avais bien fait, mais tout à coup la question a pris un tour inattendu:

Q2: C'est correct, mais maintenant, comment feriez-vous cela si DEUX les numéros manquent?

Je n'avais jamais vu / entendu / considéré cette variation auparavant, alors j'ai paniqué et je n'ai pas pu répondre à la question. L'intervieweur a insisté pour connaître mon processus de pensée, alors j'ai mentionné que nous pourrions peut-être obtenir plus d'informations en comparant avec le produit attendu, ou peut-être en faisant une deuxième fois après avoir recueilli des informations du premier passage, etc. dans le noir plutôt que d'avoir un chemin clair vers la solution.

L'intervieweur a essayé de m'encourager en disant qu'une deuxième équation est en fait une façon de résoudre le problème. À ce stade, j'étais un peu contrarié (pour ne pas connaître la réponse avant la main), et je lui ai demandé s'il s'agissait d'une technique de programmation générale (lire: "utile") ou si c'était juste une réponse.

La réponse de l'intervieweur m'a surpris: vous pouvez généraliser la technique pour trouver 3 nombres manquants. En fait, vous pouvez le généraliser pour trouver k numéros manquants.

Qk: Si exactement k les numéros manquent dans le sac, comment le trouveriez-vous efficacement?

C'était il y a quelques mois, et je n'arrivais toujours pas à comprendre ce qu'est cette technique. De toute évidence, il y a un Ω(N) limite inférieure de temps puisque nous devons balayer tous les nombres au moins une fois, mais l'interviewer a insisté pour que le TEMPS et ESPACE complexité de la technique de résolution (moins la O(N) balayage d'entrée de temps) est défini dans k ne pas N.

Donc la question ici est simple:

  • Comment résoudriez-vous Q2?
  • Comment résoudriez-vous Q3?
  • Comment résoudriez-vous Qk?

Clarifications

  • Généralement, il y a N numéros de 1 ..N, pas seulement 1..100.
  • Je ne cherche pas la solution basée sur des ensembles évidents, par ex. utilisant un jeu de bits, codant la présence / l'absence de chaque nombre par la valeur d'un bit désigné, utilisant ainsi O(N)bits dans l'espace supplémentaire. Nous ne pouvons pas nous permettre un espace supplémentaire proportionnel à N.
  • Je ne suis pas non plus à la recherche de la première approche évidente. Ceci et l'approche basée sur les ensembles méritent d'être mentionnés dans une interview (ils sont faciles à mettre en œuvre, et en fonction de N, peut être très pratique). Je suis à la recherche de la solution Holy Grail (qui peut ou non être pratique à mettre en œuvre, mais qui possède néanmoins les caractéristiques asymptotiques souhaitées).

Encore une fois, bien sûr, vous devez scanner l'entrée dans O(N), mais vous ne pouvez capturer qu'une petite quantité d'informations (définie en termes de k ne pas N), et doit ensuite trouver k numéros manquants en quelque sorte.


983
2017-08-16 10:26


origine


Réponses:


Voici un résumé de Dimitris Andreou's lien.

Rappelez-vous la somme des puissances i-ième, où i = 1,2, .., k. Cela réduit le problème à résoudre le système d'équations

une1 + a2 + ... + ak = b1

une12 + a22 + ... + ak2 = b2

...

une1k + a2k + ... + akk = bk

En utilisant Les identités de Newton, sachant bje permet de calculer

c1 = a1 + a2 + ... ak

c2 = a1une2 + a1une3 + ... + ak-1unek

...

ck = a1une2 ... unek

Si vous développez le polynôme (x-a1) ... (x-ak) les coefficients seront exactement c1, ..., ck - voir Les formules de Viète. Puisque chaque facteur polynomial est unique (anneau de polynômes est un Domaine euclidien), cela signifieje sont déterminés de manière unique, jusqu'à la permutation.

Ceci termine une preuve que le rappel des pouvoirs est suffisant pour récupérer les nombres. Pour k constant, c'est une bonne approche.

Cependant, lorsque k varie, l'approche directe de l'informatique c1, ..., ck est prohibitivement coûteux, puisque par ex. ck est le produit de tous les nombres manquants, magnitude n! / (n-k) !. Pour surmonter cela, effectuez des calculs en Zq champ, où q est un premier tel que n <= q <2n - il existe par Le postulat de Bertrand. La preuve n'a pas besoin d'être modifiée, puisque les formules sont toujours valables, et la factorisation des polynômes est toujours unique. Vous avez également besoin d'un algorithme de factorisation sur des corps finis, par exemple celui par Berlekamp ou Cantor-Zassenhaus.

Pseudo-code de haut niveau pour la constante k:

  • Calculer les i-ième puissances de nombres donnés
  • Soustraire pour obtenir des sommes de puissance i-ème de nombres inconnus. Appelez les sommes bje.
  • Utiliser les identités de Newton pour calculer les coefficients de bje; appelez les cje. Fondamentalement, c1 = b1; c2 = (c1b1 - b2) / 2; voir Wikipedia pour les formules exactes
  • Factor le polynôme xk-c1Xk-1 + ... + ck.
  • Les racines du polynôme sont les nombres nécessaires a1, ..., unek.

Pour faire varier k, trouvez un nombre premier n <= q <2n en utilisant par ex. Miller-Rabin, et effectuer les étapes avec tous les nombres réduits modulo q.

Comme l'a commenté Heinrich Apfelmus, au lieu d'un q premier, vous pouvez utiliser q = 2⌉log n⌉ et effectuer arithmétique en champ fini.


512
2017-08-16 12:13



Vous le trouverez en lisant les quelques pages de Muthukrishnan - Algorithmes de flux de données: Puzzle 1: Trouver des numéros manquants. Il montre exactement la généralisation que vous recherchez. Probablement c'est ce que votre interviewer a lu et pourquoi il a posé ces questions.

Maintenant, si seulement les gens commençaient à supprimer les réponses qui sont subsumées ou remplacées par le traitement de Muthukrishnan, et à rendre ce texte plus facile à trouver. :)


Regarde aussi sdcvvc réponse directement liée, qui inclut également le pseudocode (hourra! pas besoin de lire ces formules mathématiques compliquées :)) (merci, bon travail!).


226
2017-08-16 11:26



Nous pouvons résoudre Q2 en additionnant les nombres eux-mêmes, et le carrés des nombres.

Nous pouvons alors réduire le problème à

k1 + k2 = x
k1^2 + k2^2 = y

x et y sont dans quelle mesure les sommes sont en dessous des valeurs attendues.

Substituer nous donne:

(x-k2)^2 + k2^2 = y

Ce que nous pouvons ensuite résoudre pour déterminer nos numéros manquants.


159
2017-08-16 10:37



Comme l'a souligné @j_random_hacker, c'est assez similaire à Trouver des doublons en temps O (n) et O (1)et une adaptation de ma réponse fonctionne ici aussi.

En supposant que le "sac" est représenté par un tableau basé sur 1 A[] de taille N - k, nous pouvons résoudre Qk dans O(N) temps et O(k) espace supplémentaire.

D'abord, nous étendons notre tableau A[] par k éléments, de sorte qu'il est maintenant de taille N. C'est le O(k) espace supplémentaire. Nous exécutons ensuite l'algorithme de pseudo-code suivant:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

La première boucle initialise le k entrées supplémentaires à la même que la première entrée dans le tableau (c'est juste une valeur pratique que nous savons est déjà présente dans le tableau - après cette étape, toutes les entrées qui manquaient dans le tableau initial de taille N-k sont toujours manquants dans le tableau étendu).

La deuxième boucle permute le tableau étendu de sorte que si l'élément x est présent au moins une fois, puis l'une de ces entrées sera en position A[x].

Notez que bien qu'il ait une boucle imbriquée, il fonctionne toujours dans O(N) temps - un échange ne se produit que s'il y a un i tel que A[i] != i, et chaque échange définit au moins un élément tel que A[i] == i, où ce n'était pas vrai avant. Cela signifie que le nombre total de swaps (et donc le nombre total d'exécutions de while corps de la boucle) est au plus N-1.

La troisième boucle imprime les index du tableau i qui ne sont pas occupés par la valeur i - cela signifie que i doit avoir été manquant.


120
2018-04-22 04:32



J'ai demandé à un enfant de 4 ans de résoudre ce problème. Il a trié les chiffres et a ensuite compté. Cela a un besoin d'espace de O (plancher de cuisine), et cela fonctionne tout aussi facilement, mais beaucoup de balles manquent.


114
2018-04-12 18:59



Pas sûr, si c'est la solution la plus efficace, mais je voudrais boucler sur toutes les entrées, et utiliser un bitset pour se souvenir, quels sont les nombres sont fixés, puis tester pour 0 bits.

J'aime les solutions simples - et je crois même, que cela pourrait être plus rapide que de calculer la somme, ou la somme des carrés, etc.


30
2017-08-16 10:38



Je n'ai pas vérifié les maths, mais je soupçonne que l'informatique Σ(n^2) dans le même passage que nous calculons Σ(n) fournirait suffisamment d'informations pour obtenir deux numéros manquants, Do Σ(n^3) aussi bien s'il y en a trois, et ainsi de suite.


29
2017-08-16 10:38