Einfache Interviewfragen wurden schwieriger: Bei den angegebenen Nummern 1..100 finden Sie die fehlenden Nummern, bei denen genau k fehlt

Ich hatte vor einiger Zeit ein interessantes Vorstellungsgespräch. Die Frage begann ganz einfach:

Q1 : Wir haben eine Tasche mit Zahlen 1, 2, 3, ..., 100. Jede Zahl erscheint genau einmal, es gibt also 100 Zahlen. Jetzt wird eine Nummer zufällig aus der Tasche gezogen. Finde die fehlende Zahl.

Ich habe diese Interviewfrage natürlich schon einmal gehört, also habe ich sehr schnell geantwortet:

A1 : Nun, die Summe der Zahlen 1 + 2 + 3 + … + Nist (N+1)(N/2)(siehe Wikipedia: Summe der arithmetischen Reihen ). Denn N = 100die Summe ist 5050.

Wenn also alle Zahlen in der Tasche vorhanden sind, ist die Summe genau 5050. Da eine Zahl fehlt, ist die Summe geringer, und der Unterschied ist diese Zahl. So können wir diese fehlende Zahl in O(N)Zeit und O(1)Raum finden.

Zu diesem Zeitpunkt dachte ich, ich hätte es gut gemacht, aber plötzlich nahm die Frage eine unerwartete Wendung:

F2 : Das ist richtig, aber wie würden Sie das tun, wenn ZWEI Zahlen fehlen?

Ich hatte diese Variante noch nie gesehen / gehört / in Betracht gezogen, geriet in Panik und konnte die Frage nicht beantworten. Der Interviewer bestand darauf, meinen Denkprozess zu kennen, und ich erwähnte, dass wir vielleicht mehr Informationen erhalten können, indem wir ihn mit dem erwarteten Produkt vergleichen oder vielleicht einen zweiten Durchgang machen, nachdem wir einige Informationen aus dem ersten Durchgang usw. gesammelt haben, aber ich habe wirklich nur geschossen im Dunkeln, anstatt tatsächlich einen klaren Weg zur Lösung zu haben.

Der Interviewer hat versucht, mich zu ermutigen, indem er sagte, dass eine zweite Gleichung tatsächlich eine Möglichkeit ist, das Problem zu lösen. Zu diesem Zeitpunkt war ich etwas verärgert (weil ich die Antwort nicht vorher kannte) und fragte, ob dies eine allgemeine (sprich: "nützliche") Programmiertechnik ist oder ob es nur eine Trick / Gotcha-Antwort ist.

Die Antwort des Interviewers überraschte mich: Sie können die Technik verallgemeinern, um 3 fehlende Zahlen zu finden. Tatsächlich können Sie es verallgemeinern, um k fehlende Zahlen zu finden .

Qk : Wenn genau k Zahlen in der Tasche fehlen, wie würden Sie sie effizient finden?

Dies war vor ein paar Monaten und ich konnte immer noch nicht herausfinden, was diese Technik ist. Offensichtlich gibt es eine Ω(N)Zeituntergrenze, da wir alle Zahlen mindestens einmal scannen müssen, aber der Interviewer bestand darauf, dass die ZEIT- und RAUM- Komplexität der Lösungstechnik (abzüglich des O(N)Zeiteingabescans) in k und nicht in N definiert ist .

Die Frage hier ist also einfach:

• Wie würden Sie Q2 lösen ?
• Wie würden Sie Q3 lösen ?
• Wie würden Sie Qk lösen ?

Klarstellungen

• Im Allgemeinen gibt es N Zahlen von 1 .. N , nicht nur 1..100.
• Ich bin nicht auf der Suche nach einer offensichtlichen satzbasierten Lösung, z. B. unter Verwendung eines Bit-Satzes , der das Vorhandensein / Fehlen jeder Zahl durch den Wert eines bestimmten Bits O(N)codiert und daher Bits in zusätzlichem Raum verwendet. Wir können uns keinen zusätzlichen Platz leisten, der proportional zu N ist .
• Ich bin auch nicht auf der Suche nach dem offensichtlichen Sort-First-Ansatz. Dies und der satzbasierte Ansatz sind in einem Interview erwähnenswert (sie sind einfach zu implementieren und können je nach N sehr praktisch sein). Ich suche nach der Holy Grail-Lösung (die möglicherweise praktisch ist oder nicht, aber dennoch die gewünschten asymptotischen Eigenschaften aufweist).

Natürlich müssen Sie die Eingabe wieder einscannen O(N), aber Sie können nur eine kleine Menge an Informationen erfassen (definiert als k, nicht N ) und müssen dann die k fehlenden Zahlen irgendwie finden.

Hier ist eine Zusammenfassung des Links von Dimitris Andreou .

Denken Sie an die Summe der i-ten Potenzen, wobei i = 1,2, .., k. Dies reduziert das Problem auf die Lösung des Gleichungssystems

a ₁ + a ₂ + ... + a _k = b ₁

a ₁ ² + a ₂ ² + ... + a _k ² = b ₂

...

a ₁ ^k + a ₂ ^k + ... + a _k ^k = b _k

Wenn Sie die Newtonschen Identitäten verwenden und b _{i kennen,} können Sie rechnen

c ₁ = a ₁ + a ₂ + ... a _k

c ₂ = a ₁ a ₂ + a ₁ a ₃ + ... + a _k-1 a _k

...

c _k = a ₁ a ₂ ... a _k

Wenn Sie das Polynom (xa ₁ ) ... (xa _k ) erweitern, sind die Koeffizienten genau c ₁ , ..., c _k - siehe Viètes Formeln . Da jeder Polynomfaktor eindeutig ist (der Polynomring ist eine euklidische Domäne ), bedeutet dies, dass ein _i bis zur Permutation eindeutig bestimmt wird.

Dies beendet einen Beweis dafür, dass das Erinnern an Kräfte ausreicht, um die Zahlen wiederherzustellen. Für die Konstante k ist dies ein guter Ansatz.

Wenn jedoch k variiert, ist der direkte Ansatz der Berechnung von c ₁ , ..., c _k unerschwinglich teuer, da z. B. c _k das Produkt aller fehlenden Zahlen ist, Größe n! / (Nk)!. Um dies zu überwinden, führen Sie Berechnungen im Feld Z _{q durch} , wobei q eine Primzahl ist, so dass n <= q <2n - es existiert nach Bertrands Postulat . Der Beweis muss nicht geändert werden, da die Formeln immer noch gelten und die Faktorisierung von Polynomen immer noch einzigartig ist. Sie benötigen auch einen Algorithmus zur Faktorisierung über endliche Felder, zum Beispiel den von Berlekamp oder Cantor-Zassenhaus .

High-Level-Pseudocode für Konstante k:

• Berechnen Sie die i-ten Potenzen gegebener Zahlen
• Subtrahieren, um Summen der i-ten Potenzen unbekannter Zahlen zu erhalten. Nennen Sie die Summen b _i .
• Verwenden Sie Newtons Identitäten, um Koeffizienten aus b _i zu berechnen . nenne sie c _i . Grundsätzlich ist c ₁ = b ₁ ; c ₂ = (c ₁ b ₁ - b ₂ ) / 2; genaue Formeln finden Sie in Wikipedia
• Faktor das Polynom x ^{k -} c ₁ x ^{k - 1} + ... + c _k .
• Die Wurzeln des Polynoms sind die benötigten Zahlen a ₁ , ..., a _k .

Finden Sie zum Variieren von k eine Primzahl n <= q <2n unter Verwendung von z. B. Miller-Rabin und führen Sie die Schritte mit allen Zahlen aus, die modulo q reduziert sind.

EDIT: In der vorherigen Version dieser Antwort wurde angegeben, dass anstelle von Z _q , wobei q eine Primzahl ist, ein endliches Feld der Charakteristik 2 verwendet werden kann (q = 2 ^ (log n)). Dies ist nicht der Fall, da Newtons Formeln eine Division durch Zahlen bis k erfordern.

Sie finden es, indem Sie die paar Seiten von Muthukrishnan - Data Stream Algorithms: Puzzle 1: Finding Missing Numbers lesen . Es zeigt genau die Verallgemeinerung, die Sie suchen . Wahrscheinlich hat Ihr Interviewer dies gelesen und warum er diese Fragen gestellt hat.

Wenn nun nur die Leute anfangen würden, die Antworten zu löschen, die von Muthukrishnans Behandlung subsumiert oder ersetzt werden, und diesen Text leichter zu finden machen würden. :) :)

Siehe auch die direkt verwandte Antwort von sdcvvc , die auch Pseudocode enthält (Hurra! Keine Notwendigkeit, diese kniffligen mathematischen Formulierungen zu lesen :)) (danke, großartige Arbeit!).

Wir können Q2 lösen, indem wir sowohl die Zahlen selbst als auch die Quadrate der Zahlen summieren .

Wir können das Problem dann auf reduzieren

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

Wo xund ywie weit liegen die Summen unter den erwarteten Werten?

Das Ersetzen gibt uns:

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

Was wir dann lösen können, um unsere fehlenden Zahlen zu bestimmen.

Wie @j_random_hacker hervorhob, ist dies dem Finden von Duplikaten in O (n) Zeit und O (1) Raum ziemlich ähnlich , und eine Anpassung meiner Antwort dort funktioniert auch hier.

Unter der Annahme, dass der "Beutel" durch ein 1-basiertes A[]Größenarray dargestellt wird N - k, können wir Qk O(N)zeitlich und zeitlich lösenO(k) räumlich .

Zuerst erweitern wir unser Array A[]um kElemente, sodass es jetzt die Größe hat N. Dies ist der O(k)zusätzliche Platz. Wir führen dann den folgenden Pseudocode-Algorithmus aus:

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

Die erste Schleife initialisiert die kzusätzlichen Einträge mit dem ersten Eintrag im Array (dies ist nur ein praktischer Wert, von dem wir wissen, dass er bereits im Array vorhanden ist - nach diesem Schritt alle Einträge, die im anfänglichen Array der Größe fehltenN-k sind fehlt noch im erweiterten Array).

Die zweite Schleife permutiert das erweiterte Array, sodass sich xeiner dieser Einträge an der Position befindet , wenn das Element mindestens einmal vorhanden ist A[x].

Beachten Sie, dass es zwar eine verschachtelte Schleife hat, aber dennoch ausgeführt wird O(N) rechtzeitig ausgeführt wird - ein Swap findet nur statt, wenn es einen isolchen gibt A[i] != i, und jeder Swap setzt mindestens ein Element so, dass A[i] == i, wo dies vorher nicht wahr war. Dies bedeutet, dass die Gesamtzahl der Swaps (und damit die Gesamtzahl der Ausführungen des whileSchleifenkörpers) höchstens beträgt N-1.

Die dritte Schleife druckt die Indizes des Arrays i, die nicht vom Wert belegt sindi - dies bedeutet, idass sie fehlten.

Ich habe einen 4-Jährigen gebeten, dieses Problem zu lösen. Er sortierte die Zahlen und zählte dann mit. Dies hat einen Platzbedarf von O (Küchenboden) und funktioniert genauso einfach, auch wenn viele Bälle fehlen.

Ich bin mir nicht sicher, ob es die effizienteste Lösung ist, aber ich würde alle Einträge durchlaufen und ein Bitset verwenden, um zu merken, welche Zahlen gesetzt sind, und dann auf 0 Bits testen.

Ich mag einfache Lösungen - und ich glaube sogar, dass es schneller sein könnte als die Berechnung der Summe oder der Summe der Quadrate usw.

Ich habe die Mathematik nicht überprüft, aber ich vermute, dass das Rechnen Σ(n^2)im selben Durchgang, den wir berechnen Σ(n), genügend Informationen liefert, um zwei fehlende Zahlen zu erhalten. Tun Sie dies Σ(n^3)auch, wenn drei vorhanden sind, und so weiter.

Das Problem bei Lösungen, die auf Zahlen basieren, besteht darin, dass sie die Kosten für das Speichern und Arbeiten mit Zahlen mit großen Exponenten nicht berücksichtigen. In der Praxis würde eine Bibliothek mit großen Zahlen verwendet, damit sie für sehr große n funktioniert . Wir können die Raumnutzung für diese Algorithmen analysieren.

Wir können die zeitliche und räumliche Komplexität der Algorithmen von sdcvvc und Dimitris Andreou analysieren.

Lager:

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)`

Damit l_j \in \Theta(j log n)

Insgesamt genutzter Speicher: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Verwendeter Speicherplatz: Unter der Annahme, dass das Rechnen Zeit a^jbraucht ceil(log_2 j), Gesamtzeit:

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)

Gesamtdauer: \Theta(kn log n)

Wenn diese Zeit und dieser Raum zufriedenstellend sind, können Sie einen einfachen rekursiven Algorithmus verwenden. Sei b! I der i-te Eintrag in der Tasche, n die Anzahl der Nummern vor dem Umzug und k die Anzahl der Umzüge. In der Haskell-Syntax ...

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

Verwendeter Speicher: O(k)für Liste, O(log(n))für Stapel: O(k + log(n)) Dieser Algorithmus ist intuitiver, hat dieselbe zeitliche Komplexität und benötigt weniger Speicherplatz.

Warte eine Minute. Wie die Frage schon sagt, befinden sich 100 Nummern in der Tasche. Egal wie groß k ist, das Problem kann in konstanter Zeit gelöst werden, da Sie eine Menge verwenden und Zahlen in höchstens 100-k-Iterationen einer Schleife aus der Menge entfernen können. 100 ist konstant. Der Satz der verbleibenden Zahlen ist Ihre Antwort.

Wenn wir die Lösung auf die Zahlen von 1 bis N verallgemeinern, ändert sich nichts, außer dass N keine Konstante ist, also sind wir in der Zeit O (N - k) = O (N). Wenn wir zum Beispiel einen Bit-Satz verwenden, setzen wir die Bits in O (N) -Zeit auf 1, durchlaufen die Zahlen, setzen die Bits im Laufe der Zeit auf 0 (O (Nk) = O (N)) und dann wir habe die Antwort.

Es scheint mir, dass der Interviewer Sie gefragt hat, wie Sie den Inhalt des endgültigen Satzes in O (k) -Zeit und nicht in O (N) -Zeit ausdrucken sollen . Wenn ein Bit gesetzt ist, müssen Sie natürlich alle N Bits durchlaufen, um zu bestimmen, ob Sie die Nummer drucken sollen oder nicht. Wenn Sie jedoch die Art und Weise ändern, in der das Set implementiert ist, können Sie die Zahlen in k Iterationen ausdrucken. Dazu werden die Zahlen in ein Objekt eingefügt, das sowohl in einem Hash-Set als auch in einer doppelt verknüpften Liste gespeichert werden soll. Wenn Sie ein Objekt aus dem Hash-Set entfernen, entfernen Sie es auch aus der Liste. Die Antworten bleiben in der Liste, die jetzt die Länge k hat.

Um die Frage nach 2 (und 3) fehlenden Zahlen zu lösen, können Sie Änderungen vornehmen quickselect, die im Durchschnitt ausgeführt werden O(n)und konstanten Speicher verwenden, wenn die Partitionierung direkt erfolgt.

1. Partitionieren Sie die Menge in Bezug auf einen zufälligen Pivot pin Partitionen l, die Zahlen enthalten, die kleiner als der Pivot sind, und rdie Zahlen enthalten, die größer als der Pivot sind.

2. Bestimmen Sie, in welchen Partitionen sich die 2 fehlenden Zahlen befinden, indem Sie den Pivot-Wert mit der Größe jeder Partition ( p - 1 - count(l) = count of missing numbers in lund n - count(r) - p = count of missing numbers in r) vergleichen.

3. a) Wenn jeder Partition eine Nummer fehlt, verwenden Sie den Summenunterschiedsansatz, um jede fehlende Nummer zu finden.

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

   b) Wenn einer Partition beide Nummern fehlen und die Partition leer ist, sind die fehlenden Nummern entweder (p-1,p-2)oder (p+1,p+2) abhängig davon, auf welcher Partition die Nummern fehlen.

   Wenn einer Partition 2 Zahlen fehlen, diese aber nicht leer ist, kehren Sie zu dieser Partition zurück.

Mit nur 2 fehlenden Zahlen verwirft dieser Algorithmus immer mindestens eine Partition, sodass er erhalten bleibt O(n) durchschnittliche Zeitkomplexität der Schnellauswahl erhalten bleibt. In ähnlicher Weise verwirft dieser Algorithmus bei 3 fehlenden Nummern bei jedem Durchgang mindestens eine Partition (da wie bei 2 fehlenden Nummern höchstens 1 Partition mehrere fehlende Nummern enthält). Ich bin mir jedoch nicht sicher, um wie viel die Leistung abnimmt, wenn weitere fehlende Zahlen hinzugefügt werden.

Hier ist eine Implementierung, die keine direkte Partitionierung verwendet, sodass dieses Beispiel den Platzbedarf nicht erfüllt, aber die Schritte des Algorithmus veranschaulicht:

<?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

Hier ist eine Lösung, die k Bit zusätzlichen Speicherplatzes verwendet, ohne clevere Tricks und einfach. Ausführungszeit O (n), zusätzlicher Raum O (k). Nur um zu beweisen, dass dies gelöst werden kann, ohne zuerst die Lösung zu lesen oder ein Genie zu sein:

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 >= even) ++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 = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

Können Sie überprüfen, ob jede Nummer vorhanden ist? Wenn ja, können Sie dies versuchen:

S = Summe aller Zahlen im Beutel (S <5050)
Z = Summe der fehlenden Zahlen 5050 - S.

wenn die fehlenden Zahlen sind xund ydann:

x = Z - y und
max (x) = Z - 1

Sie überprüfen also den Bereich von 1bis max(x)und finden die Nummer

Möglicherweise kann dieser Algorithmus für Frage 1 funktionieren:

1. Berechne xor der ersten 100 ganzen Zahlen vor (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
2. xoder die Elemente, wie sie immer wieder aus dem Eingabestream kommen (val1 = val1 ^ next_input)
3. endgültige Antwort = val ^ val1

Oder noch besser:

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

Dieser Algorithmus kann tatsächlich für zwei fehlende Zahlen erweitert werden. Der erste Schritt bleibt gleich. Wenn wir GetValue mit zwei fehlenden Nummern aufrufen, sind die beiden fehlenden Nummern das Ergebnis a1^a2. Sagen wir

val = a1^a2

Um nun a1 und a2 aus val herauszusieben, nehmen wir ein beliebiges gesetztes Bit in val. Nehmen wir an, das ithBit ist in val gesetzt. Das bedeutet, dass a1 und a2 an der ithBitposition unterschiedliche Paritäten haben . Jetzt führen wir eine weitere Iteration des ursprünglichen Arrays durch und behalten zwei xor-Werte bei. Eine für die Zahlen, bei denen das i-te Bit gesetzt ist, und eine andere, bei der das i-te Bit nicht gesetzt ist. Wir haben jetzt zwei Eimer mit Zahlen, und es wird garantiert, dass a1 and a2sie in verschiedenen Eimern liegen. Wiederholen Sie nun dasselbe, was wir getan haben, um auf jedem Eimer ein fehlendes Element zu finden.

Sie können Q2 lösen, wenn Sie die Summe beider Listen und das Produkt beider Listen haben.

(l1 ist das Original, l2 ist die geänderte Liste)

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

Wir können dies optimieren, da die Summe einer arithmetischen Reihe das n-fache des Durchschnitts des ersten und letzten Terms beträgt:

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

Jetzt wissen wir das (wenn a und b die entfernten Zahlen sind):

a + b = d
a * b = m

So können wir neu anordnen zu:

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

Und multiplizieren:

-b^2 + s*b = m

Und ordnen Sie neu an, so dass die rechte Seite Null ist:

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

Dann können wir mit der quadratischen Formel lösen:

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

Beispiel für Python 3-Code:

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

Ich kenne die Komplexität der Funktionen sqrt, redu und sum nicht, daher kann ich die Komplexität dieser Lösung nicht herausfinden (wenn jemand etwas weiß, kommentieren Sie dies bitte unten.)

Für Q2 ist dies eine Lösung, die etwas ineffizienter als die anderen ist, aber dennoch eine O (N) -Laufzeit hat und O (k) Speicherplatz beansprucht.

Die Idee ist, den ursprünglichen Algorithmus zweimal auszuführen. In der ersten erhalten Sie eine fehlende Gesamtzahl, wodurch Sie eine Obergrenze der fehlenden Zahlen erhalten. Rufen wir diese Nummer an N. Sie wissen, dass sich die fehlenden zwei Zahlen summieren werden N, sodass die erste Zahl nur in dem Intervall liegen kann, [1, floor((N-1)/2)]während die zweite in sein wird [floor(N/2)+1,N-1].

Auf diese Weise durchlaufen Sie erneut alle Zahlen und verwerfen alle Zahlen, die nicht im ersten Intervall enthalten sind. Diejenigen, die sind, behalten Sie ihre Summe im Auge. Schließlich kennen Sie eine der beiden fehlenden Zahlen und im weiteren Sinne die zweite.

Ich habe das Gefühl, dass diese Methode verallgemeinert werden könnte und möglicherweise mehrere Suchvorgänge während eines einzelnen Durchlaufs über die Eingabe "parallel" ausgeführt werden, aber ich habe noch nicht herausgefunden, wie.

Ich denke, dies kann ohne komplexe mathematische Gleichungen und Theorien geschehen. Nachfolgend finden Sie einen Vorschlag für eine vorhandene und O (2n) -Zeitkomplexitätslösung:

Annahmen zum Eingabeformular:

Anzahl der Zahlen im Beutel = n

Anzahl fehlender Zahlen = k

Die Zahlen in der Tasche werden durch ein Array der Länge n dargestellt

Länge des Eingabearrays für das Algo = n

Fehlende Einträge im Array (Zahlen aus der Tasche) werden durch den Wert des ersten Elements im Array ersetzt.

Z.B. Anfangs sieht die Tasche aus wie [2,9,3,7,8,6,4,5,1,10]. Wenn 4 herausgenommen wird, wird der Wert 4 zu 2 (dem ersten Element des Arrays). Daher sieht die Tasche nach dem Herausnehmen von 4 wie folgt aus: [2,9,3,7,8,6,2,5,1,10]

Der Schlüssel zu dieser Lösung besteht darin, den INDEX einer besuchten Nummer zu markieren, indem der Wert an diesem INDEX beim Durchlaufen des Arrays negiert wird.

    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;
    }

Es gibt eine allgemeine Möglichkeit, solche Streaming-Algorithmen zu verallgemeinern. Die Idee ist, ein bisschen Randomisierung zu verwenden, um die kElemente hoffentlich in unabhängige Unterprobleme zu "verteilen" , wobei unser ursprünglicher Algorithmus das Problem für uns löst. Diese Technik wird unter anderem bei der Rekonstruktion spärlicher Signale eingesetzt.

• Machen Sie ein Array avon Größe u = k^2.
• Wählen Sie eine beliebige Universal-Hash - Funktion , h : {1,...,n} -> {1,...,u}. (Wie Multiplikationsverschiebung )
• Für jeden iin 1, ..., nErhöhunga[h(i)] += i
• xDekrementieren Sie für jede Zahl im Eingabestream a[h(x)] -= x.

Wenn alle fehlenden Zahlen in verschiedene Buckets gehasht wurden, enthalten die Nicht-Null-Elemente des Arrays jetzt die fehlenden Zahlen.

Die Wahrscheinlichkeit, dass ein bestimmtes Paar an denselben Bucket gesendet wird, ist geringer als 1/uper Definition einer universellen Hash-Funktion. Da es ungefähr k^2/2Paare gibt, haben wir, dass die Fehlerwahrscheinlichkeit höchstens ist k^2/2/u=1/2. Das heißt, wir schaffen es mit einer Wahrscheinlichkeit von mindestens 50% und wenn wir zunehmenu uns erhöhen, wir unsere Chancen.

Beachten Sie, dass dieser Algorithmus Platz beansprucht k^2 logn(wir benötigen lognBits pro Array-Bucket). Dies entspricht dem Platz, der in der Antwort von @Dimitris Andreou benötigt wird (insbesondere dem Platzbedarf der Polynomfaktorisierung, der zufällig ebenfalls randomisiert wird.) Dieser Algorithmus hat ebenfalls eine Konstante Zeit pro Update, statt Zeit kbei Leistungssummen.

Tatsächlich können wir mit dem in den Kommentaren beschriebenen Trick sogar effizienter als die Leistungssummenmethode sein.

Eine sehr einfache Lösung für das zweite Quartal, von der ich überrascht bin, dass noch niemand geantwortet hat. Verwenden Sie die Methode aus Q1, um die Summe der beiden fehlenden Zahlen zu ermitteln. Bezeichnen wir es mit S, dann ist eine der fehlenden Zahlen kleiner als S / 2 und die andere größer als S / 2 (duh). Summieren Sie alle Zahlen von 1 bis S / 2 und vergleichen Sie sie mit dem Ergebnis der Formel (ähnlich der Methode in Q1), um die niedrigere Zahl zwischen den fehlenden Zahlen zu ermitteln. Subtrahieren Sie es von S, um die größere fehlende Zahl zu finden.

Sehr schönes Problem. Ich würde einen festgelegten Unterschied für Qk verwenden. Viele Programmiersprachen unterstützen dies sogar, wie in Ruby:

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

Es ist wahrscheinlich nicht die effizienteste Lösung, aber es ist eine, die ich im wirklichen Leben verwenden würde, wenn ich in diesem Fall vor einer solchen Aufgabe stünde (bekannte Grenzen, niedrige Grenzen). Wenn die Anzahl sehr groß wäre, würde ich natürlich einen effizienteren Algorithmus in Betracht ziehen, aber bis dahin würde mir die einfache Lösung ausreichen.

Sie können versuchen, einen Bloom-Filter zu verwenden . Fügen Sie jede Zahl in den Beutel in die Blüte ein und durchlaufen Sie dann den gesamten 1-k-Satz, bis jede nicht gefundene gemeldet wird. Dies findet möglicherweise nicht in allen Szenarien die Antwort, ist jedoch möglicherweise eine ausreichend gute Lösung.

Ich würde diese Frage anders angehen und den Interviewer auf weitere Details zu dem größeren Problem untersuchen, das er zu lösen versucht. Abhängig vom Problem und den damit verbundenen Anforderungen ist die offensichtliche satzbasierte Lösung möglicherweise das Richtige und der Ansatz, eine Liste zu erstellen und anschließend durchzusuchen, möglicherweise nicht.

Zum Beispiel könnte es sein, dass der Interviewer nNachrichten versendet und wissen muss k, was nicht zu einer Antwort geführt hat, und dass er es in möglichst kurzer Wanduhrzeit nach dem wissen muss . Danach enthält das Set die Liste der fehlenden Elemente und es ist keine zusätzliche Verarbeitung erforderlich.n-k Eingang der Antwort . Nehmen wir auch an, dass der Nachrichtenkanal so beschaffen ist, dass selbst bei voller Auslastung genügend Zeit für die Verarbeitung zwischen Nachrichten bleibt, ohne dass sich dies darauf auswirkt, wie lange es dauert, bis das Endergebnis nach dem Eintreffen der letzten Antwort erstellt wird. Diese Zeit kann genutzt werden, um eine identifizierende Facette jeder gesendeten Nachricht in einen Satz einzufügen und sie zu löschen, wenn jede entsprechende Antwort eintrifft. Sobald die letzte Antwort eingetroffen ist, müssen Sie nur noch die Kennung aus dem Satz entfernen, was in typischen Implementierungen erforderlich istO(log k+1)k

Dies ist sicherlich nicht der schnellste Ansatz für die Stapelverarbeitung vorgenerierter Zahlenbeutel, da das Ganze läuft O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)). Es funktioniert jedoch für jeden Wert von k(auch wenn es nicht im Voraus bekannt ist) und wurde im obigen Beispiel so angewendet, dass das kritischste Intervall minimiert wird.

Sie können die Lösung motivieren, indem Sie sie in Form von Symmetrien (Gruppen, in mathematischer Sprache) betrachten. Unabhängig von der Reihenfolge der Zahlen sollte die Antwort dieselbe sein. Wenn Sie kFunktionen verwenden möchten, um die fehlenden Elemente zu ermitteln, sollten Sie sich überlegen, welche Funktionen diese Eigenschaft haben: symmetrisch. Die Funktion s_1(x) = x_1 + x_2 + ... + x_nist ein Beispiel für eine symmetrische Funktion, aber es gibt andere von höherem Grad. Berücksichtigen Sie insbesondere die elementaren symmetrischen Funktionen . Die elementare symmetrische Funktion des Grades 2 ist s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_ndie Summe aller Produkte zweier Elemente. Ähnliches gilt für die elementaren symmetrischen Funktionen des Grades 3 und höher. Sie sind offensichtlich symmetrisch. Darüber hinaus stellt sich heraus, dass sie die Bausteine ​​für alle symmetrischen Funktionen sind.

Sie können die elementaren symmetrischen Funktionen erstellen, indem Sie dies beachten s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Weitere Überlegungen sollten Sie davon überzeugen s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))und so weiter, damit sie in einem Durchgang berechnet werden können.

Wie können wir feststellen, welche Elemente im Array fehlten? Denken Sie an das Polynom (z-x_1)(z-x_2)...(z-x_n). Es wird ausgewertet, 0ob Sie eine der Zahlen eingeben x_i. Wenn Sie das Polynom erweitern, erhalten Sie z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. Die elementaren symmetrischen Funktionen erscheinen auch hier, was wirklich keine Überraschung ist, da das Polynom gleich bleiben sollte, wenn wir eine Permutation auf die Wurzeln anwenden.

Wir können also das Polynom bauen und versuchen, es zu faktorisieren, um herauszufinden, welche Zahlen nicht in der Menge enthalten sind, wie andere erwähnt haben.

Wenn wir uns schließlich Gedanken über ein Überlaufen des Speichers mit großen Zahlen machen (das n-te symmetrische Polynom liegt in der Größenordnung 100!), können wir diese Berechnungen durchführen, mod pwenn peine Primzahl größer als 100 ist. In diesem Fall bewerten wir das Polynom mod pund stellen fest, dass es erneut ausgewertet wird bis, 0wenn die Eingabe eine Zahl in der Menge ist, und es wird ein Wert ungleich Null ausgewertet, wenn die Eingabe eine Zahl ist, die nicht in der Menge enthalten ist. Wie andere bereits betont haben , müssen wir das Polynom faktorisieren, um die Werte aus dem Polynom in einer Zeit herauszuholen, die davon abhängt k, und nicht davon .Nmod p

Ein weiterer Weg ist die Verwendung der Restgraphenfilterung.

Angenommen, wir haben die Nummern 1 bis 4 und 3 fehlt. Die binäre Darstellung ist die folgende:

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

Und ich kann ein Flussdiagramm wie das folgende erstellen.

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

Beachten Sie, dass das Flussdiagramm x Knoten enthält, während x die Anzahl der Bits ist. Und die maximale Anzahl von Kanten beträgt (2 * x) -2.

Für eine 32-Bit-Ganzzahl wird also O (32) oder O (1) benötigt.

Wenn ich nun die Kapazität für jede Zahl ab 1,2,4 entferne, bleibt ein Restdiagramm übrig.

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

Zum Schluss werde ich eine Schleife wie die folgende ausführen:

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

Jetzt enthält das Ergebnis resultZahlen, die ebenfalls nicht fehlen (falsch positiv). Aber das k <= (Größe des Ergebnisses) <= n, wenn kElemente fehlen.

Ich werde die angegebene Liste ein letztes Mal durchgehen, um zu markieren, ob das Ergebnis fehlt oder nicht.

Die zeitliche Komplexität ist also O (n).

Schließlich ist es möglich , die Anzahl der falsch positiven (und den Raum erforderlich) , indem Knoten zu reduzieren 00, 01, 11, 10statt nur 0und 1.

Sie müssten wahrscheinlich klären, was O (k) bedeutet.

Hier ist eine triviale Lösung für beliebiges k: Akkumulieren Sie für jedes v in Ihrer Zahlenmenge die Summe von 2 ^ v. Am Ende Schleife i von 1 nach N. Wenn die Summe bitweise UND mit 2 ^ i Null ist, fehlt i. (Oder numerisch, wenn der Boden der Summe geteilt durch 2 ^ i gerade ist. Or sum modulo 2^(i+1)) < 2^i.)

Einfach richtig? O (N) Zeit, O (1) Speicherung, und es unterstützt beliebiges k.

Abgesehen davon, dass Sie enorme Zahlen berechnen, die auf einem realen Computer jeweils O (N) Speicherplatz benötigen würden. Tatsächlich ist diese Lösung mit einem Bitvektor identisch.

Sie könnten also klug sein und die Summe und die Summe der Quadrate und die Summe der Würfel ... bis zur Summe von v ^ k berechnen und die ausgefallene Mathematik durchführen, um das Ergebnis zu extrahieren. Aber das sind auch große Zahlen, was die Frage aufwirft: Von welchem ​​abstrakten Betriebsmodell sprechen wir? Wie viel passt in den O (1) -Raum und wie lange dauert es, Zahlen beliebiger Größe zusammenzufassen?

Hier ist eine Lösung, die sich nicht auf komplexe Mathematik stützt wie die Antworten von sdcvvc / Dimitris Andreou, das Eingabearray nicht wie bei caf und Colonel Panic ändert und das Bitset von enormer Größe nicht wie Chris Lercher, JeremyP und verwendet viele andere taten es. Grundsätzlich begann ich mit der Idee von Svalorzen / Gilad Deutch für Q2, verallgemeinerte sie auf den allgemeinen Fall Qk und implementierte sie in Java, um zu beweisen, dass der Algorithmus funktioniert.

Die Idee

Angenommen, wir haben ein beliebiges Intervall I, von dem wir nur wissen, dass es mindestens eine der fehlenden Zahlen enthält. Nach einem Durchgang durch das Eingabearray , wobei wir nur die Zahlen von I betrachten , können wir sowohl die Summe S als auch die Menge Q der fehlenden Zahlen von I erhalten . Wir tun dies, indem wir einfach die Länge von I jedes Mal verringern, wenn wir auf eine Zahl von I stoßen (um Q zu erhalten ) und indem wir die vorberechnete Summe aller Zahlen in I jedes Mal um diese angetroffene Zahl verringern (um S zu erhalten ).

Nun schauen wir uns S und Q an . Wenn Q = 1 , bedeutet dies , dass dann ich enthalten nur eine der fehlenden Zahlen, und diese Zahl ist deutlich S . Wir markieren I als fertig (es wird im Programm als "eindeutig" bezeichnet) und lassen es von weiteren Überlegungen aus. Wenn andererseits Q> 1 ist , können wir den Durchschnitt A = S / Q der in I enthaltenen fehlenden Zahlen berechnen . Da alle Zahlen verschieden sind, wobei mindestens eine dieser Zahlen ist strikt kleiner als A und mindestens ein streng größer als ist A . Jetzt teilen wir mich in A.in zwei kleinere Intervalle, von denen jedes mindestens eine fehlende Zahl enthält. Beachten Sie, dass es keine Rolle spielt, welchem ​​der Intervalle wir A zuweisen, falls es sich um eine Ganzzahl handelt.

Wir machen den nächsten Array-Durchgang, indem wir S und Q für jedes der Intervalle separat berechnen (aber im selben Durchgang) und danach Intervalle mit Q = 1 markieren und Intervalle mit Q> 1 teilen . Wir setzen diesen Prozess fort, bis es keine neuen "mehrdeutigen" Intervalle mehr gibt, dh wir haben nichts zu teilen, da jedes Intervall genau eine fehlende Zahl enthält (und wir kennen diese Zahl immer, weil wir S kennen ). Wir beginnen mit dem einzigen "gesamten Bereich" -Intervall, das alle möglichen Zahlen enthält (wie [1..N] in der Frage).

Zeit- und Raumkomplexitätsanalyse

Die Gesamtzahl der Durchgänge p, die wir machen müssen, bis der Prozess stoppt, ist niemals größer als die Anzahl der fehlenden Zahlen k . Die Ungleichung p <= k kann rigoros bewiesen werden. Andererseits gibt es auch eine empirische Obergrenze p <log ₂ N + 3 , die für große Werte von k nützlich ist . Wir müssen eine binäre Suche für jede Nummer des Eingabearrays durchführen, um das Intervall zu bestimmen, zu dem es gehört. Dies addiert den log k- Multiplikator zur Zeitkomplexität.

Insgesamt beträgt die zeitliche Komplexität O (N ≤ min (k, log N) ≤ log k) . Beachten Sie, dass dies für großes k signifikant besser ist als für die Methode von sdcvvc / Dimitris Andreou, die O (N ᛫ k) ist .

Für seine Arbeit benötigt der Algorithmus O (k) zusätzlichen Speicherplatz zum Speichern in den meisten k Intervallen, was in "Bitset" -Lösungen signifikant besser ist als O (N) .

Java-Implementierung

Hier ist eine Java-Klasse, die den obigen Algorithmus implementiert. Es wird immer ein sortiertes Array fehlender Zahlen zurückgegeben. Außerdem müssen die fehlenden Zahlen nicht k gezählt werden, da sie im ersten Durchgang berechnet werden. Der gesamte Zahlenbereich wird durch die Parameter minNumberund maxNumberangegeben (z. B. 1 und 100 für das erste Beispiel in der Frage).

public class MissingNumbers {
    private static class Interval {
        boolean ambiguous = true;
        final int begin;
        int quantity;
        long sum;

        Interval(int begin, int end) { // begin inclusive, end exclusive
            this.begin = begin;
            quantity = end - begin;
            sum = quantity * ((long)end - 1 + begin) / 2;
        }

        void exclude(int x) {
            quantity--;
            sum -= x;
        }
    }

    public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
        Interval full = new Interval(minNumber, ++maxNumber);
        for (inputBag.startOver(); inputBag.hasNext();)
            full.exclude(inputBag.next());
        int missingCount = full.quantity;
        if (missingCount == 0)
            return new int[0];
        Interval[] intervals = new Interval[missingCount];
        intervals[0] = full;
        int[] dividers = new int[missingCount];
        dividers[0] = minNumber;
        int intervalCount = 1;
        while (true) {
            int oldCount = intervalCount;
            for (int i = 0; i < oldCount; i++) {
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    if (itv.quantity == 1) // number inside itv uniquely identified
                        itv.ambiguous = false;
                    else
                        intervalCount++; // itv will be split into two intervals
            }
            if (oldCount == intervalCount)
                break;
            int newIndex = intervalCount - 1;
            int end = maxNumber;
            for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
                // newIndex always >= oldIndex
                Interval itv = intervals[oldIndex];
                int begin = itv.begin;
                if (itv.ambiguous) {
                    // split interval itv
                    // use floorDiv instead of / because input numbers can be negative
                    int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
                    intervals[newIndex--] = new Interval(mean, end);
                    intervals[newIndex--] = new Interval(begin, mean);
                } else
                    intervals[newIndex--] = itv;
                end = begin;
            }
            for (int i = 0; i < intervalCount; i++)
                dividers[i] = intervals[i].begin;
            for (inputBag.startOver(); inputBag.hasNext();) {
                int x = inputBag.next();
                // find the interval to which x belongs
                int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
                if (i < 0)
                    i = -i - 2;
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    itv.exclude(x);
            }
        }
        assert intervalCount == missingCount;
        for (int i = 0; i < intervalCount; i++)
            dividers[i] = (int)intervals[i].sum;
        return dividers;
    }
}

Aus Fairnessgründen erhält diese Klasse Eingaben in Form von NumberBagObjekten. NumberBagErmöglicht keine Änderung des Arrays und keinen wahlfreien Zugriff und zählt auch, wie oft das Array zum sequentiellen Durchlaufen angefordert wurde. Es ist auch besser für Tests mit großen Arrays geeignet, als Iterable<Integer>weil es das Boxen primitiver intWerte vermeidet und das Umwickeln eines Teils eines großen int[]Werts für eine bequeme Testvorbereitung ermöglicht. Es ist nicht schwer zu ersetzen, falls gewünscht, NumberBagdurch int[]oder Iterable<Integer>in dem Typ findSignatur, die von zwei wechselnden for-Schleifen in ihnen in foreach denjenigen.

import java.util.*;

public abstract class NumberBag {
    private int passCount;

    public void startOver() {
        passCount++;
    }

    public final int getPassCount() {
        return passCount;
    }

    public abstract boolean hasNext();

    public abstract int next();

    // A lightweight version of Iterable<Integer> to avoid boxing of int
    public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
        return new NumberBag() {
            int index = toIndex;

            public void startOver() {
                super.startOver();
                index = fromIndex;
            }

            public boolean hasNext() {
                return index < toIndex;
            }

            public int next() {
                if (index >= toIndex)
                    throw new NoSuchElementException();
                return base[index++];
            }
        };
    }

    public static NumberBag fromArray(int[] base) {
        return fromArray(base, 0, base.length);
    }

    public static NumberBag fromIterable(Iterable<Integer> base) {
        return new NumberBag() {
            Iterator<Integer> it;

            public void startOver() {
                super.startOver();
                it = base.iterator();
            }

            public boolean hasNext() {
                return it.hasNext();
            }

            public int next() {
                return it.next();
            }
        };
    }
}

Tests

Nachfolgend finden Sie einfache Beispiele für die Verwendung dieser Klassen.

import java.util.*;

public class SimpleTest {
    public static void main(String[] args) {
        int[] input = { 7, 1, 4, 9, 6, 2 };
        NumberBag bag = NumberBag.fromArray(input);
        int[] output = MissingNumbers.find(1, 10, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
                Arrays.toString(input), Arrays.toString(output), bag.getPassCount());

        List<Integer> inputList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            inputList.add(2 * i);
        Collections.shuffle(inputList);
        bag = NumberBag.fromIterable(inputList);
        output = MissingNumbers.find(0, 19, bag);
        System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
                inputList, Arrays.toString(output), bag.getPassCount());

        // Sieve of Eratosthenes
        final int MAXN = 1_000;
        List<Integer> nonPrimes = new ArrayList<>();
        nonPrimes.add(1);
        int[] primes;
        int lastPrimeIndex = 0;
        while (true) {
            primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
            int p = primes[lastPrimeIndex]; // guaranteed to be prime
            int q = p;
            for (int i = lastPrimeIndex++; i < primes.length; i++) {
                q = primes[i]; // not necessarily prime
                int pq = p * q;
                if (pq > MAXN)
                    break;
                nonPrimes.add(pq);
            }
            if (q == p)
                break;
        }
        System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
                primes.length, MAXN);
        for (int i = 0; i < primes.length; i++)
            System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
    }
}

Tests mit großen Arrays können folgendermaßen durchgeführt werden:

import java.util.*;

public class BatchTest {
    private static final Random rand = new Random();
    public static int MIN_NUMBER = 1;
    private final int minNumber = MIN_NUMBER;
    private final int numberCount;
    private final int[] numbers;
    private int missingCount;
    public long finderTime;

    public BatchTest(int numberCount) {
        this.numberCount = numberCount;
        numbers = new int[numberCount];
        for (int i = 0; i < numberCount; i++)
            numbers[i] = minNumber + i;
    }

    private int passBound() {
        int mBound = missingCount > 0 ? missingCount : 1;
        int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
        return Math.min(mBound, nBound);
    }

    private void error(String cause) {
        throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
    }

    // returns the number of times the input array was traversed in this test
    public int makeTest(int missingCount) {
        this.missingCount = missingCount;
        // numbers array is reused when numberCount stays the same,
        // just Fisher–Yates shuffle it for each test
        for (int i = numberCount - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            if (i != j) {
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
        final int bagSize = numberCount - missingCount;
        NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
        finderTime -= System.nanoTime();
        int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
        finderTime += System.nanoTime();
        if (inputBag.getPassCount() > passBound())
            error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
        if (found.length != missingCount)
            error("wrong result length");
        int j = bagSize; // "missing" part beginning in numbers
        Arrays.sort(numbers, bagSize, numberCount);
        for (int i = 0; i < missingCount; i++)
            if (found[i] != numbers[j++])
                error("wrong result array, " + i + "-th element differs");
        return inputBag.getPassCount();
    }

    public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
        BatchTest t = new BatchTest(numberCount);
        System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
        for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
            int minPass = Integer.MAX_VALUE;
            int passSum = 0;
            int maxPass = 0;
            t.finderTime = 0;
            for (int j = 1; j <= repeats; j++) {
                int pCount = t.makeTest(missingCount);
                if (pCount < minPass)
                    minPass = pCount;
                passSum += pCount;
                if (pCount > maxPass)
                    maxPass = pCount;
            }
            System.out.format("║ %9d  %9d  ║  %2d  %5.2f  %2d  ║  %11.3f    ║%n", missingCount, numberCount, minPass,
                    (double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
        }
    }

    public static void main(String[] args) {
        System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
        System.out.println("║      Number count     ║      Passes     ║  Average time   ║");
        System.out.println("║   missimg     total   ║  min  avg   max ║ per search (ms) ║");
        long time = System.nanoTime();
        strideCheck(100, 0, 100, 1, 20_000);
        strideCheck(100_000, 2, 99_998, 1_282, 15);
        MIN_NUMBER = -2_000_000_000;
        strideCheck(300_000_000, 1, 10, 1, 1);
        time = System.nanoTime() - time;
        System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
        System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
    }
}

Probieren Sie sie auf Ideone aus

Ich glaube, ich habe einen O(k)Zeit- und O(log(k))Raumalgorithmus, vorausgesetzt, Sie haben die floor(x)und log2(x)-Funktionen für beliebig große ganze Zahlen zur Verfügung:

Sie haben eine k-bit lange Ganzzahl (daher das log8(k)Leerzeichen), in der Sie die x^2Zahl hinzufügen , wobei x die nächste Zahl ist, die Sie in der Tasche finden: s=1^2+2^2+...Dies braucht O(N)Zeit (was für den Interviewer kein Problem ist). Am Ende erhalten Sie j=floor(log2(s))die größte Zahl, die Sie suchen. Dann s=s-jund du machst nochmal das oben genannte:

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

Jetzt haben Sie normalerweise keine 2756Floor- und Log2-Funktionen für -bit-Ganzzahlen, sondern für Doubles. Damit? Sie können diese Funktionen einfach für jeweils 2 Bytes (oder 1, 3 oder 4) verwenden, um die gewünschten Zahlen zu erhalten. Dies erhöht jedoch die O(N)Zeitkomplexität

Das mag dumm klingen, aber bei dem ersten Problem, das Ihnen präsentiert wird, müssten Sie alle verbleibenden Zahlen in der Tasche sehen, um sie tatsächlich zu addieren und die fehlende Zahl anhand dieser Gleichung zu finden.

Da Sie also alle Zahlen sehen können, suchen Sie einfach nach der fehlenden Zahl. Gleiches gilt, wenn zwei Zahlen fehlen. Ziemlich einfach finde ich. Es macht keinen Sinn, eine Gleichung zu verwenden, wenn Sie die in der Tasche verbleibenden Zahlen sehen.

Ich denke, das kann so verallgemeinert werden:

Bezeichnen Sie S, M als Anfangswerte für die Summe von arithmetischen Reihen und Multiplikationen.

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

Ich sollte über eine Formel nachdenken, um dies zu berechnen, aber das ist nicht der Punkt. Wenn eine Nummer fehlt, haben Sie die Lösung bereits bereitgestellt. Wenn jedoch zwei Zahlen fehlen, bezeichnen wir die neue Summe und das Gesamtmultiplikator mit S1 und M1, die wie folgt lauten:

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

Where a and b are the missing numbers.

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

Da Sie S1, M1, M und S kennen, ist die obige Gleichung lösbar, um a und b, die fehlenden Zahlen, zu finden.

Nun zu den drei fehlenden Zahlen:

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

Where a and b are the missing numbers.

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

Jetzt ist Ihr Unbekannter 3, während Sie nur zwei Gleichungen haben, aus denen Sie lösen können.

Ich weiß nicht, ob dies effizient ist oder nicht, aber ich möchte diese Lösung vorschlagen.

1. Berechnen Sie xor der 100 Elemente
2. Berechnen Sie xor der 98 Elemente (nachdem die 2 Elemente entfernt wurden)
3. Jetzt (Ergebnis von 1) XOR (Ergebnis von 2) gibt Ihnen das xor der beiden fehlenden Nos i..ea XOR b, wenn a und b die fehlenden Elemente sind.
   4. Erhalten Sie die Summe der fehlenden Nos mit Ihrem üblichen Ansatz von Summenformel diff und sagen wir, der Diff ist d.

Führen Sie nun eine Schleife aus, um die möglichen Paare (p, q) zu erhalten, die beide in [1, 100] liegen und zu d summieren.

Wenn ein Paar erhalten wird, prüfen Sie, ob (Ergebnis von 3) XOR p = q ist und ob wir fertig sind.

Bitte korrigieren Sie mich, wenn ich falsch liege, und kommentieren Sie auch die zeitliche Komplexität, wenn dies korrekt ist

Wir können Q1 und Q2 die meiste Zeit in O (log n) ausführen.

Angenommen, unser memory chipbesteht aus einem Array von nAnzahl von test tubes. Und eine Zahl xim Reagenzglas wird durch x milliliterchemische Flüssigkeit dargestellt.

Angenommen, unser Prozessor ist a laser light. Wenn wir den Laser anzünden, durchläuft er alle Röhren senkrecht zu seiner Länge. Jedes Mal, wenn es durch die chemische Flüssigkeit gelangt, wird die Leuchtkraft um verringert 1. Und das Licht bei einer bestimmten Milliliter-Marke zu passieren, ist eine Operation von O(1).

Wenn wir nun unseren Laser in der Mitte des Reagenzglases anzünden und die Helligkeitsleistung erhalten

• gleich einem vorberechneten Wert (berechnet, wenn keine Zahlen fehlten), dann sind die fehlenden Zahlen größer als n/2.
• Wenn unsere Ausgabe kleiner ist, fehlt mindestens eine Zahl, die kleiner als ist n/2. Wir können auch überprüfen, ob die Leuchtkraft um 1oder verringert ist 2. Wenn es bis dahin reduziert wird, 1ist eine fehlende Zahl kleiner als n/2und die andere größer als n/2. Wenn es bis dahin reduziert 2ist, sind beide Zahlen kleiner als n/2.

Wir können den obigen Vorgang immer wieder wiederholen und unsere Problemdomäne eingrenzen. In jedem Schritt verkleinern wir die Domain um die Hälfte. Und schließlich können wir zu unserem Ergebnis gelangen.

Erwähnenswerte parallele Algorithmen (weil sie interessant sind),

• Das Sortieren nach einem parallelen Algorithmus, beispielsweise das parallele Zusammenführen, kann zeitlich erfolgen O(log^3 n). Und dann kann die fehlende Nummer durch binäre Suche O(log n)rechtzeitig gefunden werden.
• Wenn wir nProzessoren haben, kann theoretisch jeder Prozess eine der Eingaben überprüfen und ein Flag setzen, das die Nummer identifiziert (bequem in einem Array). Und im nächsten Schritt kann jeder Prozess jedes Flag überprüfen und schließlich die Nummer ausgeben, die nicht markiert ist. Der gesamte Prozess wird einige O(1)Zeit dauern . Es hat zusätzlichen O(n)Platz- / Speicherbedarf.

Beachten Sie, dass die beiden oben bereitgestellten parallelen Algorithmen möglicherweise zusätzlichen Speicherplatz benötigen, wie im Kommentar erwähnt .