Sie erhalten eine Datei, die alle möglichen Zahlen einer 32-Bit-Architektur enthält. In dieser Datei fehlen 4 Zahlen. Finde die 4 fehlenden Zahlen

Dies ist eine Interviewfrage, die ich einige Male durchlaufen habe, und ich bin mir nicht sicher, wie ich sie lösen soll, da vier Zahlen fehlen. Ich bin mit Algorithmen zum Auffinden einer oder zweier fehlender Zahlen vertraut, sehe jedoch keine Möglichkeit, eine von beiden auf vier zu verallgemeinern.

Egal, ob es sich um ein Interview oder eine konkrete Arbeit handelt, Ihre erste Priorität muss eine funktionierende Lösung sein, die für Sie sinnvoll ist . Das in der Regel bedeutet , sollten Sie die erste Lösung bieten Sie einfach davon ist denken kann und einfach für Sie zu erklären.

Für mich bedeutet das, die Zahlen zu sortieren und nach Lücken zu suchen. Aber ich arbeite an Geschäftssystemen und Web-Apps. Ich spiele nicht mit Stücken und ich möchte nicht, dass mein Team es tut!

Wenn Sie ein Interview für einen Job auf niedrigem Niveau führen, der dem Metall am nächsten kommt, wird "Sortieren" wahrscheinlich mit leeren Blicken beantwortet. Sie möchten, dass Sie bequem über Bits und so weiter nachdenken können. Ihre erste Antwort sollte lauten: "Oh, ich würde eine Bitmap verwenden." (Oder Bit-Array oder Bit gesetzt.)

Und dann, egal wie - selbst wenn Sie eine "falsche" Lösung angeben, wenn Ihr Interviewer (oder Chef!) Darauf drängt , können Sie einige Verbesserungen oder Alternativen vorschlagen, wobei Sie sich auf das spezifische Anliegen des Managers konzentrieren.

• Streng begrenzter RAM? Weniger als 512 MB?
  Sortieren Sie es auf der Festplatte. Sie können beliebig viel RAM verwenden, um sortierte Blöcke zu optimieren und / oder zu puffern.
• Begrenzte Zeit?
  Benutze diesen RAM! Sortieren ist schon O(n*log(n)). (Oder O (n) für eine Ganzzahl-Bucket-Sortierung!)
• Wartbarkeit?
  Was könnte einfacher sein als zu sortieren ?!
• Zeigt keine Kenntnisse über Bit-Flags / -Felder? ( BitSet/ BitMap/ BitArray)
  Nun gut ... gehe voran und benutze a, BitArrayum die "gefundenen Zahlen" zu kennzeichnen. Und dann nach scannen 0.
• Vorhersehbare "Echtzeit" -Komplexität?
  Verwenden Sie die Bitmap-Lösung. Es ist ein einzelner Durchlauf über die Datei und ein weiterer Durchlauf über dasBitArray/BitSet(um die zu finden0). DasO(n)denke ich!

Oder Wasauchimmer.

Gehen Sie auf die Bedenken ein, die Sie tatsächlich haben. Lösen Sie das Problem einfach zuerst und verwenden Sie gegebenenfalls naive Lösungen. Verschwenden Sie nicht die Zeit aller, um Bedenken auszuräumen, die es noch nicht gibt.

Da es sich um eine Datei handelt, gehe ich davon aus, dass Sie mehrere Durchgänge durchführen dürfen. Erstellen Sie zunächst ein Array mit 256 Zählern, durchlaufen Sie die Datei und erhöhen Sie für jede Zahl den Zähler, der als erstes Byte der Zahl indiziert ist. Wenn Sie fertig sind, sollten die meisten Indikatoren 2 ^ 24 sein, aber 1 bis 4 Indikatoren sollten niedrigere Werte haben. Jeder dieser Indizes repräsentiert ein erstes Byte einer der fehlenden Zahlen (wenn es weniger als 4 gibt, liegt das daran, dass mehrere fehlende Zahlen dasselbe erste Byte teilen).

Erstellen Sie für jeden dieser Indizes ein weiteres Array mit 256 Zählern und führen Sie einen zweiten Durchlauf für die Datei durch. Wenn diesmal das erste Byte einer der vorherigen Werte ist, erhöhen Sie einen Zähler in seinem Array basierend auf dem zweiten Byte. Wenn Sie fertig sind, suchen Sie erneut nach den Zählern unter 2 ^ 16, und Sie erhalten das zweite Byte der fehlenden Zahlen, die jeweils mit dem ersten Byte übereinstimmen.

Wiederholen Sie dies für das dritte Byte (beachten Sie, dass Sie maximal 4 Arrays in jedem Durchgang benötigen, obwohl auf jedes Byte bis zu 4 verschiedene Bytes folgen können) und für das vierte Byte, und Sie haben alle fehlenden Zahlen gefunden.

Zeitkomplexität - O(n * log n)
Raumkomplexität - konstant !

Bearbeiten:

Eigentlich habe ich das n=2^32als Parameter angesehen, aber die Anzahl der fehlenden Zahlen k=4ist auch ein Parameter. Angenommen, k<<ndies bedeutet, dass der Raum komplex ist O(k).

Aktualisieren:

Nur zum Spaß (und weil ich gerade versuche Rust zu lernen) habe ich es in Rust implementiert: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f . Ich habe mich für eine Textdarstellung entschieden, da on-one diese mit ~ 2 ^ 32 Zahlen ausführen wird ...

Wenn dies Java wäre, könnten Sie ein BitSet verwenden. Nun, zwei von ihnen, weil sie nicht alle 32-Bit-Zahlen halten können. Skelettcode, vielleicht fehlerhaft:

BitSet bitsetForPositives = new Bitset(2^31);  // obviously not 2^31 but you get the idea
BitSet bitsetForNegatives = new Bitset(2^31);

for (int value: valuesTheyPassInSomehow) {
  if ((value & 0x80000000) == 0)
     bitsetForPositives.set(value );
  else
     bitsetForNegatives.set(value & ~0x80000000);
}

Verwenden Sie dann, um BitSet.nextClearBit()zu finden, wer fehlt.

Anmerkung viel später hinzugefügt:

Beachten Sie, dass es mit diesem Algorithmus ziemlich einfach ist, den zeitaufwändigen Teil parallel auszuführen . Angenommen, die Originaldatei wurde in vier ungefähr gleiche Teile aufgeteilt. Ordnen Sie 4 BitSet-Paare zu (2 GB, noch verwaltbar).

1. Lassen Sie vier Threads gleichzeitig eine Datei in ein eigenes BitSet-Paar verarbeiten.
2. Wenn Sie fertig sind, kehren Sie zu einem einzelnen Thread oder den Bitsets zurück (triviale Zeit) und rufen Sie nextClearBit viermal auf (ebenfalls ziemlich triviale Zeit).

Ich würde erwarten, dass I / O immer noch die Geschwindigkeitsbegrenzungsstufe ist, aber wenn alle Zahlen auf magische Weise im Speicher wären, könnten Sie die Dinge wirklich beschleunigen.

Diese Frage kann mit einem Array von Bits (wahr / falsch) gelöst werden. Dies sollte die effizienteste Struktur sein, um die Antworten für alle Zahlen zu speichern, wobei der Index des Arrays verwendet wird, um festzustellen, ob diese bestimmte Zahl gefunden wurde.

C #

var bArray = new BitArray(Int32.MaxValue);

//Assume the file has 1 number per line
using (StreamReader sr = File.OpenText(fileName))
{
        string s = String.Empty;
        while ((s = sr.ReadLine()) != null)
        {
            var n = int32.Parse(s);
            bArray[n] = true;
        }
}

Durchlaufen Sie dann einfach das Array und für die Werte, die immer noch falsch sind, sind sie nicht in der Datei enthalten.

Sie konnten die Datei in kleinere Teile aufteilen, aber ich konnte meinem 16,0-GB-Laptop unter Windows 7 (64-Bit) ein Array mit maximaler Größe (2147483647) zuweisen.

Selbst wenn ich kein 64-Bit-System verwenden würde, könnte ich kleinere Bit-Arrays zuweisen. Ich würde die Datei vorverarbeiten und eine Reihe kleinerer Dateien mit einem Bereich von [0-64000] [64001-128000] usw. erstellen, die für die verfügbaren Umweltressourcen geeignet wären. Gehen Sie die große Datei durch und schreiben Sie jede Zahl in die entsprechende Set-Datei. Verarbeiten Sie dann jede kleinere Datei. Aufgrund des Vorverarbeitungsschritts würde es etwas länger dauern, aber dies würde Ressourcenbeschränkungen umgehen, wenn es begrenzte Ressourcen gäbe.

Da es sich um eine Interviewfrage handelt, möchte ich dem Interviewer Verständnis für die Einschränkungen vermitteln. Was bedeutet dann "alle möglichen Zahlen"? Ist es wirklich 0 ... 2 <(32-1), wie jeder vermutet? Übliche 32-Bit-Architekturen können mit viel mehr als nur 32-Bit-Zahlen arbeiten. Es ist natürlich nur eine Frage der Repräsentation.

Muss es auf einem 32-Bit-System gelöst werden, oder ist das eher ein Teil der Beschränkung auf Zahlen? Beispielsweise kann ein typisches 32-Bit-System die Datei nicht sofort in den Arbeitsspeicher laden. Ich würde auch erwähnen, dass ein 32-Bit-System aufgrund der Dateigrößenbeschränkung häufig nicht in der Lage ist, eine Datei mit allen Zahlen zu erstellen. Nun, es sei denn, es verfügt über eine clevere Codierung wie "Alle Zahlen außer diesen vier". In diesem Fall ist das Problem trivial gelöst.

Aber wenn Sie die Frage wirklich als "Wenn Sie eine Datei mit allen Zahlen von 0 ... 2 ^ (32-1) bis auf wenige Zahlen verstehen wollen, geben Sie mir eine fehlende" (und das ist ein großes Wenn !), Dann Es gibt viele Möglichkeiten, dies zu lösen.

Trivial, aber nicht machbar: Scannen Sie für jede mögliche Nummer die Datei und prüfen Sie, ob sie dort enthalten ist.

Mit 512 MB RAM und Single Pass Through-Datei: Markieren Sie jede aus der Datei gelesene Nummer (= gesetztes Bit an diesem Index) und übergeben Sie anschließend den RAM einmal und sehen Sie die fehlenden.

Ein Ansatz, der leicht zu merken und in einem Interview zu artikulieren ist, besteht darin, die Tatsache zu verwenden, dass bei Betrachtung aller Zahlen in N Bits jedes Bit in genau der Hälfte dieser Werte und nicht in der anderen Hälfte gesetzt wird .

Wenn Sie alle Werte in der Datei durchlaufen und die Anzahl der Werte am Ende auf 32 setzen, erhalten Sie 32 Werte, die genau (2 ^ 32/2) oder etwas weniger als dieser Wert sind. Die Differenz zwischen dem Maximum (2 ^ 32/2) und der Summe ergibt die Summe der Bits, die an jeder Position der fehlenden Werte gesetzt sind.

Sobald Sie das haben, können Sie alle möglichen Sätze von 4 Werten bestimmen, die diese Summen ergeben könnten. Aus diesem Grund können Sie die Werte in der Datei erneut durchgehen und nach Werten suchen, die Teil dieser Kombinationen sind. Wenn Sie eine finden, werden Kombinationen, die diesen Wert enthalten, als Möglichkeiten ausgeschlossen. Sobald Sie nur noch eine mögliche Kombination haben, müssen Sie antworten.

Wenn Sie beispielsweise ein Nibble verwenden, haben Sie die folgenden Werte:

1010
0110
1111
0111
1101
1001
0100
0101
0001
1011
1100
1110

Die an jeder Position gesetzten Gesamtbits sind:

7867

Subtrahiert man diese von 8 (4 ^ 2/2), so erhält man:

1021

Was bedeutet, dass es diese folgenden möglichen Sätze von 4 Werten gibt:

1000
0000
0011
0010

1010
0001
0010
0000

(Verzeih mir, wenn ich welche verpasst habe, ich mache das nur aus der Sicht)

Wenn wir uns die ursprünglichen Zahlen noch einmal ansehen, finden wir sofort 1010, was bedeutet, dass der erste Satz die Antwort war.

Angenommen, die Datei wird nach zunehmender Anzahl sortiert:

Stellen Sie sicher, dass es keine (2³²-4) Zahlen enthält.
Wenn die Datei nun vollständig wäre (oder wenn die 4 fehlenden Zahlen die letzten 4 waren), würde das Lesen eines Wortes in der Datei an Position N den passenden Wert N zurückgeben.

Verwenden Sie eine Dichotomiesuche an den Positionen [0..2³²-4-1), um nach der ersten nicht erwarteten Zahl X1 zu suchen.
Wenn Sie diese erste fehlende Zahl gefunden haben, wiederholen Sie die Dichtotomie-Suche an den Positionen [X1 .. (2³²-4-1)], um die zweite fehlende Zahl zu finden wenn es keine fehlenden Nummern mehr gibt (da Sie eine fehlende Nummer übergeben haben).
Iterieren Sie ebenfalls für die beiden verbleibenden Nummern. Bei der dritten Iteration sollte das Lesewort an Position N N-2 und bei der vierten N-3 zurückgeben.

Einschränkung: Ich habe das nicht getestet. Aber ich denke es sollte funktionieren. :)

Jetzt im wirklichen Leben stimme ich anderen Antworten zu: Die ersten Fragen würden sich auf die Umwelt beziehen. Haben wir RAM-Verfügbarkeit (wie viel), befindet sich die Datei auf einem Direktzugriffsspeichergerät, handelt es sich um eine einmalige Operation (keine Optimierung erforderlich) oder um eine kritische Operation (jede Zykluszahl)? Haben wir ein externes Sortierdienstprogramm verfügbar? usw.
Dann finden Sie einen für den Kontext akzeptablen Kompromiss. Dies zeigt zumindest, dass Sie mit der Analyse des Problems beginnen, bevor Sie nach einem Algorithmus suchen.

Wie bei allen Standardfragen besteht die Lösung darin, sie vor dem Interview zu googeln.

Diese Frage und Variationen haben eine sehr eindeutige "richtige" Antwort, bei der alle Zahlen durch XOR verknüpft werden. Es soll Ihnen zeigen, dass Sie Indizes in Datenbanken oder Ähnlichem verstehen. Also null Punkte für jedes "könnte funktionieren, aber nicht, was es auf dem Papier sagt", antworte ich sofort.

Auf der positiven Seite gibt es eine endliche Menge dieser Fragen, die Sie nach ein paar Stunden Überarbeitung wie ein Genie aussehen lassen. Denken Sie daran, so zu tun, als würden Sie es in Ihrem Kopf herausarbeiten.

Bearbeiten. Ahh es scheint für 4 gibt es einen anderen Ansatz als XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

Bearbeiten. Downvoters: Dies ist ein veröffentlichtes Lehrbuch O (n) Lösung für das genaue Problem im OP angegeben.