Otrzymałem pytanie do tego wywiadu:
Biorąc pod uwagę plik wejściowy z czterema miliardami liczb całkowitych, zapewnij algorytm do generowania liczby całkowitej, która nie jest zawarta w pliku. Załóżmy, że masz 1 GB pamięci. Kontynuuj, co byś zrobił, gdybyś miał tylko 10 MB pamięci.
Moja analiza:
Rozmiar pliku to 4 × 10 9 × 4 bajtów = 16 GB.
Możemy dokonać zewnętrznego sortowania, co pozwoli nam poznać zakres liczb całkowitych.
Moje pytanie brzmi: jaki jest najlepszy sposób na wykrycie brakującej liczby całkowitej w posortowanych dużych liczbach całkowitych?
Moje zrozumienie (po przeczytaniu wszystkich odpowiedzi):
Zakładając, że mówimy o 32-bitowych liczbach całkowitych, istnieją 2 32 = 4 * 10 9 różnych liczb całkowitych.
Przypadek 1: mamy 1 GB = 1 * 10 9 * 8 bitów = 8 miliardów bitów pamięci.
Rozwiązanie:
Jeśli użyjemy jednego bitu reprezentującego jedną odrębną liczbę całkowitą, to wystarczy. nie potrzebujemy sortować.
Realizacja:
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);
}
}
}
Przypadek 2: 10 MB pamięci = 10 * 10 6 * 8 bitów = 80 milionów bitów
Rozwiązanie:
Dla wszystkich możliwych 16-bitowych prefiksów istnieje 2 16 liczb całkowitych = 65536, potrzebujemy 2 16 * 4 * 8 = 2 miliony bitów. Potrzebujemy zbudować 65536 wiader. Dla każdego segmentu potrzebujemy 4 bajtów z wszystkimi możliwościami, ponieważ najgorszym przypadkiem jest to, że wszystkie 4 miliardy liczb całkowitych należą do tego samego segmentu.
- Zbuduj licznik każdego segmentu przez pierwsze przejście przez plik.
- Zeskanuj wiadra, znajdź pierwszego, który ma mniej niż 65536 trafień.
- Twórz nowe segmenty, których wysokie 16-bitowe prefiksy znajdują się w kroku 2 do drugiego przejścia pliku
- Zeskanuj wiadra zbudowane w kroku 3, znajdź pierwsze wiadro, które nie ma trafienia.
Kod jest bardzo podobny do powyższego.
Wniosek: Zmniejszamy pamięć poprzez zwiększenie przepustowości plików.
Wyjaśnienie dla osób spóźniających się: Pytanie, jak zadano, nie mówi, że istnieje dokładnie jedna liczba całkowita, która nie jest zawarta w pliku - przynajmniej tak nie interpretuje większość ludzi. Wiele komentarzy W komentarzu wątku są o tej odmianie zadania, choć. Niestety komentarz, który wprowadził go do wątku komentarza, został później usunięty przez autora, więc teraz wygląda na to, że osierocone odpowiedzi po prostu źle wszystko zrozumiały. Przepraszam, to bardzo mylące.
int getMissingNumber(File inputFile) { return 4; }
( odniesienie )