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


Answers

Vous le trouverez en lisant les quelques pages de Muthukrishnan - Data Stream Algorithms: 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. :)

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

Question

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 les numéros 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 nombres 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 en temps O(N) et O(1) .

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

Q2 : C'est exact, mais maintenant, comment feriez-vous cela si DEUX 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 nombres manquants.

Qk : Si exactement des k 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. Évidemment, il y a une limite de temps Ω(N) puisque nous devons balayer tous les nombres au moins une fois, mais l'intervieweur a insisté sur le fait que la complexité temporelle et spatiale de la technique de résolution (moins le balayage d'entrée de temps O(N) 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 exemple en utilisant un ensemble de bits , codant la présence / absence de chaque nombre par la valeur d'un bit désigné, utilisant donc O(N) bits dans l'espace supplémentaire. Nous ne pouvons nous permettre aucun 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 , peuvent être très pratiques). 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'information (définie en termes de k non N ), et devez alors trouver les k nombres manquants.




Pour résoudre la question 2 (et 3) numéros manquants, vous pouvez modifier quickselect , qui s'exécute en moyenne dans O(n) et utilise la mémoire constante si le partitionnement est effectué sur place.

  1. Partitionner 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 supérieurs au pivot.

  2. Déterminer les partitions dans lesquelles se trouvent les 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) Si une partition manque les deux nombres et que la partition est vide, alors les nombres manquants sont (p-1,p-2) ou (p+1,p+2) selon la partition qui manque les nombres.

    Si une partition manque 2 nombres mais n'est pas vide, alors recurse sur cette partie.

Avec seulement 2 nombres manquants, cet algorithme rejette toujours au moins une partition, donc il conserve O(n) complexité moyenne en temps de quickselect. De même, avec 3 nombres manquants, cet algorithme rejette également au moins une partition à chaque passage (car comme avec 2 nombres manquants, au plus une seule partition contiendra plusieurs nombres manquants). Cependant, je ne suis pas sûr de combien les performances diminuent quand plus de nombres manquants sont ajoutés.

Voici une implémentation qui n'utilise pas le partitionnement sur place, donc cet exemple ne répond pas à l'exigence d'espace mais illustre les étapes de l'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);
    }
  }

Demo




You'd probably need clarification on what O(k) means.

Here's a trivial solution for arbitrary k: for each v in your set of numbers, accumulate the sum of 2^v. At the end, loop i from 1 to N. If sum modulo 2^i is zero, then i is missing.

Easy, right? O(N) time, O(1) storage, and it supports arbitrary k.

Except that you're computing enormous numbers that on a real computer would each require O(N) space. In fact, this solution is identical to a bit vector.

So you could be clever and compute the sum and the sum of squares and the sum of cubes... up to the sum of v^k, and do the fancy math to extract the result. But those are big numbers too, which begs the question: what abstract model of operation are we talking about? How much fits in O(1) space, and how long does it take to sum up numbers of whatever size you need?




May be this algorithm can work for question 1:

  1. Precompute xor of first 100 integers(val=1^2^3^4....100)
  2. xor the elements as they keep coming from input stream ( val1=val1^next_input)
  3. final answer=val^val1

Or even better:

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

This algorithm can in fact be expanded for two missing numbers. The first step remains the same. When we call GetValue with two missing numbers the result will be a a1^a2 are the two missing numbers. Lets say

val = a1^a2

Now to sieve out a1 and a2 from val we take any set bit in val. Lets say the ith bit is set in val. That means that a1 and a2 have different parity at ith bit position. Now we do another iteration on the original array and keep two xor values. One for the numbers which have the ith bit set and other which doesn't have the ith bit set. We now have two buckets of numbers, and its guranteed that a1 and a2 will lie in different buckets. Now repeat the same what we did for finding one missing element on each of the bucket.




A very simple way to do it in roughly O(N) time is to remove each element when seen in both lists. This works for unsorted lists too and can be easily further optimized if the lists are both sorted.

import random

K = 2
missingNums = range(0, 101)
incompleteList = range(0, 101)

#Remove K numbers
for i in range(K):
    valueToRemove = random.choice(incompleteList)
    incompleteList.remove(valueToRemove)

dummyVariable = [missingNums.remove(num) for num in p if num in missingNums]

print missingNums



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.




Voici une solution qui utilise k bits de stockage supplémentaire, sans astuces astucieuses et simple. Temps d'exécution O (n), espace supplémentaire O (k). Juste pour prouver que cela peut être résolu sans lire d'abord sur la solution 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;
}



I think this can be generalized like this:

Denote S, M as the initial values for the sum of arithmetic series and multiplication.

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

I should think about a formula to calculate this, but that is not the point. Anyway, if one number is missing, you already provided the solution. However, if two numbers are missing then, let's denote the new sum and total multiple by S1 and M1, which will be as follows:

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

Where a and b are the missing numbers.

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

Since you know S1, M1, M and S, the above equation is solvable to find a and b, the missing numbers.

Now for the three numbers missing:

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

Where a and b are the missing numbers.

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

Now your unknown is 3 while you just have two equations you can solve from.




I don't know whether this is efficient or not but I would like to suggest this solution.

  1. Compute xor of the 100 elements
  2. Compute xor of the 98 elements (after the 2 elements are removed)
  3. Now (result of 1) XOR (result of 2) gives you the xor of the two missing nos i..ea XOR b if a and b are the missing elements
    4.Get the sum of the missing Nos with your usual approach of the sum formula diff and lets say the diff is d.

Now run a loop to get the possible pairs (p,q) both of which lies in [1 , 100] and sum to d.

When a pair is obtained check whether (result of 3) XOR p = q and if yes we are done.

Please correct me if I am wrong and also comment on time complexity if this is correct




Le problème avec les solutions basées sur la somme des 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 n très grand, une bibliothèque de grands nombres serait employée . Nous pouvons analyser l'utilisation de l'espace pour ces algorithmes.

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

Espace de rangement:

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 calculer 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 sont satisfaisants, vous pouvez utiliser un algorithme récursif simple. Soit b! I l'entrée ith dans le sac, n le nombre de chiffres avant les retraits, et k le nombre de suppressions. Dans la 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

Stockage utilisé: 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.




There is a general way to generalize streaming algorithms like this. The idea is to use a bit of randomization to hopefully 'spread' the k elements into independent sub problems, where our original algorithm solves the problem for us. This technique is used in sparse signal reconstruction, among other things.

  • Make an array, a , of size u = k^2 .
  • Pick any universal hash function , h : {1,...,n} -> {1,...,u} . (Like multiply-shift )
  • For each i in 1, ..., n increase a[h(i)] += i
  • For each number x in the input stream, decrement a[h(x)] -= x .

If all of the missing numbers have been hashed to different buckets, the non-zero elements of the array will now contain the missing numbers.

The probability that a particular pair is sent to the same bucket, is less than 1/u by definition of a universal hash function. Since there are about k^2/2 pairs, we have that the error probability is at most k^2/2/u=1/2 . That is, we succeed with probability at least 50%, and if we increase u we increase our chances.

Notice that this algorithm takes k^2 logn bits of space (We need logn bits per array bucket.) This matches the space required by @Dimitris Andreou's answer (In particular the space requirement of polynomial factorization, which happens to also be randomized.) This algorithm also has constant time per update, rather than time k in the case of power-sums.

In fact, we can be even more efficient than the power sum method by using the trick described in the comments.




I believe I have a O(k) time and O(log(k)) space algorithm, given that you have the floor(x) and log2(x) functions for arbitrarily big integers available:

You have an k -bit long integer (hence the log8(k) space) where you add the x^2 , where x is the next number you find in the bag: s=1^2+2^2+... This takes O(N) time (which is not a problem for the interviewer). At the end you get j=floor(log2(s)) which is the biggest number you're looking for. Then s=sj and you do again the above:

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

Now, you usually don't have floor and log2 functions for 2756 -bit integers but instead for doubles. Alors? Simply, for each 2 bytes (or 1, or 3, or 4) you can use these functions to get the desired numbers, but this adds an O(N) factor to time complexity




Comme l'a souligné @j_random_hacker, ceci est assez similaire à Trouver des doublons dans le temps O (n) et dans l'espace O (1) , et une adaptation de ma réponse fonctionne là 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 en temps O(N) et O(k) espace supplémentaire.

Tout d'abord, nous étendons notre tableau A[] par k éléments, de sorte qu'il est maintenant de taille N C'est l'espace additionnel 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 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 Nk 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, alors l'une de ces entrées sera à la position A[x] .

Notez que bien qu'il ait une boucle imbriquée, il s'exécute toujours en temps O(N) - un échange ne se produit que s'il y a un i tel que A[i] != i , et chaque swap 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 du corps de la 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 dois avoir manqué.




This might sound stupid, but, in the first problem presented to you, you would have to see all the remaining numbers in the bag to actually add them up to find the missing number using that equation.

So, since you get to see all the numbers, just look for the number that's missing. The same goes for when two numbers are missing. Pretty simple I think. No point in using an equation when you get to see the numbers remaining in the bag.




You could try using a Bloom Filter . Insert each number in the bag into the bloom, then iterate over the complete 1-k set until reporting each one not found. This may not find the answer in all scenarios, but might be a good enough solution.