1122 votes

Simple question d'entrevue obtenu plus difficile: étant donné les numéros 1..100, trouver le nombre manquant(s)

J'ai eu une intéressante entrevue d'emploi de l'expérience d'un moment de retour. La question a commencé à vraiment facile:

Q1: Nous avons un sac contenant des numéros 1, 2, 3, ..., 100. Chaque chiffre apparaisse exactement une fois, il y a donc 100 numéros. Maintenant, un nombre est choisi au hasard dans le sac. Trouver le nombre manquant.

J'ai entendu cette question d'entrevue avant, bien sûr, j'ai donc très rapidement répondu le long des lignes de:

A1: eh Bien, la somme des nombres 1 + 2 + 3 + … + N est (N+1)(N/2) (voir Wikipédia: somme arithmétique de la série). Pour N = 100, la somme est 5050.

Ainsi, si tous les nombres sont présents dans le sac, la somme sera exactement 5050. Depuis un certain nombre est manquant, la somme sera de moins que cela, et la différence est de ce nombre. Ainsi, nous pouvons trouver que le nombre manquant de O(N) du temps et O(1) de l'espace.

À ce stade, je pensais que j'avais bien fait, mais tout à coup, la question a pris une tournure inattendue:

Q2: C'est exact, mais maintenant, comment voulez-vous faire si les DEUX numéros sont manquants?

Je n'avais jamais vu/entendu/a considéré que cette variation avant, alors j'ai paniqué et je ne pouvais pas répondre à la question. L'interviewer a insisté sur le fait de savoir mon processus de pensée, donc je l'ai mentionné que peut-être nous pouvons obtenir plus d'informations par une comparaison avec le produit escompté, ou peut-être faire un deuxième passage après avoir rassemblé quelques informations de la première passe, etc, mais j'ai vraiment été juste des photos dans le noir plutôt que de réellement avoir une voie claire vers la solution.

L'intervieweur n'a essayer de m'encourager en disant que le fait d'avoir un deuxième équation est en effet une manière de résoudre le problème. À ce point, j'étais un peu en colère contre (pour ne pas connaître la réponse avant de la main), et a demandé si ce est un général (lire: "utile") technique de programmation, ou si c'est juste un truc/gotcha réponse.

L'interviewer réponse m'a surpris: vous pouvez généraliser la technique pour trouver 3 nombres manquants. En fait, vous pouvez généraliser pour trouver les k nombres manquants.

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

C'était il y a quelques mois, et je ne pouvais toujours pas à comprendre ce que cette technique est. Évidemment il y a un Ω(N) du temps limite inférieure puisque nous devons parcourir tous les nombres au moins une fois, mais l'intervieweur a insisté pour que le TEMPS et l'ESPACE de la complexité de la résolution de la technique (moins de la O(N) du temps d'entrée de balayage) est définie dans k pas N.

Donc la question est simple:

  • Comment voulez-vous résoudre T2?
  • Comment voulez-vous résoudre T3?
  • Comment voulez-vous résoudre Qk?

Précisions

  • Généralement, il y a N nombres à partir de 1..N, pas juste 1..100.
  • Je ne suis pas à la recherche de l'évidence, basés sur la solution, par exemple à l'aide d'un ensemble de bits, codage de la présence/absence de chaque nombre par la valeur d'un bit, par conséquent, à l'aide de O(N) bits de l'espace supplémentaire. Nous ne pouvons nous permettre un espace supplémentaire proportionnelle à N.
  • Je ne suis pas à la recherche de l'évidence de tri-première approche. Le présent et l'approche fondée sur vaut la peine de mentionner dans une interview (ils sont faciles à mettre en œuvre, et en fonction de N, peut être très pratique). Je suis à la recherche du Saint Graal de la solution (qui peut ou peut ne pas être pratique à mettre en œuvre, mais a souhaité asymptotique caractéristiques néanmoins).

Encore une fois, bien sûr, vous devez analyser l'entrée en O(N), mais vous ne pouvez capturer petite quantité d'informations (en termes de k pas de N), et il faut alors trouver les k nombres manquants en quelque sorte.

579voto

sdcvvc Points 14968

Voici un résumé de Dimitris Andreou du lien.

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

a1 + a2 + ... + ak = b1

un12 + 22 + ... + k2 = b2

...

un1k + 2k + ... + kk = bk

À l'aide de Newton identités, sachant bi permet de calculer

c1 = a1 + a2 + ... k

c2 = a1a2 + a1a3 + ... + k-1unk

...

ck = a1a2 ... k

Si vous développez le polynôme (x-1)...(x-k) les coefficients seront exactement c1, ..., ck - voir les formules de Viète. Étant donné que chaque polynôme facteurs unique (l'anneau de polynômes est un Euclidienne de domaine), cela signifie quej'ai sont déterminée de manière unique, jusqu'à la permutation.

C'est la fin d'une preuve que se souvenir de pouvoirs suffit de récupérer le nombre. Pour la constante k, c'est une bonne approche.

Toutefois, lorsque k est variable, la méthode directe de calcul de c1,...,ck est prohibitely cher, depuis par exemple ck est le produit de tous les nombres manquants, ordre n!/(n-k)!. Pour remédier à cela, effectuer des calculs dans Z,q champ, où q est un nombre premier tel que n <= q < 2n - il existe par Bertrand du postulat. La preuve n'a pas besoin d'être changé, puisque les formules tiennent toujours, et la factorisation de polynômes est encore unique. Vous avez également besoin d'un algorithme de factorisation sur les corps finis, par exemple celui de Berlekamp ou de Cantor-Zassenhaus.

Haut niveau pseudo-code de la constante k:

  • Calculer i-ème de puissances de nombres donnés
  • Soustraire pour obtenir des sommes d'i-ème pouvoirs de numéros inconnus. Appelez les sommes bje.
  • Utiliser les identités de Newton pour calculer les coefficients de bi; appeler cje. Fondamentalement, c1 = b1; c2 = (c1b1 - b2)/2; voir Wikipedia pour des formules exactes
  • Factoriser le polynôme xk-c1xk-1 + ... + ck.
  • Les racines du polynôme sont les numéros nécessaires un1, ..., k.

Pour varier k, trouver un nombre premier n <= q < 2n par exemple à l'aide de Miller-Rabin, et effectuez les étapes avec tous les numéros de réduction modulo q.

Comme Heinrich Apfelmus commenté, au lieu d'un nombre premier q vous pouvez utiliser pour q=2⌈log n⌉ et effectuer l'arithmétique de galois.

238voto

Dimitris Andreou Points 5398

Vous le trouverez en lisant les quelques pages de Muthukrishnan - Flux de Données Algorithmes: Puzzle 1: Trouver les Numéros Manquants. Cela montre exactement la généralisation que vous êtes à la recherche pour. C'est probablement ce que votre interlocuteur lire, et pourquoi il a posé ces questions.

Maintenant, si seulement les gens commencent à supprimer les réponses qui sont regroupés ou remplacée par Muthukrishnan du traitement, et de rendre ce texte plus facile à trouver. :)

Voir aussi sdcvvc est directement liée réponse, qui comprend également des pseudo-code (hourra! pas besoin de lire ces délicates formulations mathématiques :)) (merci, excellent travail!).

171voto

Anon. Points 26829

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

On peut alors réduire le problème à

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

x et y sont dans quelle mesure les sommes sont inférieures aux valeurs attendues.

En substituant nous donne:

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

Qui ensuite, nous pouvons résoudre pour déterminer nos numéros manquants.

136voto

caf Points 114951

@J_random_hacker signalé, c'est tout à fait similaire à Trouver les doublons en O(n) en temps et O(1) de l'espace, et une adaptation de ma réponse, il fonctionne ici aussi.

En supposant que le "sac" est représenté par un 1-tableau de base A[] de la taille de l' N - k, nous pouvons résoudre Qk en O(N) du temps et O(k) d'espace supplémentaire.

Tout d'abord, nous prolongeons notre tableau A[] par k éléments, de sorte qu'il est maintenant de la taille de l' N. C'est l' O(k) d'espace supplémentaire. Nous avons ensuite exécuter le pseudo-code de l'algorithme:

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 if
end for

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

La première boucle initialise l' k entrées supplémentaires pour la même que la première entrée dans le tableau (c'est juste une pratique de la valeur que nous savons, c'est déjà présente dans le tableau - après cette étape, toutes les entrées manquantes dans la table initiale de la taille de l' N-k sont toujours portées disparues dans la gamme étendue).

La deuxième boucle permute la gamme étendue de sorte que si l'élément x est présent au moins une fois, puis une de ces inscriptions seront à la position A[x].

Notez que même si il a une boucle imbriquée, il fonctionne encore en O(N) du temps - un swap se produit uniquement si il y a un i tels que A[i] != i, et chaque swap définit au moins un élément tel que A[i] == i, alors que ce n'était pas le cas auparavant. Cela signifie que le nombre total de swaps (et donc le nombre total d'exécutions de l' while corps de boucle) est au plus N-1.

La troisième boucle imprime ces index du tableau i qui ne sont pas occupés par la valeur i - i doit avoir été absent.

123voto

Colonel Panic Points 18390

J'ai demandé à un enfant de 4 ans pour résoudre ce problème. Il a trié les nombres, puis comptés. Cela a un besoin d'espace de O(plancher de la cuisine), et il fonctionne tout aussi facile cependant de nombreuses balles sont manquants.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X