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

Sie wollen vielleicht wissen, ob Sie schon einmal etwas von einer probabilistischen Bloom-Filter die sehr effizient feststellen kann, ob ein Wert nicht Teil einer großen Menge ist (aber nur mit hoher Wahrscheinlichkeit feststellen kann, dass er ein Mitglied der Menge ist).

Answer 2

Ausgehend von der derzeitigen Formulierung in der ursprünglichen Frage ist die einfachste Lösung die folgende:

Ermitteln Sie den Höchstwert in der Datei und addieren Sie dann 1 dazu.

Answer 3

Verwenden Sie eine BitSet . 4 Milliarden ganze Zahlen (bei bis zu 2^32 ganzen Zahlen), gepackt in ein BitSet mit 8 pro Byte, sind 2^32 / 2^3 = 2^29 = ca. 0,5 Gb.

Um ein wenig mehr Details hinzuzufügen - jedes Mal, wenn Sie eine Zahl lesen, setzen Sie das entsprechende Bit im BitSet. Dann machen Sie einen Durchlauf über das BitSet, um die erste Zahl zu finden, die nicht vorhanden ist. Sie könnten dies genauso gut tun, indem Sie wiederholt eine Zufallszahl auswählen und prüfen, ob sie vorhanden ist.

BitSet.nextClearBit(0) sagt Ihnen das erste nicht gesetzte Bit.

Wenn man sich die BitSet-API ansieht, scheint sie nur 0..MAX_INT zu unterstützen, so dass man möglicherweise 2 BitSets braucht - eines für +'ve Zahlen und eines für -'ve Zahlen - aber die Speicheranforderungen ändern sich nicht.

Answer 4

Wenn es keine Größenbeschränkung gibt, ist der schnellste Weg, die Länge der Datei zu nehmen und die Länge der Datei+1 Anzahl zufälliger Ziffern (oder einfach "11111..." s) zu generieren. Vorteil: Sie brauchen die Datei nicht einmal zu lesen und können den Speicherbedarf fast auf Null reduzieren. Nachteil: Sie werden Milliarden von Ziffern drucken.

Wenn jedoch der einzige Faktor die Minimierung der Speichernutzung ist und nichts anderes wichtig ist, wäre dies die optimale Lösung. Sie könnte Ihnen sogar einen Preis für den "schlimmsten Missbrauch der Regeln" einbringen.

Answer 5

Wenn wir davon ausgehen, dass der Zahlenbereich immer 2^n (eine gerade Potenz von 2) ist, dann funktioniert Exklusiv-Oder (wie von einem anderen Poster gezeigt). Warum das so ist, können wir beweisen:

Die Theorie

Bei einem beliebigen 0-basierten Bereich von ganzen Zahlen, der 2^n Elemente, bei denen ein Element fehlt, können Sie das fehlende Element finden, indem Sie einfach die bekannten Werte miteinander xor-ieren, um die fehlende Zahl zu erhalten.

Der Beweis

Betrachten wir n = 2. Für n=2 können wir 4 eindeutige ganze Zahlen darstellen: 0, 1, 2, 3. Sie haben ein Bitmuster von:

• 0 - 00
• 1 - 01
• 2 - 10
• 3 - 11

Wenn wir nun schauen, wird jedes einzelne Bit genau zweimal gesetzt. Wenn eine einzelne Zahl fehlt, ergibt die Exklusiv-Oder-Verknüpfung eine Zahl, die bei der Exklusiv-Oder-Verknüpfung mit der fehlenden Zahl 0 ergibt. Die fehlende Zahl und die resultierende Exklusiv-Oder-Zahl sind also genau gleich. Wenn wir 2 entfernen, ist das Ergebnis von xor 10 (oder 2).

Betrachten wir nun n+1. Nennen wir die Anzahl, wie oft jedes Bit gesetzt ist, in n , x und die Anzahl, wie oft jedes Bit in n+1 y . Der Wert von y wird gleich sein mit y = x * 2 denn es gibt x Elemente mit dem n+1 Bit auf 0 gesetzt, und x Elemente mit dem n+1 Bit auf 1 gesetzt. Und da 2x wird immer ausgeglichen sein, n+1 wird jedes Bit immer eine gerade Anzahl von Malen gesetzt sein.

Deshalb, da n=2 arbeitet, und n+1 funktioniert, funktioniert die xor-Methode für alle Werte von n>=2 .

Der Algorithmus für 0-basierte Bereiche

Das ist ganz einfach. Es verwendet 2*n Bits Speicher, d.h. für jeden Bereich <= 32 funktionieren 2 32-Bit-Ganzzahlen (ohne Berücksichtigung des vom Dateideskriptor verbrauchten Speichers). Und es macht einen einzigen Durchgang durch die Datei.

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

Der Algorithmus für beliebige Basisbereiche

Dieser Algorithmus funktioniert für Bereiche mit einer beliebigen Anfangszahl bis zu einer beliebigen Endzahl, solange der Gesamtbereich gleich 2^n... ist. Im Grunde genommen wird der Bereich so umgestellt, dass das Minimum bei 0 liegt, aber es sind zwei Durchläufe durch die Datei erforderlich (der erste, um das Minimum zu ermitteln, der zweite, um den fehlenden Wert zu berechnen).

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

Arbiträre Bereiche

Wir können diese modifizierte Methode auf eine Menge beliebiger Bereiche anwenden, da alle Bereiche mindestens einmal eine Potenz von 2^n durchlaufen. Dies funktioniert nur, wenn ein einziges Bit fehlt. Bei einer unsortierten Datei sind 2 Durchläufe erforderlich, aber die einzelne fehlende Zahl wird jedes Mal gefunden:

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

Grundsätzlich wird der Bereich um 0 herum neu festgelegt. Dann wird die Anzahl der unsortierten Werte gezählt, die bei der Berechnung des Exklusiv-Oders angehängt werden. Dann wird 1 zur Anzahl der unsortierten Werte hinzugefügt, um den fehlenden Wert zu berücksichtigen (den fehlenden Wert zählen). Dann wird der Wert n immer wieder um 1 erhöht, bis n eine Potenz von 2 ist. Das Ergebnis wird dann wieder auf die ursprüngliche Basis zurückgerechnet. Das war's.

Hier ist der Algorithmus, den ich in PHP getestet habe (mit einem Array statt einer Datei, aber mit demselben Konzept):

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

Wird ein Array mit einem beliebigen Wertebereich (ich habe auch negative Werte getestet) mit einem fehlenden Wert innerhalb dieses Bereichs gefüttert, wird jedes Mal der richtige Wert gefunden.

Eine andere Herangehensweise

Da wir eine externe Sortierung verwenden können, warum nicht einfach auf eine Lücke prüfen? Wenn wir davon ausgehen, dass die Datei vor der Ausführung dieses Algorithmus sortiert ist:

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;