Erzeugen einer ganzen Zahl, die nicht unter den vier Milliarden gegebenen Einsen ist

Question

Ich habe diese Frage im Vorstellungsgespräch gestellt bekommen:

Geben Sie einen Algorithmus für eine Eingabedatei mit vier Milliarden ganzen Zahlen an, um eine ganze Zahl zu erzeugen, die nicht in der Datei enthalten ist. Angenommen, Sie haben 1 GB Speicher. Erläutern Sie anschließend, was Sie tun würden, wenn Sie nur 10 MB Speicherplatz hätten.

Meine Analyse:

Die Größe der Datei beträgt 4×10 9 ×4 Bytes = 16 GB.

Wir können eine externe Sortierung vornehmen und kennen so den Bereich der ganzen Zahlen.

Meine Frage ist, was ist der beste Weg, um die fehlende ganze Zahl in der sortierten große ganze Zahl Sätze zu erkennen?

Mein Verständnis (nachdem ich alle Antworten gelesen habe):

Angenommen, es handelt sich um 32-Bit-Ganzzahlen, dann gibt es 2 32 \= 4*10 9 verschiedene ganze Zahlen.

Fall 1: wir haben 1 GB = 1 * 10 9 * 8 Bits = 8 Milliarden Bits Speicher.

Lösung:

Wenn wir ein Bit verwenden, das eine eindeutige ganze Zahl repräsentiert, reicht das aus und wir brauchen keine Sortierung.

Umsetzung:

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

Fall 2: 10 MB Speicher = 10 * 10 6 * 8 Bits = 80 Millionen Bits

Lösung:

Für alle möglichen 16-Bit-Präfixe gibt es 2 16 Anzahl von Ganzzahlen = 65536, wir brauchen 2 16 * 4 * 8 = 2 Millionen Bits. Wir müssen 65536 Buckets bilden. Für jeden Bucket benötigen wir 4 Bytes, die alle Möglichkeiten enthalten, da im schlimmsten Fall alle 4 Milliarden ganzen Zahlen zum selben Bucket gehören.

1. Erstellen Sie den Zähler für jeden Eimer beim ersten Durchlauf durch die Datei.
2. Scanne die Eimer und finde den ersten, der weniger als 65536 Treffer hat.
3. Erstellen Sie neue Buckets, deren hohe 16-Bit-Präfixe wir in Schritt 2 gefunden haben durch zweiten Durchlauf der Datei
4. Scannen Sie die in Schritt 3 erstellten Eimer und suchen Sie den ersten Eimer, der nicht einen Treffer hat.

Der Code ist dem obigen sehr ähnlich.

Schlussfolgerung: Wir verringern den Speicherplatz durch Erhöhung des Dateidurchlaufs.

---

Eine Klarstellung für diejenigen, die zu spät kommen: Die Frage, so wie sie gestellt wurde, besagt nicht, dass es genau eine ganze Zahl gibt, die nicht in der Datei enthalten ist - zumindest interpretieren die meisten Leute sie nicht so. Viele Kommentare im Kommentar-Thread sind über diese Variante der Aufgabe. Leider ist die Bemerkung, dass eingeführt wurde später von seinem Verfasser gelöscht, so dass es jetzt so aussieht, als hätten die verwaisten Antworten darauf einfach alles missverstanden. Das ist sehr verwirrend, tut mir leid.

Answer 1

Unter der Annahme, dass "Ganzzahl" 32 Bits bedeutet : 10 MB Speicherplatz sind mehr als genug, um zu zählen, wie viele Zahlen in der Eingabedatei mit einem bestimmten 16-Bit-Präfix enthalten sind, und zwar für alle möglichen 16-Bit-Präfixe in einem Durchgang durch die Eingabedatei. Mindestens einer der Eimer wird weniger als 2 Treffer haben. 16 Zeiten. Führen Sie einen zweiten Durchlauf durch, um herauszufinden, welche der möglichen Zahlen in diesem Bereich bereits verwendet werden.

Wenn es sich um mehr als 32 Bit handelt, aber immer noch eine begrenzte Größe hat : Wie oben, wobei alle Eingabezahlen ignoriert werden, die außerhalb des 32-Bit-Bereichs (mit oder ohne Vorzeichen; Sie haben die Wahl) liegen.

Wenn "Ganzzahl" eine mathematische Ganzzahl bedeutet : Lesen Sie die Eingabe einmal durch und notieren Sie sich die größte Zahl Länge der längsten Zahl, die Sie je gesehen haben. Wenn Sie fertig sind, geben Sie das Maximum plus eins eine Zufallszahl, die eine Ziffer mehr hat. (Eine der Zahlen in der Datei kann ein Bignum sein, dessen exakte Darstellung mehr als 10 MB erfordert, aber wenn die Eingabe eine Datei ist, können Sie zumindest die Länge von allem, was hineinpasst).

Answer 2

Statistisch informierte Algorithmen lösen dieses Problem mit weniger Durchläufen als deterministische Ansätze.

Wenn sehr große ganze Zahlen erlaubt sind dann kann man in O(1)-Zeit eine Zahl erzeugen, die wahrscheinlich eindeutig ist. Eine pseudozufällige 128-Bit-Ganzzahl wie eine GUID kollidiert nur in weniger als einer von 64 Milliarden Milliarden Milliarden Milliarden Fällen mit einer der vorhandenen vier Milliarden ganzen Zahlen in der Menge.

Wenn Ganzzahlen auf 32 Bit begrenzt sind dann kann man in einem einzigen Durchgang eine Zahl generieren, die wahrscheinlich einmalig ist und viel weniger als 10 MB benötigt. Die Wahrscheinlichkeit, dass eine pseudozufällige 32-Bit-Ganzzahl mit einer der 4 Milliarden existierenden Ganzzahlen kollidiert, beträgt etwa 93 % (4e9 / 2^32). Die Wahrscheinlichkeit, dass 1000 pseudozufällige Ganzzahlen miteinander kollidieren, ist kleiner als eins zu 12.000 Milliarden Milliarden Milliarden Milliarden (odds-of-one-collision ^ 1000). Wenn also ein Programm eine Datenstruktur mit 1000 pseudozufälligen Kandidaten unterhält und die bekannten ganzen Zahlen durchläuft und dabei Übereinstimmungen aus den Kandidaten eliminiert, ist es so gut wie sicher, mindestens eine ganze Zahl zu finden, die nicht in der Datei enthalten ist.

Answer 3

Eine ausführliche Erörterung dieses Problems findet sich in Jon Bentley "Säule 1. Die Auster knacken" Programmier-Perlen Addison-Wesley S. 3-10

Bentley erörtert mehrere Ansätze, darunter externe Sortierung, Merge-Sortierung unter Verwendung mehrerer externer Dateien usw. Die beste Methode, die Bentley vorschlägt, ist jedoch ein Algorithmus in einem einzigen Durchgang unter Verwendung von Bit-Felder die er humorvoll "Wonder Sort" nennt :) Um zum Problem zu kommen: 4 Milliarden Zahlen können in :

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

Der Code zur Implementierung des Bitsets ist einfach: (entnommen aus Lösungsseite )

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

Bentleys Algorithmus führt einen einzigen Durchlauf durch die Datei durch, set das entsprechende Bit im Array und prüft dann dieses Array mit test Makro, um die fehlende Zahl zu finden.

Wenn der verfügbare Speicher weniger als 0,466 GB beträgt, schlägt Bentley einen k-pass-Algorithmus vor, der die Eingabe je nach verfügbarem Speicher in Bereiche unterteilt. Ein sehr einfaches Beispiel: Wenn nur 1 Byte (d.h. Speicher für 8 Zahlen) zur Verfügung steht und der Bereich von 0 bis 31 reicht, unterteilen wir diesen in die Bereiche 0 bis 7, 8-15, 16-22 usw. und verarbeiten diesen Bereich in jedem der folgenden Bereiche 32/8 = 4 Pässe.

HTH.

Answer 4

Da die Aufgabe nicht besagt, dass wir die kleinstmögliche Zahl finden müssen, die nicht in der Datei enthalten ist, könnten wir einfach eine Zahl generieren, die länger ist als die Eingabedatei selbst :)

Answer 5

Für die Variante mit 1 GB RAM können Sie einen Bitvektor verwenden. Sie müssen 4 Milliarden Bits == 500 MB Byte Array zuweisen. Für jede Zahl, die Sie von der Eingabe lesen, setzen Sie das entsprechende Bit auf '1'. Wenn Sie das getan haben, iterieren Sie über die Bits und finden Sie das erste, das noch '0' ist. Sein Index ist die Antwort.