Frage Einfache Interviewfrage wurde schwieriger: geben Sie die Nummern 1..100, finden Sie die fehlende Nummer (n)


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

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

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

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

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

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

Q2: Das stimmt, aber wie würdest du das jetzt tun? ZWEI Nummern fehlen?

Ich hatte diese Variation nie zuvor gesehen / gehört / in Erwägung gezogen, also geriet ich in Panik und konnte die Frage nicht beantworten. Der Interviewer bestand auf meinen Denkprozess zu wissen, so erwähnte ich, dass vielleicht können wir durch einen Vergleich gegen das erwartete Produkt mehr Informationen erhalten, oder vielleicht einen zweiten Durchgang zu tun, nachdem einige Informationen aus dem ersten Durchlauf gesammelt hat, etc, aber ich war wirklich nur schießen im Dunkeln, anstatt tatsächlich einen klaren Weg zur Lösung zu haben.

Der Interviewer versuchte mich zu ermutigen, indem er sagte, dass eine zweite Gleichung in der Tat eine Möglichkeit ist, das Problem zu lösen. An diesem Punkt war ich etwas verärgert (weil ich die Antwort vor der Hand nicht kannte) und fragte, ob dies eine allgemeine (lies: "nützliche") Programmiertechnik sei, oder ob es nur eine Trick- / Gotcha-Antwort ist.

Die Antwort des Interviewers hat mich überrascht: Sie können die Technik verallgemeinern, um 3 fehlende Zahlen zu finden. In der Tat können Sie es verallgemeinern, um zu finden k fehlende Nummern.

Qk: Wenn genau k Zahlen fehlen in der Tasche, wie würdest du es effizient finden?

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

Die Frage ist also einfach:

  • Wie würdest du lösen? Q2?
  • Wie würdest du lösen? Q3?
  • Wie würdest du lösen? Qk?

Erläuterungen

  • Generell gibt es N Zahlen von 1 ..Nnicht nur 1..100.
  • Ich suche nicht nach der offensichtlichen satzbasierten Lösung, z. Verwendung einer Bit gesetztCodieren der Anwesenheit / Abwesenheit jeder Zahl durch den Wert eines bestimmten Bits, daher Verwenden O(N)Bits im zusätzlichen Speicherplatz. Wir können uns keinen zusätzlichen Platz proportional dazu leisten N.
  • Ich suche auch nicht nach dem offensichtlichen Ansatz erster Art. Dies und der Set-basierte Ansatz sind in einem Interview erwähnenswert (sie sind einfach zu implementieren und abhängig von N, kann sehr praktisch sein). Ich suche nach der Heilig-Gral-Lösung (die vielleicht nicht praktikabel zu implementieren ist, aber trotzdem die gewünschten asymptotischen Eigenschaften hat).

Also nochmal, natürlich müssen Sie die Eingabe einlesen O(N), aber Sie können nur eine kleine Menge an Informationen erfassen (definiert in k nicht N), und muss dann die finden k fehlende Nummern irgendwie.


983
2017-08-16 10:26


Ursprung


Antworten:


Hier ist eine Zusammenfassung von Dimitris Andreous Verknüpfung.

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

ein1 + a2 + ... + ak = b1

ein12 + a22 + ... + ak2 = b2

...

ein1k + a2k + ... + akk = bk

Verwenden Newtons Identitäten, wissend bich erlaubt zu berechnen

c1 = a1 + a2 + ... ak

c2 = a1ein2 + a1ein3 + ... + ak-1eink

...

ck = a1ein2 ... eink

Wenn Sie das Polynom erweitern (x-a1) ... (x-ak) die Koeffizienten werden genau c sein1, ..., ck - sehen Viètes Formeln. Da jedes Polynom Faktoren eindeutig (Ring von Polynomen ist ein Euklidische Domäne), das bedeutet aich sind bis zur Permutation eindeutig bestimmt.

Dies beendet den Beweis, dass das Erinnern der Kräfte ausreicht, um die Zahlen wiederherzustellen. Für konstante k ist dies ein guter Ansatz.

Wenn jedoch k variiert, ist der direkte Ansatz der Berechnung c1, ..., ck ist verbietbar teuer, da z.B. ck ist das Produkt aller fehlenden Zahlen, Magnitude n! / (n-k) !. Um dies zu umgehen, führen Sie Berechnungen in Z durchq Feld, wobei q eine Primzahl ist, so dass n <= q <2n - es existiert durch 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 einen nach Berlekamp oder Cantor-Zassenhaus.

Pseudocode auf hoher Ebene für konstante k:

  • Berechne i-te Potenzen gegebener Zahlen
  • Subtrahiere, um Summen von i-ten Potenzen unbekannter Zahlen zu erhalten. Nenne die Summen bich.
  • Verwenden Sie Newtons Identitäten, um Koeffizienten aus b zu berechnenich; nenne sie cich. Grundsätzlich c1 = b1; c2 = (c1b1 - b2) / 2; Genaue Formeln finden Sie in Wikipedia
  • Faktor das Polynom xk-c1xk-1 + ... + ck.
  • Die Wurzeln des Polynoms sind die benötigten Zahlen a1, ..., eink.

Um k zu variieren, finde eine Primzahl n <= q <2n unter Verwendung von z.B. Miller-Rabin, und führen Sie die Schritte mit allen Zahlen Modulo q reduziert.

Wie Heinrich Apfelmus kommentierte, kann man statt einer Primzahl q auch q = 2 verwenden⌈log n⌉ und performen Arithmetik im endlichen Feld.


512
2017-08-16 12:13



Sie werden es finden, indem Sie die paar Seiten von lesen Muthukrishnan - Datenstrom-Algorithmen: Puzzle 1: Suche nach fehlenden Zahlen. Es zeigt genau die Generalisierung, nach der Sie suchen. Wahrscheinlich hat Ihr Interviewer das gelesen und warum hat er diese Fragen gestellt.

Wenn jetzt nur die Leute anfangen würden, die Antworten zu löschen, die durch Muthukrishnans Behandlung subsumiert oder ersetzt wurden, und diesen Text leichter auffindbar machen. :)


Siehe auch sdcvvcs direkt verwandte Antwort, die auch Pseudocode enthält (hurra! keine Notwendigkeit, diese kniffligen mathematischen Formulierungen zu lesen :)) (danke, tolle Arbeit!).


226
2017-08-16 11:26



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

Wir können dann das Problem auf reduzieren

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

Woher x und y Wie weit sind die Summen unter den erwarteten Werten?

Substitution gibt uns:

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

Was wir dann lösen können, um unsere fehlenden Nummern zu ermitteln.


159
2017-08-16 10:37



Wie @j_random_hacker gezeigt hat, ist dies sehr ähnlich Duplikate in O (n) Zeit und O (1) Raum findenund eine Anpassung meiner Antwort funktioniert auch hier.

Angenommen, dass der "Beutel" durch ein 1-basiertes Array repräsentiert wird A[] von der Größe N - kWir können Qk lösen O(N) Zeit und O(k) zusätzlicher Raum.

Zuerst erweitern wir unser Array A[] durch k Elemente, so dass es jetzt von der Größe ist N. Dies ist das O(k) zusätzlicher Raum. Wir führen dann den folgenden Pseudo-Code-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 k zusätzliche Einträge zum selben wie der erste Eintrag im Array (dies ist nur ein bequemer Wert, von dem wir wissen, dass er bereits im Array vorhanden ist - nach diesem Schritt alle Einträge, die im ursprünglichen Array der Größe fehlten N-k fehlen noch im erweiterten Array).

Die zweite Schleife permutiert das erweiterte Array, so dass wenn Element x ist mindestens einmal vorhanden, dann wird einer dieser Einträge an der Position sein A[x].

Beachten Sie, dass obwohl es eine verschachtelte Schleife hat, es trotzdem läuft O(N) Zeit - ein Tausch tritt nur auf, wenn es einen gibt i so dass A[i] != iund jeder Austausch legt mindestens ein Element fest, so dass A[i] == i, wo das vorher nicht stimmte. Dies bedeutet, dass die Gesamtzahl der Swaps (und damit die Gesamtzahl der Ausführungen des while Schleifenkörper) ist höchstens N-1.

Die dritte Schleife druckt diese Indizes des Arrays i die nicht durch den Wert belegt sind i - das bedeutet, dass i muss gefehlt haben.


120
2018-04-22 04:32



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 es funktioniert genauso einfach, aber viele Bälle fehlen.


114
2018-04-12 18:59



Nicht sicher, ob es die effizienteste Lösung ist, aber ich würde alle Einträge durchlaufen und ein Bitset verwenden, um mich daran zu erinnern, welche Zahlen gesetzt sind, und dann nach 0 Bits zu 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.


30
2017-08-16 10:38



Ich habe die Mathematik nicht überprüft, aber ich vermute, dass Computer Σ(n^2) im selben Durchgang wie wir berechnen Σ(n) würde genug Informationen liefern, um zwei fehlende Zahlen zu erhalten, Do Σ(n^3) auch wenn es drei gibt, und so weiter.


29
2017-08-16 10:38



Das Problem mit Lösungen, die auf Zahlensummen basieren, ist, dass sie die Kosten des Speicherns und Arbeitens mit Zahlen mit großen Exponenten nicht berücksichtigen ... in der Praxis würde eine große Zahlenbibliothek verwendet werden, um für sehr große n zu arbeiten . Wir können die Raumnutzung für diese Algorithmen analysieren.

Wir können die Zeit- und Raumkomplexität von sdcvvc und Dimitris Andreous Algorithmen 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)

Verwendeter Gesamtspeicher: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Platz verwendet: Annahme, dass Computer a^j dauert ceil(log_2 j) Zeit, 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)

Gesamtzeit verwendet: \Theta(kn log n)

Wenn diese Zeit und dieser Platz zufriedenstellend sind, können Sie ein einfaches rekursives verwenden Algorithmus. Sei b! I der i-te Eintrag in der Tasche, n die Anzahl der Zahlen davor Entfernungen und k die Anzahl der Entfernungen. 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

Lagerung verwendet: O(k) für die Liste, O(log(n)) für Stapel: O(k + log(n)) Dieser Algorithmus ist intuitiver, hat die gleiche Zeitkomplexität und benötigt weniger Platz.


12
2017-09-02 11:41



Warte eine Minute. Wie die Frage besagt, sind 100 Nummern in der Tasche. Unabhängig davon, wie groß k ist, kann das Problem in konstanter Zeit gelöst werden, da Sie eine Menge verwenden und Zahlen aus der Menge in höchstens 100 - k Iterationen einer Schleife entfernen können. 100 ist konstant. Die Menge der verbleibenden Nummern ist deine Antwort.

Wenn wir die Lösung für die Zahlen von 1 bis N verallgemeinern, ändert sich nichts außer N ist keine Konstante, also sind wir in O (N - k) = O (N) -Zeit. Wenn wir zum Beispiel eine Bitmenge verwenden, setzen wir die Bits in O (N) Zeit auf 1, durchlaufen die Zahlen und setzen die Bits auf 0, während wir gehen (O (Nk) = O (N)) und dann wir habe die Antwort.

Es scheint mir, dass der Interviewer Sie gefragt hat, wie ausdrucken der Inhalt der letzten Menge in O (k) Zeit statt O (N) Zeit. Wenn Sie ein Bit gesetzt haben, müssen Sie natürlich alle N Bits durchlaufen, um zu bestimmen, ob Sie die Zahl drucken sollen oder nicht. Wenn Sie jedoch die Art der Implementierung des Sets ändern, können Sie die Zahlen in k Iterationen ausdrucken. Dies geschieht, indem die Zahlen in ein Objekt gesetzt werden, das sowohl in einem Hash-Satz als auch in einer doppelt verknüpften Liste gespeichert wird. Wenn Sie ein Objekt aus dem Hash-Set entfernen, entfernen Sie es auch aus der Liste. Die Antworten werden in der Liste gelassen, die jetzt die Länge k hat.


10
2017-08-16 11:25



Hier ist eine Lösung, die k Bits zusätzlichen Speicherplatzes verwendet, ohne irgendwelche cleveren Tricks und einfach einfach. Ausführungszeit O (n), Extraraum O (k). Nur um zu beweisen, dass dies gelöst werden kann, ohne die Lösung zuerst 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 >= 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;
}

6
2018-04-07 18:53