Question d'entrevue facile est devenu plus difficile: compte tenu des chiffres 1..100, trouver le numéro 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 nombre apparaît exactement une fois, donc il y a 100 nombres. Maintenant, un nombre est choisi au hasard dans le sac. Trouvez le numéro manquant.

j'ai entendu cette question d'interview avant, bien sûr, donc j'ai très rapidement répondu dans le sens de:

A1 : 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 nombres sont présents dans le sac, la somme sera exactement 5050 . Puisqu'il manque un nombre, la somme sera inférieure à, et la différence est de ce nombre. Nous pouvons donc trouver ce numéro manquant dans O(N) time et O(1) space.

à ce point je pensais avoir bien fait, mais tout d'un coup la question a pris une tournure inattendue:

Q2 : c'est exact, mais maintenant comment feriez-vous si deux numéros sont manquants?

je n'avais jamais vu/entendu / considéré cette variation avant, donc j'ai paniqué et ne pouvait pas répondre à la question. L'intervieweur a insisté pour connaître mon processus de pensée, donc j'ai mentionné que peut-être nous pouvons obtenir plus d'informations en comparant avec le produit attendu, ou peut-être faire un deuxième passage après avoir recueilli quelques informations de la première passe, etc, mais je ne faisais vraiment que tirer dans le noir plutôt que d'avoir un chemin clair vers la solution.

l'intervieweur a essayé pour m'encourager en disant qu'avoir une deuxième équation est en effet 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 main), et demandé si c'est une technique de programmation générale (lire: "utile"), ou si c'est juste un truc/gotcha 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 nombres manquants.

Qk : si exactement k nombres sont manquants du sac, comment le trouver efficacement?

C'était il y a quelques mois, et je ne savais toujours pas ce qu'était cette technique. Évidemment, il y a une limite inférieure de temps Ω(N) puisque nous devons scanner tous les nombres au moins une fois, mais l'interviewer a insisté pour que le temps et SPACE la complexité de la technique de résolution (moins le O(N) time input scan) est définie dans k pas N .

donc la question ici est simple:

  • comment résoudriez-vous Q2 ?
  • comment résoudriez-vous Q3 ?
  • comment résoudre Qk ?

Clarifications

  • il y a généralement des numéros N de 1.. N , pas seulement 1..100.
  • Je ne cherche pas la solution évidente basée sur un jeu de bits, p.ex. en utilisant un bit set , encodant la présence/absence de chaque nombre par la valeur d'un bit désigné, donc en utilisant O(N) bits en 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 l'évidente première approche de tri. Cette approche ainsi que celle basée sur le set valent la peine d'être mentionnées dans une interview (elles sont faciles à mettre en œuvre, et en fonction de N , peuvent être très pratiques). Je suis à la recherche de la solution du Saint Graal (qui peut être pratique ou non à mettre en œuvre, mais a les caractéristiques asymptotiques désirées néanmoins.)

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éfini en termes de k pas N ), et doit ensuite trouver le k numéros manquants d'une façon ou d'une autre.

1005
demandé sur AndyG 2010-08-16 14:26:58
la source

30 ответов

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

Souvenez-vous de la somme de i-ème pouvoirs, où i=1,2,..,K. Cela réduit le problème à la résolution du système d'équations

un 1 + 2 + ... + a k = b 1

un 1 2 + un 2 2 +... + a k 2 = b 2

...

un 1 k + un 2 k + ... + a k k = b k

à l'Aide de Newton identités , sachant b I permet de calculer

c 1 = 1 + 2 + ... a k

c 2 = 1 un 2 + 1 un 3 + ... + un k-1 un k

...

c k = 1 un 2 ... a k

si vous étendez le polynôme (x-a 1 )...(x-a k ) les coefficients seront exactement c 1 ,..., c k - voir Viete's formulas . Comme chaque polynôme est un seul facteur (anneau de polynômes est un domaine euclidien ) ), cela signifie un i sont déterminées de façon unique, jusqu'à la permutation.

ceci termine une preuve que se souvenir des pouvoirs est suffisant pour récupérer les nombres. Pour la constante k, c'est une bonne approche.

Toutefois, lorsque k est variable, l'approche directe de l'informatique c 1 ,...,c k est prohibitivement cher, puisque par exemple c k est le produit de tous les nombres manquants, ordre n!/(n-k)!. Pour surmonter cela, effectuer des calculs dans Z q champ, où q est un premier tel que n <= q < 2n - il existe par postulat de Bertrand . 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 pour la factorisation sur des champs finis, par exemple celui de Berlekamp ou Cantor-Zassenhaus .

pseudocode de haut niveau pour constante k:

  • Calculer i-ème de puissances de nombres donnés
  • soustrayez pour obtenir les sommes des pouvoirs i-ème de nombres inconnus. Appelez les sommes b je .
  • Utiliser les identités de Newton pour calculer les coefficients de b je ; appeler c je . Essentiellement, c 1 = b 1 ; c 2 = (c 1 b 1 - b 2 )/2; voir Wikipedia pour les formules exactes
  • factoriser le polynôme x k -c 1 x k-1 + ... + c k .
  • Les racines du polynôme sont les numéros nécessaires 1 , ... un k .

pour faire varier k, trouver un premier n <= q < 2n en utilisant par exemple Miller-Rabin, et effectuer les étapes avec tous les nombres modulo réduit Q.

comme Heinrich Apfelmus a commenté, au lieu d'un premier q Vous pouvez utiliser q=2 փ log n փ փ et effectuer arithmétique en champ fini .

526
répondu sdcvvc 2017-05-23 15:02:46
la source

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

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


Voir aussi sdcvvc's réponse directement liée , qui inclut également le pseudocode (hourra! pas besoin de lire ces délicates formulations mathématiques :)) (merci, excellent travail!).

229
répondu Dimitris Andreou 2017-05-23 14:47:24
la source

nous pouvons résoudre Q2 en sommant à la fois 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 inférieures aux valeurs attendues.

Le remplacement de

nous donne:

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

que nous pouvons ensuite résoudre pour déterminer nos nombres manquants.

160
répondu Anon. 2010-08-16 14:37:21
la source

comme @j_random_hacker l'a fait remarquer, c'est tout à fait similaire à trouver des doublons dans O(n) le temps et O(1) l'espace 1519260920" , et une adaptation de ma réponse fonctionne ici aussi.

en supposant que le" sac "est représenté par un tableau à base 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 réseau A[] par k éléments, de sorte qu'il est maintenant de taille N . C'est l'espace supplémentaire O(k) . 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 les entrées supplémentaires k à la même valeur que la première entrée dans le tableau (c'est juste une valeur pratique que nous savons être déjà présente dans le tableau - après cette étape, toutes les entrées qui manquaient dans le tableau initial de la taille N-k sont toujours manquantes dans la gamme étendue).

la deuxième boucle Permute le réseau étendu de sorte que si l'élément x est présent au moins une fois, alors l'une de ces entrées sera à la position A[x] .

notez que bien qu'il ait une boucle imbriquée, il fonctionne toujours en O(N) time - un swap ne se produit que s'il y a un i tel que A[i] != i , et chaque swap met 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 du corps de boucle while ) 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.

123
répondu caf 2017-05-23 15:34:44
la source

j'ai demandé à un enfant de 4 ans de 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, mais de nombreuses balles sont manquantes.

116
répondu Colonel Panic 2014-05-29 16:53:38
la source

pas sûr, si c'est la solution la plus efficace, mais je ferais boucle sur toutes les entrées, et utiliser un bitset pour se souvenir, quels nombres sont définis, puis tester pour 0 bits.

j'aime les solutions simples - et je crois même, qu'il pourrait être plus rapide que le calcul de la somme, ou la somme des carrés, etc.

30
répondu Chris Lercher 2010-08-16 14:38:16
la source

Je n'ai pas vérifié les maths, mais je soupçonne que le calcul Σ(n^2) dans le même passage que nous calculons Σ(n) fournirait assez d'information pour obtenir deux nombres manquants, faire Σ(n^3) aussi bien s'il ya trois, et ainsi de suite.

29
répondu AakashM 2010-08-16 14:38:41
la source

le problème avec les solutions basées sur des sommes de nombres est qu'ils ne prennent pas en compte le coût de stockage et de travail avec des nombres avec de grands exposants... en pratique, pour qu'il fonctionne pour de très grands n, une bibliothèque de grands nombres serait utilisée. Nous pouvons analyser l'espace d'utilisation de ces algorithmes.

nous pouvons analyser la complexité temporelle et spatiale des algorithmes de sdcvvc et Dimitris Andreou.

stockage:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

Donc l_j \in \Theta(j log n)

stockage Total utilisé: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

espace utilisé: en supposant que le calcul de a^j prend ceil(log_2 j) temps, temps total:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

temps Total utilisé: \Theta(kn log n)

si ce temps et cet espace est satisfaisant, vous pouvez utiliser un simple récursif algorithme. Laisse b!je l'ith entrée dans le sac, n le nombre de chiffres avant les déménagements, et k le nombre de suppression. En syntaxe Haskell...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

mémoire utilisée: O(k) pour la liste, O(log(n)) pour la pile: O(k + log(n)) Cet algorithme est plus intuitif, a la même complexité temporelle et utilise moins d'espace.

12
répondu a1kmm 2010-09-02 15:41:42
la source

attendez une minute. Comme la question est énoncée, il ya 100 numéros dans le sac. Peu importe la taille de k, le problème peut être résolu en temps constant parce que vous pouvez utiliser un ensemble et supprimer des nombres de l'ensemble à la plupart des 100 - K itérations d'une boucle. 100, c'est constant. L'ensemble des numéros restants est votre réponse.

si nous généralisons la solution aux nombres de 1 À N, rien ne change sauf que N n'est pas une constante, donc nous sommes dans O(N - k) = O(N) temps. Pour par exemple, si nous utilisons un jeu de bits, nous définissons les bits à 1 dans le temps O(N), nous itérons à travers les nombres, en définissant les bits à 0 que nous allons (O(N-k) = O(N)) et puis nous avons la réponse.

il me semble que l'intervieweur vous demandait comment imprimer le contenu de l'ensemble final en O(k) temps plutôt qu'en O(N) temps. Clairement, avec un bit défini, vous devez itérer à travers tous les bits N pour déterminer si vous devez imprimer le nombre ou non. Toutefois, si vous changer la façon dont l'ensemble est mis en œuvre vous pouvez imprimer les nombres en K itérations. Ceci est fait en mettant les nombres dans un objet pour être stocké à la fois dans un jeu de hash et une liste doublement liée. Lorsque vous retirez un objet du jeu de hash, vous le retirez également de la liste. Les réponses seront laissées dans la liste qui est maintenant de longueur K.

10
répondu JeremyP 2010-08-16 15:25:59
la source

Voici une solution qui utilise k bits de stockage supplémentaire, sans astuces astucieuses et tout simplement simple. Délai D'exécution O( n), espace supplémentaire O (k). Juste pour prouver que cela peut être résolu sans lire sur la solution d'abord OU être un génie:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= odd) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = even; i < n; ++i) data [i] += 1;
}
7
répondu gnasher729 2014-04-14 14:29:41
la source

pour résoudre la question des 2 (et 3) nombres manquants, vous pouvez modifier quickselect , qui tourne en moyenne dans O(n) et utilise la mémoire constante si le partitionnement est fait en place.

  1. Partition l'ensemble par rapport à un pivot aléatoire p en partitions l , qui contiennent des nombres plus petits que le pivot, et r , qui contiennent des nombres plus grands que le pivot.

  2. déterminer les partitions des 2 nombres manquants en comparant la valeur de pivot à la taille de chaque partition ( p - 1 - count(l) = count of missing numbers in l et n - count(r) - p = count of missing numbers in r )

  3. a) S'il manque un nombre à chaque partition, utilisez l'approche de la différence des sommes pour trouver chaque nombre manquant.

    (1 + 2 + ... + (p-1)) - sum(l) = missing #1 et ((p+1) + (p+2) ... + n) - sum(r) = missing #2

    b) s'il manque une partition, les deux nombres et la partition est vide, alors les nombres manquants sont soit (p-1,p-2) ou (p+1,p+2) selon quelle partition manque les nombres.

    si une partition manque 2 nombres mais n'est pas vide, alors revenez sur ce partiton.

avec seulement 2 nombres manquants, cet algorithme écarte toujours au moins une partition, de sorte qu'il conserve O(n) complexité temporelle moyenne de quickselect. De la même façon, avec 3 nombres manquants cet algorithme écarte également au moins une partition avec chaque passe (parce que comme avec 2 nombres manquants, au plus une seule partition contiendra plusieurs nombres manquants). Cependant, je ne suis pas sûr de combien la performance diminue lorsque d'autres nombres manquants sont ajoutés.

Voici une implémentation qui ne pas utiliser le partitionnement en place, de sorte que cet exemple ne répond pas à l'exigence d'espace, mais il illustre les étapes de la algorithme:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Démo

6
répondu FuzzyTree 2016-05-18 06:21:28
la source

pouvez-vous vérifier si chaque numéro existe? Si oui, vous pouvez essayer ceci:

s = somme de tous les nombres dans le sac (S < 5050)

Z = somme des nombres manquants 5050-s

si les numéros manquants sont x et y alors:

x = Z - y et

max (x) = Z-1

donc vous vérifiez le plage de 1 à max(x) et trouver le nombre

4
répondu Ilian Iliev 2012-11-21 21:57:14
la source

vous pouvez résoudre Q2 si vous avez la somme des deux listes et le produit des deux listes.

(L1 est l'original, l2 est la liste modifiée)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

nous pouvons optimiser ceci puisque la somme d'une série arithmétique est n fois la moyenne des premier et dernier Termes:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

maintenant nous savons que (si a et b sont les nombres supprimés):

a + b = d
a * b = m

pour que nous puissions nous réarranger en:

a = s - b
b * (s - b) = m

et multiplier:

-b^2 + s*b = m

et réarrangez de sorte que le côté droit est zéro:

-b^2 + s*b - m = 0

alors nous pouvons résoudre avec la formule quadratique:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

exemple de code Python 3:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

Je ne connais pas la complexité de la sqrt, réduire et la somme des fonctions donc je ne peux pas comprendre la complexité de cette solution (si quelqu'un sait, s'il vous plaît commentaire ci-dessous.)

3
répondu Tuomas Laakkonen 2014-11-16 19:14:55
la source

peut-être cet algorithme peut fonctionner pour la question 1:

  1. précalculer xor des premiers 100 entiers(val=1^2^3^4....100)
  2. X pour les éléments qui proviennent toujours du flux d'entrée (val1=val1^next_input)
  3. réponse finale = val^val1

ou même mieux:

def GetValue(A)
    for i=1 to 100
     do
       val=val^i
     done
     for value in A:
       do
         val=val^value 
       done
    return val

cet algorithme peut en fait être élargi pour deux nombres manquants. La première étape reste la même. Lorsque nous appelons GetValue avec deux numéros manquants le résultat sera un a1^a2 sont les deux nombres manquants. Disons

val = a1^a2

maintenant, pour tamiser a1 et a2 à partir de val, nous prenons n'importe quel bit fixé à val. Disons que le bit ith est défini en val. Cela signifie que a1 et a2 ont une parité différente à la position ith bit. Maintenant nous faisons une autre itération sur le tableau original et gardons deux valeurs de xor. Un pour les nombres qui ont le ith ensemble de bits et d'autres qui n'ont pas le i-ème bit. Nous avons maintenant deux seaux de nombres, et son guranteed que a1 and a2 se trouvera dans des seaux différents. Répétez maintenant ce que nous avons fait pour trouver un élément manquant sur chaque seau.

3
répondu bashrc 2016-05-04 07:21:24
la source

je pense que cela peut être fait sans équations et théories mathématiques complexes. On trouvera ci-après une proposition de solution en place et de complexité temporelle O(2n):

suppositions relatives aux formulaires D'entrée:

# de nombres dans le sac = n

# de nombres manquants = k

les nombres dans le sac sont représentés par un tableau de longueur n

Longueur du tableau d'entrée pour l'algo = n

entrées Manquantes dans le tableau (chiffres tirés du sac) sont remplacés par la valeur du premier élément du tableau.

par exemple. Initialement sac ressemble à [2,9,3,7,8,6,4,5,1,10]. Si le 4 est sorti, la valeur de 4 deviendra 2 (le premier élément du tableau). Par conséquent après avoir sorti 4 le sac ressemblera à [2,9,3,7,8,6,2,5,1,10]

la clé de cette solution est d'étiqueter L'indice d'un nombre visité en niant la valeur à cet indice comme le réseau est traversé.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }
2
répondu pickhunter 2012-12-12 22:57:14
la source

pour Q2 c'est une solution qui est un peu plus inefficace que les autres, mais qui a quand même O(N) runtime et prend O(k) space.

L'idée est d'exécuter l'algorithme original à deux reprises. Dans la première, vous obtenez un nombre total qui est manquante, ce qui vous donne une limite supérieure de l'numéros manquants. Appelons ce numéro N . Vous savez que les deux nombres manquants vont se résumer à N , de sorte que le premier nombre ne peut être que dans l'intervalle [1, floor((N-1)/2)] alors que le second sera dans [floor(N/2)+1,N-1] .

ainsi vous bouclez sur tous les nombres encore une fois, en rejetant tous les nombres qui ne sont pas inclus dans le premier intervalle. Ceux qui sont, vous garder une trace de leur somme. Enfin, vous connaîtrez un des deux nombres manquants, et par extension le second.

j'ai le sentiment que cette méthode pourrait être généralisée et que des recherches multiples pourraient être effectuées en "parallèle" lors d'un passage unique sur l'entrée, mais Je n'ai pas encore trouvé comment.

2
répondu Svalorzen 2016-05-24 19:51:12
la source

très joli problème. J'utiliserais une différence pour Qk. Beaucoup de langages de programmation ont même un support, comme dans Ruby:

missing = (1..100).to_a - bag

ce n'est probablement pas la solution la plus efficace, mais c'est une solution que j'utiliserais dans la vie réelle si j'étais confronté à une telle tâche dans ce cas (limites connues, limites basses). Si l'ensemble de nombre serait très grand alors je considérerais un algorithme plus efficace, bien sûr, mais en attendant la solution simple serait assez pour moi.

1
répondu DarkDust 2010-08-16 15:18:39
la source

j'adopte une approche différente à cette question et j'interroge l'intervieweur pour obtenir plus de détails sur le plus grand problème qu'il essaie de résoudre. Selon le problème et les exigences qui l'entourent, la solution évidente basée sur les ensembles pourrait être la bonne chose et l'approche génératrice-liste-et-pick-through-it-after pourrait ne pas l'être.

par exemple, il se pourrait que l'intervieweur va envoyer n messages et a besoin de connaître le k cela n'a pas abouti à une réponse et doit le savoir en aussi peu de temps d'horloge que possible après l'arrivée de la réponse n-k . Disons aussi que la nature du canal de messages est telle que même s'il fonctionne à pleine capacité, il y a assez de temps pour faire un certain traitement entre les messages sans avoir aucun impact sur le temps qu'il faut pour produire le résultat final après la dernière réponse arrive. Ce temps peut être mis à utiliser en insérant une certaine facette d'identification de chaque message envoyé dans un ensemble et en le supprimant comme chaque réponse correspondante arrive. Une fois que la dernière réponse est arrivée, la seule chose à faire est de supprimer son identifiant de l'ensemble, qui dans les implémentations typiques prend O(log k+1) . Après cela, l'ensemble contient la liste des éléments manquants k et il n'y a pas de traitement supplémentaire à faire.

ce n'est certainement pas l'approche la plus rapide pour le traitement par lots pré-généré sacs de numéros parce que le tout fonctionne O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)) . Mais il fonctionne pour toute valeur de k (même si elle n'est pas connue à l'avance) et dans l'exemple ci-dessus elle a été appliquée d'une manière qui minimise l'intervalle le plus critique.

1
répondu Blrfl 2010-09-03 06:57:57
la source

vous pouvez motiver la solution en y pensant en termes de symétries (groupes, en langage mathématique). Peu importe l'ordre d'un ensemble de nombres, la réponse doit être la même. Si vous utilisez les fonctions k pour aider à déterminer les éléments manquants, vous devriez réfléchir à quelles fonctions ont cette propriété: symétrique. La fonction s_1(x) = x_1 + x_2 + ... + x_n est un exemple de fonction symétrique, mais il y en a d'autres de plus haut degré. En particulier, examiner les élémentaire des fonctions symétriques . La fonction symétrique élémentaire du degré 2 est s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n , la somme de tous les produits de deux éléments. De même pour les fonctions élémentaires symétriques de degré 3 et plus. Ils sont évidemment symétriques. De plus, il s'avère qu'ils sont les éléments constitutifs de toutes les fonctions symétriques.

vous pouvez construire les fonctions élémentaires symétriques que vous allez en notant que s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)) . D'autres réflexions devraient vous convaincre que s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1)) et ainsi de suite, afin qu'ils puissent être calculés en un seul passage.

Comment savoir quels articles manquaient dans le tableau? Pensez au polynôme (z-x_1)(z-x_2)...(z-x_n) . Il évalue à 0 si vous mettez dans l'un des nombres x_i . En agrandissant le polynôme, vous obtenez z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n . Les fonctions élémentaires symétriques apparaissent ici aussi, ce qui n'est vraiment pas surprenant, puisque le polynôme devrait rester le même si nous appliquons n'importe quelle permutation aux racines.

donc nous pouvons construire le polynôme et essayer de le factoriser pour comprendre quels nombres ne sont pas dans l'ensemble, comme d'autres l'ont mentionné.

enfin, si nous nous soucions de déborder la mémoire avec de grands nombres (le nième polynôme symétrique sera de l'ordre de 100! ), nous pouvons faire ces calculs mod pp est un nombre premier supérieur à 100. Dans ce cas, nous évaluons le polynôme mod p et nous constatons qu'il évalue à 0 lorsque l'entrée est un nombre dans l'ensemble, et il renvoie une valeur non nulle lorsque l'entrée est un nombre pas dans le jeu. Cependant, comme d'autres l'ont souligné, d'obtenir les valeurs du polynôme dans le temps qui dépend de la k , pas N , nous avons factoriser le polynôme mod p .

1
répondu Edward Doolittle 2015-04-21 22:49:18
la source

vous auriez probablement besoin d'éclaircissements sur ce que O(k) signifie.

Voici une solution triviale pour K arbitraire: pour chaque v dans votre ensemble de nombres, accumuler la somme de 2^v. à la fin, boucle i de 1 à N. Si la somme modulo 2^I est zéro, alors je manque.

facile, non? O(N), O(1) de stockage et prend en charge arbitraire k.

sauf que vous calculez des nombres énormes que sur un vrai ordinateur exigerait chacun O(N) espace. En fait, cette solution est identique à un vecteur de bits.

de Sorte que vous pourriez être intelligent et calculer la somme et la somme des carrés et la somme des cubes... jusqu'à la somme de v^k, et faire les maths fantaisistes pour extraire le résultat. Mais ce sont aussi de grands nombres, ce qui soulève la question: de quel modèle abstrait de fonctionnement parlons-nous? Combien de place dans L'espace O (1), et combien de temps cela prend-il pour résumer des nombres de n'importe quelle taille dont vous avez besoin?

1
répondu sfink 2016-08-10 00:52:20
la source

il y a une façon générale de généraliser des algorithmes de streaming comme celui-ci. L'idée est d'utiliser un peu de randomisation pour, espérons, "propager" les éléments k en sous-problèmes indépendants, où notre algorithme original résout le problème pour nous. Cette technique est utilisée dans la reconstruction de signaux épars, entre autres choses.

  • Faire un tableau, a , de taille u = k^2 .
  • Choisissez tout universel fonction de hachage , h : {1,...,n} -> {1,...,u} . (Comme multipliez-shift )
  • pour chaque i dans 1, ..., n augmentation a[h(i)] += i
  • pour chaque numéro x dans le flux d'entrée, décrément a[h(x)] -= x .

si tous les nombres manquants ont été hachurés à des seaux différents, les éléments non-zéros du tableau contiendront maintenant les nombres manquants.

la probabilité qu'une paire particulière soit envoyée dans le même seau est inférieure à 1/u par définition d'une fonction de hachage universelle. Depuis il y a environ k^2/2 paires, nous avons que la probabilité d'erreur est au plus k^2/2/u=1/2 . C'est-à-dire, nous réussissons avec Probabilité au moins 50%, et si nous augmentons u nous augmentons nos chances.

notez que cet algorithme prend k^2 logn bits d'espace (nous avons besoin de logn bits par tableau seau.) Ceci correspond à l'espace requis par la réponse de @Dimitris Andreou (en particulier l'espace requis par la factorisation polynomiale, qui se trouve aussi être aléatoire.) Cet algorithme dispose également de temps constant par mise à jour, plutôt que de temps k dans le cas de puissances-sommes.

en fait, nous pouvons être encore plus efficace que la méthode de la somme de puissance en utilisant l'astuce décrite dans les commentaires.

1
répondu Thomas Ahle 2017-11-26 13:42:38
la source

vous pouvez essayer d'utiliser un filtre de fleur . Insérez chaque nombre dans le sac dans la fleur, puis itérez au-dessus de l'ensemble 1-k complet jusqu'à ce que le rapport de chacun n'a pas trouvé. Cela peut ne pas trouver la réponse dans tous les scénarios, mais pourrait être une bonne solution.

0
répondu jdizzle 2010-09-03 02:22:37
la source

je crois que j'ai un O(k) temps et O(log(k)) algorithme de l'espace, étant donné que vous avez les floor(x) et log2(x) fonctions pour des entiers arbitrairement grands disponibles:

vous avez un k - bit entier long (d'où l'espace log8(k) ) où vous ajoutez le x^2 , où x est le prochain nombre que vous trouvez dans le sac: s=1^2+2^2+... cela prend O(N) temps (qui n'est pas un problème pour l'interviewer). À la fin, vous obtenez j=floor(log2(s)) qui est le plus grand nombre que vous recherchez. Puis s=s-j et vous recommencez ce qui précède:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

Maintenant, vous n'avez généralement pas de fonctions floor et log2 pour 2756 -bits entiers, mais à la place pour doubles. Alors? Simplement, pour chaque 2 octets (ou 1, ou 3, ou 4) Vous pouvez utiliser ces fonctions pour obtenir les nombres désirés, mais cela ajoute un O(N) facteur de complexité de temps

0
répondu CostasGR43 2012-11-21 21:58:36
la source

cela peut sembler stupide, mais, dans le premier problème présenté à vous, vous auriez à voir tous les nombres restants dans le sac pour les additionner effectivement pour trouver le nombre manquant en utilisant cette équation.

donc, puisque vous pouvez voir tous les numéros, cherchez juste le numéro qui manque. Il en va de même lorsque deux numéros sont manquants. Assez simple je pense. Inutile d'utiliser une équation quand on voit les nombres qui restent dans le sac.

0
répondu Stephan M 2014-05-29 16:46:22
la source

je pense que cela peut être généralisé comme ceci:

indique S, M comme valeurs initiales pour la somme des séries arithmétiques et de la multiplication.

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

je devrais penser à une formule pour calculer ceci, mais ce n'est pas le point. Quoi qu'il en soit, s'il manque un numéro, vous avez déjà fourni la solution. Cependant, s'il manque deux nombres, alors, nous dénotons la nouvelle somme et le multiple total par S1 et M1, qui sera comme suit:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

comme vous connaissez S1, M1, M et S, l'équation ci-dessus est soluble pour trouver a et b, les nombres manquants.

pour les trois numéros manquants:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

maintenant votre Inconnu est 3 tandis que vous avez juste deux équations que vous pouvez résoudre à partir.

0
répondu Jack_of_All_Trades 2014-05-29 16:59:41
la source

je ne sais pas si c'est efficace ou non, mais je voudrais suggérer cette solution.

  1. calculer xor des 100 éléments
  2. calculer xor des 98 éléments (après suppression des 2 éléments)
  3. Now (résultat de 1) XOR (résultat de 2) Vous donne le xor des deux nos I..e a XOR B Si a et b sont les éléments manquants

    4.Obtenez la somme des Nos manquants avec votre approche habituelle de la formule de la somme diff et disons que la diff est D.

exécutez maintenant une boucle pour obtenir les paires possibles (p,q) qui se trouvent toutes les deux dans [1 , 100] et la somme à d.

Lorsqu'une paire est obtenue, vérifier si (résultat de 3) XOR p = q et si oui, nous sommes fait.

s'il vous plaît corrigez-moi si je me trompe et aussi commenter la complexité du temps si c'est correct

0
répondu user2221214 2014-08-05 01:49:59
la source

j'ai une idée, mais cela suppose que la taille réelle du tableau est de 100 et les nombres manquants sont remplacés par quelque chose d'autre (comme -1).

En Gros, faites une sorte de version modifiée d'une sélection qui change la liste en place. Je crois que C'est le bon moment(corrigez-moi si je me trompe) parce que nous utilisons le fait que nous connaissons déjà les nombres qui devraient exister. Nous échangeons la valeur avec la position" correcte", jusqu'à ce que l'indice nous sont a le bon numéro (ou -1).

Après nous, nous venons de boucle de nouveau la liste et l'index sera essentiellement les numéros manquants

#Set up the input
input = (1..100).to_a.shuffle
input[rand(0..99)] = -1
input[rand(0..99)] = -1

def f(a)
  for i in 0..99
    while (a[i] != i+1) && a[i] > 0
      v1 = a[i]
      v2 = a[v1 - 1]
      a[i] = v2
      a[v1 - 1] = v1
    end
  end

  result = []
  a.each_with_index do |value, index|
    if value < 0
      result.push(index + 1)
    end
  end

  return result
end

#Returns the 2 missing numbers
puts f(input)
0
répondu stephwag 2017-05-20 05:34:40
la source

nous pouvons faire le Q1 et Q2 dans O(log n) la plupart du temps.

supposons que notre memory chip consiste en une rangée de n nombre de test tubes . Et un numéro x dans le tube d'essai est représenté par x milliliter de chimique-liquide.

Supposons que notre processeur est un laser light . Quand on allume le laser, il parcourt tous les tubes perpendiculairement à c'est la longueur. A chaque passage dans le liquide chimique, la luminosité est réduite de 1 . Et passer la lumière à un certain millilitre marque est une opération de O(1) .

maintenant si nous allumons notre laser au milieu du tube à essai et obtenir le rendement de luminosité

  • est égal à une valeur pré-calculée(calculée lorsqu'il n'y avait pas de nombres manquants), alors les nombres manquants sont supérieurs à n/2 .
  • si notre sortie est plus petite, alors il y a au moins un nombre manquant qui est plus petit que n/2 . Nous pouvons également vérifier si la luminosité est réduite par 1 ou 2 . si elle est réduite de 1 alors un nombre manquant est plus petit que n/2 et l'autre est plus grand que n/2 . Si elle est réduite de 2 , alors les deux nombres sont plus petits que n/2 .

Nous pouvons répéter le processus ci-dessus à nouveau et à nouveau circonscrire notre domaine de problèmes. À chaque étape, nous rendons le domaine plus petit de moitié. Et finalement nous pouvons arriver à notre résultat.

algorithmes parallèles qui valent la peine d'être mentionnés (parce qu'ils sont intéressants),

  • Tri par un algorithme parallèle, par exemple, la fusion parallèle peut être faite en O(log^3 n) temps. Et puis le nombre manquant peut être trouvé par recherche binaire dans O(log n) temps.
  • Théoriquement, si nous avons des processeurs n , alors chaque processus peut vérifier une des entrées et définir un drapeau qui identifie le nombre(commodément dans un tableau). Et dans l'étape suivante chaque processus peut vérifier chaque drapeau et finalement produire le nombre qui n'est pas marqué. L'ensemble du processus prendra O(1) temps. Il a besoin d'espace/mémoire supplémentaire O(n) .

noter que les deux algorithmes parallèles fournis ci-dessus peuvent besoin d'espace supplémentaire, comme mentionné dans le commentaire .

0
répondu shuva 2017-12-16 00:47:41
la source

encore une autre façon est d'utiliser le filtrage de graphe résiduel.

supposons que nous ayons les numéros 1 à 4 et 3 est manquant. La représentation binaire est la suivante,

1 = 001b, 2= 010b, 3 = 011b, 4 =100b

et je peux créer un graphique de flux comme celui-ci.

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

noter que le graphique de flux contient x noeuds, tandis que x est le nombre de bits. Et le nombre maximum de bords sont (2*x)-2 .

donc pour 32 bit entier il faudra de l'espace O(32) ou de L'espace O(1).

maintenant si je supprime la capacité pour chaque nombre à partir de 1,2,4 puis je suis laissé avec un graphe résiduel.

0 ----------> 1 ---------> 1

enfin je vais lancer une boucle comme la suivante,

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

Maintenant, le résultat est dans result contient des nombres qui ne sont pas manquantes(faux positif). Mais le k < = (Taille de le résultat) <= n quand il y a des k éléments manquants.

je doit passer par la liste donnée une dernière fois pour marquer le résultat manquant ou non.

ainsi la complexité de temps sera O(n) .

enfin, il est possible de réduire le nombre de faux positifs(et l'espace requis) en prenant des noeuds 00 , 01 , 11 , 10 au lieu de simplement 0 et 1 .

0
répondu shuva 2018-07-20 20:30:59
la source

Essayer de trouver le produit des nombres de 1 à 50:

produit Let, P1 = 1 x 2 x 3 x............. 50

lorsque vous retirez des nombres un par un, multipliez-les de sorte que vous obtenez le produit P2. Mais il manque ici deux nombres, donc P2 < P1.

le produit des deux termes mising, A x B = P1 - P2.

vous connaissez déjà la somme, a + b = S1.

des deux précédents équations à résoudre pour a et b à travers une équation quadratique. a et b sont les numéros manquants.

-1
répondu Manjunath 2014-05-29 16:45:24
la source

Autres questions sur algorithm math