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 ⁹ × 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 ³² = 4 * 10 ⁹ różnych liczb całkowitych.

Przypadek 1: mamy 1 GB = 1 * 10 ⁹ * 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 ⁶ * 8 bitów = 80 milionów bitów

Rozwiązanie:

Dla wszystkich możliwych 16-bitowych prefiksów istnieje 2 ¹⁶ liczb całkowitych = 65536, potrzebujemy 2 ¹⁶ * 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.

1. Zbuduj licznik każdego segmentu przez pierwsze przejście przez plik.
2. Zeskanuj wiadra, znajdź pierwszego, który ma mniej niż 65536 trafień.
3. Twórz nowe segmenty, których wysokie 16-bitowe prefiksy znajdują się w kroku 2 do drugiego przejścia pliku
4. 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.}

Zakładając, że „liczba całkowita” oznacza 32 bity : 10 MB miejsca wystarcza, aby policzyć, ile liczb jest w pliku wejściowym z dowolnym 16-bitowym prefiksem, dla wszystkich możliwych 16-bitowych prefiksów w jednym przejściu plik wejściowy. Co najmniej jeden z wiader zostanie trafiony mniej niż 2 ¹⁶ razy. Wykonaj drugie przejście, aby dowiedzieć się, która z możliwych liczb w tym segmencie jest już używana.

Jeśli oznacza to więcej niż 32 bity, ale wciąż o ograniczonym rozmiarze : Wykonaj jak wyżej, ignorując wszystkie liczby wejściowe, które przypadają poza (podpisany lub niepodpisany; twój wybór) zakres 32-bitowy.

Jeśli „liczba całkowita” oznacza matematyczną liczbę całkowitą : przeczytaj raz dane wejściowe i śledź największą długość liczby z najdłuższej liczby, jaką kiedykolwiek widziałeś. Kiedy skończysz, wypisz maksimum plus jeden losową liczbę, która ma jeszcze jedną cyfrę. (Jedną z liczb w pliku może być bignum, które dokładnie reprezentuje więcej niż 10 MB, ale jeśli dane wejściowe to plik, to możesz przynajmniej reprezentować długość wszystkiego, co się w nim mieści).

Algorytmy posiadające informacje statystyczne rozwiązują ten problem przy użyciu mniejszej liczby przejść niż podejścia deterministyczne.

Jeśli dozwolone są bardzo duże liczby całkowite, można wygenerować liczbę, która prawdopodobnie będzie unikalna w czasie O (1). Pseudolosowa 128-bitowa liczba całkowita, taka jak GUID , zderzy się tylko z jedną z czterech istniejących miliardów liczb całkowitych w zestawie w mniej niż jednej na 64 miliardy miliardów przypadków.

Jeśli liczby całkowite są ograniczone do 32 bitów, wówczas można wygenerować liczbę, która prawdopodobnie będzie unikalna w jednym przejściu, używając znacznie mniej niż 10 MB. Szanse na zderzenie pseudolosowej 32-bitowej liczby całkowitej z jedną z 4 miliardów istniejących liczb całkowitych wynoszą około 93% (4e9 / 2 ^ 32). Szanse, że zderzy się 1000 pseudolosowych liczb całkowitych, są mniejsze niż jeden na 12 000 miliardów miliardów (prawdopodobieństwo jednego zderzenia ^ 1000). Więc jeśli program utrzymuje strukturę danych zawierającą 1000 pseudolosowych kandydatów i iteruje znane liczby całkowite, eliminując dopasowania z kandydatów, prawie na pewno znajdzie przynajmniej jedną liczbę całkowitą, której nie ma w pliku.

Szczegółowa dyskusja na ten temat została omówiona w kolumnie Jona Bentleya „Kolumna 1. Cracking the Oyster” Perły programistyczne Addison-Wesley str. 3-10

Bentley omawia kilka podejść, w tym sortowanie zewnętrzne, sortowanie korespondencji seryjnej przy użyciu kilku plików zewnętrznych itp., Ale najlepsza metoda sugerowana przez Bentleya to algorytm jednoprzebiegowy wykorzystujący pola bitowe , które humorystycznie nazywa „Wonder Sort” :) Podchodząc do problemu, 4 miliardy liczby mogą być reprezentowane w:

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

Kod implementujący zestaw bitów jest prosty: (wzięty ze strony rozwiązań )

#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)); }

Algorytm Bentleya wykonuje pojedyncze przejście przez plik, setzaznaczając odpowiedni bit w tablicy, a następnie sprawdza tę tablicę za pomocą testmakra powyżej, aby znaleźć brakującą liczbę.

Jeśli dostępna pamięć jest mniejsza niż 0,466 GB, Bentley sugeruje algorytm k-pass, który dzieli dane wejściowe na zakresy w zależności od dostępnej pamięci. Aby wziąć bardzo prosty przykład, jeśli dostępny był tylko 1 bajt (tj. Pamięć do obsługi 8 liczb), a zakres wynosił od 0 do 31, dzielimy to na zakres od 0 do 7, 8-15, 16-22 i tak dalej i obsługiwać ten zakres w każdym z 32/8 = 4przebiegów.

HTH.

Ponieważ problem nie określa, że ​​musimy znaleźć najmniejszą możliwą liczbę, której nie ma w pliku, moglibyśmy po prostu wygenerować liczbę dłuższą niż sam plik wejściowy. :)

W przypadku wariantu 1 GB pamięci RAM można użyć nieco wektora. Musisz przydzielić 4 miliardy bitów == 500 MB bajtów. Dla każdej liczby odczytywanej z wejścia ustaw odpowiedni bit na „1”. Gdy skończysz, iteruj po bitach, znajdź pierwszy, który wciąż ma „0”. Jego indeks jest odpowiedzią.

Jeśli są to 32-bitowe liczby całkowite (prawdopodobnie z wyboru ~ 4 miliardów liczb blisko 2 ³² ), twoja lista 4 miliardów liczb zajmie najwyżej 93% możliwych liczb całkowitych (4 * 10 ⁹ / (2 ³² ) ). Więc jeśli utworzysz tablicę bitów składającą się z 2 ³² bitów z każdym bitem zainicjowanym na zero (co zajmie 2 ²⁹ bajtów ~ 500 MB pamięci RAM; pamiętaj bajt = 2 ³ bity = 8 bitów), przeczytaj listę liczb całkowitych i dla każdego int ustaw odpowiedni element tablicy bitów od 0 do 1; a następnie przeczytaj swoją tablicę bitów i zwróć pierwszy bit, który wciąż wynosi 0.

W przypadku, gdy masz mniej pamięci RAM (~ 10 MB), to rozwiązanie należy nieco zmodyfikować. 10 MB ~ 83886080 bitów wciąż wystarcza, aby wykonać tablicę bitów dla wszystkich liczb od 0 do 83886079. Abyś mógł przeczytać swoją listę liczb wewnętrznych; i zapisuj tylko liczby z zakresu od 0 do 83886079 w tablicy bitów. Jeśli liczby są losowo rozmieszczone; z ogromnym prawdopodobieństwem (różni się o 100% o około 10 ^-2592069 ) znajdziesz brakującą ^{liczbę całkowitą} ). W rzeczywistości, jeśli wybierzesz tylko liczby od 1 do 2048 (tylko 256 bajtów pamięci RAM), nadal znajdziesz brakującą liczbę w przeważającej części (99,999999999999999999999999999999999999999999999999999999999999999995%).

Ale powiedzmy zamiast mieć około 4 miliardów liczb; miałeś coś w rodzaju 2 ^32-1 liczb i mniej niż 10 MB pamięci RAM; więc każdy mały zakres liczb całkowitych ma jedynie niewielką możliwość nieumieszczania liczby.

Jeśli masz gwarancję, że każda liczba int na liście jest unikalna, możesz zsumować liczby i odjąć sumę z jednym brakiem do pełnej sumy (½) (2 ³² ) (2 ³² - 1) = 9223372034707292160, aby znaleźć brakującą liczbę int . Jednak jeśli int wystąpił dwukrotnie, ta metoda zawiedzie.

Zawsze możesz jednak dzielić i podbijać. Naiwną metodą byłoby odczytanie tablicy i policzenie liczb znajdujących się w pierwszej połowie (od 0 do 2 ³¹ -1) i drugiej połowie (2 ³¹ , 2 ³² ). Następnie wybierz zakres z mniejszą liczbą liczb i powtórz dzieląc ten zakres na pół. (Załóżmy, że w (2 ³¹ , 2 ³² ) było mniej dwóch liczb , to następne wyszukiwanie policzy liczby w zakresie (2 ³¹ , 3 * 2 ³⁰ -1), (3 * 2 ³⁰ , 2 ³² ). powtarzając, dopóki nie znajdziesz zakresu z zerowymi liczbami i nie uzyskasz odpowiedzi. Powinieneś wziąć O (lg N) ~ 32 odczytów przez tablicę.

Ta metoda była nieefektywna. Używamy tylko dwóch liczb całkowitych na każdym kroku (lub około 8 bajtów pamięci RAM z 4 bajtową liczbą całkowitą (32-bitową)). Lepszym sposobem byłoby podzielenie na sqrt (2 ³² ) = 2 ¹⁶ = 65536 przedziałów, każdy z 65536 liczbami w bin. Każdy pojemnik wymaga 4 bajtów do przechowywania swojej liczby, więc potrzebujesz 2 ¹⁸ bajtów = 256 kB. Tak więc bin 0 to (0 do 65535 = 2 ¹⁶ -1), bin 1 to (2 ¹⁶ = 65536 do 2 * 2 ¹⁶ -1 = 131071), bin 2 to (2 * 2 ¹⁶ = 131072 do 3 * 2 ¹⁶ - 1 = 196607). W pythonie masz coś takiego:

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

Przeczytaj listę ~ 4 miliardów liczb całkowitych; i policz ile ints przypada na każdy z 2 ¹⁶ pojemników i znajdź niekompletny_bin, który nie ma wszystkich 65536 liczb. Następnie ponownie przeczytasz listę 4 miliardów liczb całkowitych; ale tym razem zauważ tylko, gdy liczby całkowite są w tym zakresie; przewracając trochę, gdy je znajdziesz.

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break

Dlaczego to takie skomplikowane? Pytasz o liczbę całkowitą, której nie ma w pliku?

Zgodnie z podanymi regułami jedyną rzeczą, którą musisz przechowywać, jest największa liczba napotkana do tej pory w pliku. Po odczytaniu całego pliku zwróć liczbę o 1 większą od tego.

Nie ma ryzyka uderzenia w maksimum lub cokolwiek innego, ponieważ zgodnie z regułami nie ma ograniczeń co do wielkości liczby całkowitej lub liczby zwracanej przez algorytm.

Można to rozwiązać na bardzo małej przestrzeni za pomocą wariantu wyszukiwania binarnego.

1. Zacznij od dozwolonego zakresu liczb, 0do 4294967295.

2. Oblicz punkt środkowy.

3. Zapętlaj plik, licząc, ile liczb było równych, mniejszych lub wyższych od wartości punktu środkowego.

4. Jeśli żadna liczba nie była równa, gotowe. Numer punktu środkowego jest odpowiedzią.

5. W przeciwnym razie wybierz zakres, który miał najmniej liczb, i powtórz od kroku 2 z tym nowym zakresem.

Będzie to wymagało do 32 liniowych skanów przez plik, ale zajmie tylko kilka bajtów pamięci do przechowywania zakresu i zliczeń.

Jest to w zasadzie to samo co rozwiązanie Henninga , z tym wyjątkiem, że używa dwóch pojemników zamiast 16k.

EDYCJA Ok, nie zostało to do końca przemyślane, ponieważ zakłada, że ​​liczby całkowite w pliku są zgodne z pewnym rozkładem statycznym. Najwyraźniej nie muszą, ale nawet wtedy należy spróbować:

Istnieje ≈4,3 miliarda 32-bitowych liczb całkowitych. Nie wiemy, jak są one dystrybuowane w pliku, ale najgorszym przypadkiem jest ten, który ma najwyższą entropię Shannona: równy rozkład. W takim przypadku prawdopodobieństwo wystąpienia jednej liczby całkowitej w pliku jest następujące

((2³²-1) / 2³²) ⁴ ⁰⁰⁰ ⁰⁰⁰ ⁰⁰⁰ ≈ .4

Im niższa entropia Shannona, tym większe prawdopodobieństwo, że dostaje się ono średnio, ale nawet w tym najgorszym przypadku mamy szansę 90% na znalezienie nie powtarzającej się liczby po 5 zgadnięciach z losowymi liczbami całkowitymi. Po prostu twórz takie liczby za pomocą generatora pseudolosowego, przechowuj je na liście. Następnie przeczytaj int po int i porównaj go ze wszystkimi swoimi domysłami. W przypadku dopasowania usuń ten wpis z listy. Po przejrzeniu całego pliku istnieje szansa, że ​​pozostanie więcej niż jeden przypuszczenie. Użyj dowolnego z nich. W rzadkim (10% nawet w najgorszym przypadku) przypadku, w którym nie ma wątpliwości, zdobądź nowy zestaw losowych liczb całkowitych, być może tym razem więcej (10-> 99%).

Zużycie pamięci: kilkadziesiąt bajtów, złożoność: O (n), koszty ogólne: nieuniknione, ponieważ większość czasu zostanie poświęcona na nieunikniony dostęp do dysku twardego, a nie na porównywanie int.

Jeśli brakuje jednej liczby całkowitej z zakresu [0, 2 ^ x - 1], po prostu xor je wszystkie razem. Na przykład:

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(Wiem, że to nie odpowiada na pytanie dokładnie , ale jest to dobra odpowiedź na bardzo podobne pytanie).

Mogą chcieć sprawdzić, czy słyszałeś o probabilistycznym filtrze Blooma, który może bardzo skutecznie określić absolutnie, czy wartość nie jest częścią dużego zbioru, (ale może z dużym prawdopodobieństwem ustalić, że jest członkiem zbioru).

W oparciu o obecne sformułowanie w pierwotnym pytaniu najprostszym rozwiązaniem jest:

Znajdź maksymalną wartość w pliku, a następnie dodaj do niej 1.

Użyj a BitSet. 4 miliardy liczb całkowitych (przy założeniu do 2 ^ 32 liczb całkowitych) spakowanych do BitSet po 8 na bajt to 2 ^ 32/2 ^ 3 = 2 ^ 29 = około 0,5 Gb.

Aby dodać nieco więcej szczegółów - za każdym razem, gdy czytasz cyfrę, ustaw odpowiedni bit w BitSet. Następnie przełóż BitSet, aby znaleźć pierwszy numer, który nie jest obecny. W rzeczywistości możesz to zrobić równie skutecznie, wielokrotnie wybierając losową liczbę i testując, czy jest ona obecna.

Właściwie BitSet.nextClearBit (0) powie ci pierwszy nie ustawiony bit.

Patrząc na BitSet API, wydaje się, że obsługuje tylko 0..MAX_INT, więc możesz potrzebować 2 BitSetów - jeden dla liczb + i jeden dla numerów - ale wymagania dotyczące pamięci się nie zmieniają.

Jeśli nie ma limitu rozmiaru, najszybszym sposobem jest pobranie długości pliku i wygenerowanie długości pliku + 1 liczby losowych cyfr (lub tylko „11111 ...”). Zaleta: nie musisz nawet czytać pliku i możesz zminimalizować zużycie pamięci prawie do zera. Wada: wydrukujesz miliardy cyfr.

Gdyby jednak jedynym czynnikiem było zminimalizowanie zużycia pamięci i nic innego nie jest ważne, byłoby to optymalne rozwiązanie. Może nawet dać ci nagrodę za „najgorsze nadużycie zasad”.

Jeśli założymy, że zakres liczb zawsze będzie wynosił 2 ^ n (równa potęga 2), wówczas wyłączność - lub zadziała (jak pokazano na innym plakacie). O ile to udowodnimy:

Teoria

Biorąc pod uwagę dowolny zakres liczb całkowitych oparty na 0, który ma 2^n brakuje elementów z jednym elementem, możesz znaleźć ten brakujący element, po prostu łącząc znane wartości razem, aby uzyskać brakującą liczbę.

Dowód

Spójrzmy na n = 2. Dla n = 2 możemy przedstawić 4 unikalne liczby całkowite: 0, 1, 2, 3. Mają one następujący wzór:

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

Teraz, jeśli spojrzymy, każdy bit jest ustawiany dokładnie dwa razy. Dlatego, ponieważ jest on ustawiany parzystą liczbę razy, a liczba wyłączna - lub z liczb da 0. 0. Jeśli brakuje jednej liczby, wartość wyłączna - lub da liczbę, która w przypadku wykluczenia z brakującą liczbą spowoduje 0. W związku z tym brakująca liczba i wynikowa liczba rudy wyłącznej są dokładnie takie same. Jeśli usuniemy 2, powstanie xor10 (lub 2).

Teraz spójrzmy na n + 1. Nazwijmy, ile razy każdy bit jest ustawiony n, xi ile razy każdy bit jest ustawiony n+1 y. Wartość ybędzie równa, y = x * 2ponieważ istnieją xelementy z n+1bitem ustawionym na 0, i xelementy z n+1bitem ustawionym na 1. A ponieważ 2xzawsze będzie parzysty, n+1zawsze będzie ustawiony bit na parzystą liczbę razy.

Dlatego, ponieważ n=2działa i n+1działa, metoda xor będzie działać dla wszystkich wartości n>=2.

Algorytm dla zakresów opartych na 0

To jest dość proste. Wykorzystuje 2 * n bitów pamięci, więc dla dowolnego zakresu <= 32, będą działać 2 32-bitowe liczby całkowite (ignorując pamięć zajętą ​​przez deskryptor pliku). I to robi pojedyncze przejście pliku.

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

Algorytm dla zakresów opartych na arbitrażu

Ten algorytm będzie działał dla zakresów od dowolnej liczby początkowej do dowolnej liczby końcowej, pod warunkiem, że całkowity zakres jest równy 2 ^ n ... Zasadniczo ponownie opiera zakres, aby mieć minimum na 0. Ale wymaga 2 przebiegów przez plik (pierwszy pobiera minimum, drugi oblicza brakującą liczbę całkowitą).

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;

Zakresy arbitralne

Możemy zastosować tę zmodyfikowaną metodę do zbioru dowolnych zakresów, ponieważ wszystkie zakresy przekroczą potęgę 2 ^ n przynajmniej raz. Działa to tylko wtedy, gdy brakuje jednego bitu. Zajmuje 2 przebiegi nieposortowanego pliku, ale za każdym razem znajdzie brakujący numer:

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;

Zasadniczo ponownie opiera zakres około 0. Następnie zlicza liczbę nieposortowanych wartości, które mają zostać dołączone, obliczając wartość wyłączności lub. Następnie dodaje 1 do liczby nieposortowanych wartości, aby zająć się brakującą wartością (policzyć tę brakującą). Następnie trzymaj xoring wartość n, zwiększaną o 1 za każdym razem, aż n będzie potęgą 2. Wynik jest następnie ponownie oparty na pierwotnej podstawie. Gotowy.

Oto algorytm, który przetestowałem w PHP (używając tablicy zamiast pliku, ale tej samej koncepcji):

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;
}

Podawana w tablicy z dowolnym zakresem wartości (testowałem łącznie z negatywami) z jedną z tego brakującego zakresu, za każdym razem znajdowała prawidłową wartość.

Inne podejście

Ponieważ możemy korzystać z zewnętrznego sortowania, dlaczego nie po prostu sprawdzić lukę? Jeśli założymy, że plik jest sortowany przed uruchomieniem tego algorytmu:

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;

Podchwytliwe pytanie, chyba że zostało źle podane. Wystarczy raz przeczytać plik, aby uzyskać maksymalną liczbę całkowitą ni wrócić n+1.

Oczywiście na wszelki wypadek potrzebujesz planu tworzenia kopii zapasowych n+1 przepełnienia liczby całkowitej.

Sprawdź rozmiar pliku wejściowego, a następnie wypisz dowolną liczbę, która jest zbyt duża, aby mogła być reprezentowana przez plik o tym rozmiarze. To może wydawać się tanią sztuczką, ale jest kreatywnym rozwiązaniem problemu z wywiadem, starannie omija problem z pamięcią i technicznie jest O (n).

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

Powinien wypisać 10 ^bitcount - 1 , która zawsze będzie większa niż 2 ^bitcount . Technicznie liczba, którą musisz pokonać, to 2 ^bity - (4 * 10 ⁹ - 1) , ponieważ wiesz, że w pliku są (4 miliardy - 1) inne liczby całkowite, a nawet przy doskonałej kompresji zajmą co najmniej po jednym kawałku.

• Najprostszym podejściem jest znalezienie minimalnej liczby w pliku i zwrócenie 1 mniejszej. Wykorzystuje to pamięć O (1) i czas O (n) dla pliku o liczbie n. Jednak nie powiedzie się, jeśli zakres liczb jest ograniczony, co może sprawić, że min-1 nie będzie liczbą.

• Wspomniano już o prostej i bezpośredniej metodzie użycia mapy bitowej. Ta metoda wykorzystuje O (n) czas i pamięć.

• Wspomniano także o metodzie 2-przebiegowej z liczeniem 2 ^ 16. Odczytuje 2 * n liczb całkowitych, więc używa czasu O (n) i pamięci O (1), ale nie może obsługiwać zestawów danych zawierających więcej niż 2 ^ 16 liczb. Można go jednak łatwo rozszerzyć na (np.) 2 ^ 60 64-bitowych liczb całkowitych, uruchamiając 4 przebiegi zamiast 2, i łatwo przystosować do korzystania z małej pamięci, używając tylko tyle przedziałów, ile mieści się w pamięci i odpowiednio zwiększając liczbę przebiegów w który czas wykonania przypadku nie jest już O (n), ale zamiast tego O (n * log n).

• Metoda XOR'owania wszystkich liczb razem, wspomniana do tej pory przez rfrankel i w końcu przez ircmaxell, odpowiada na pytanie zadane w przepełnieniu stosu # 35185 , jak wskazała ltn100. Wykorzystuje pamięć O (1) i czas działania O (n). Jeśli na razie przyjmiemy 32-bitowe liczby całkowite, XOR ma 7% prawdopodobieństwo wygenerowania wyraźnej liczby. Uzasadnienie: podano ~ 4G odrębne liczby XOR razem i ok. 300 M poza plikiem, liczba ustawionych bitów w każdej pozycji bitowej ma równe szanse bycia nieparzystym lub parzystym. Zatem 2 ^ 32 liczb ma równe prawdopodobieństwo pojawienia się jako wynik XOR, z czego 93% jest już zapisanych. Zauważ, że jeśli wszystkie liczby w pliku nie są różne, prawdopodobieństwo sukcesu metody XOR wzrasta.

Z jakiegoś powodu, gdy tylko przeczytałem ten problem, pomyślałem o diagonalizacji. Zakładam, że dowolnie duże liczby całkowite.

Przeczytaj pierwszy numer. Lewy pad z zerowymi bitami, aż będziesz miał 4 miliardy bitów. Jeśli pierwszy (wysoki) bit jest równy 0, wyjście 1; w przeciwnym razie wyjście 0. (Nie musisz tak naprawdę wstawiać lewej strony: po prostu wyprowadzasz 1, jeśli liczba nie jest wystarczająca.) Zrób to samo z drugą liczbą, z wyjątkiem tego, że używasz jej drugiego bitu. Kontynuuj przeglądanie pliku w ten sposób. Będziesz wysyłać 4 miliardy bitów po jednym bicie, a liczba ta nie będzie taka sama jak w pliku. Dowód: były takie same jak n-ta liczba, wtedy zgodziliby się co do n-tego bitu, ale z założenia nie.

Możesz użyć flag bitowych, aby zaznaczyć, czy liczba całkowita jest obecna, czy nie.

Po przejściu całego pliku, przeskanuj każdy bit, aby ustalić, czy numer istnieje, czy nie.

Zakładając, że każda liczba całkowita jest 32-bitowa, dogodnie zmieści się w 1 GB pamięci RAM, jeśli zostanie wykonane oznaczanie bitów.

Usuń białe znaki i znaki nienumeryczne z pliku i dołącz 1. Twój plik zawiera teraz pojedynczy numer niewymieniony w oryginalnym pliku.

Od Reddit przez Carbonetc.

Tylko dla kompletności, oto kolejne bardzo proste rozwiązanie, które najprawdopodobniej potrwa bardzo długo, ale zużywa bardzo mało pamięci.

Niech wszystkie możliwe liczby całkowite będą z zakresu od int_mindo int_maxoraz bool isNotInFile(integer)funkcja, która zwraca wartość true, jeśli plik nie zawiera określonej liczby całkowitej, a fałsz inny (przez porównanie tej liczby całkowitej z każdą liczbą całkowitą w pliku)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

Dla ograniczenia pamięci 10 MB:

1. Konwertuj liczbę na jej reprezentację binarną.
2. Utwórz drzewo binarne, gdzie lewy = 0, a prawy = 1.
3. Wstaw każdą liczbę do drzewa, używając jej reprezentacji binarnej.
4. Jeśli numer został już wstawiony, liście zostaną już utworzone.

Po zakończeniu wybierz ścieżkę, która nie została wcześniej utworzona, aby utworzyć żądany numer.

4 miliardy liczb = 2 ^ 32, co oznacza, że ​​10 MB może być niewystarczające.

EDYTOWAĆ

Optymalizacja jest możliwa, jeśli utworzono dwa końce liści i mają one wspólnego elementu nadrzędnego, wówczas można je usunąć, a element nadrzędny oflagować jako rozwiązanie. To odcina gałęzie i zmniejsza zapotrzebowanie na pamięć.

EDYCJA II

Nie ma też potrzeby budowania drzewa całkowicie. Musisz budować głębokie gałęzie tylko wtedy, gdy liczby są podobne. Jeśli wycinamy również gałęzie, to rozwiązanie może faktycznie działać.

Odpowiem na wersję 1 GB:

W pytaniu nie ma wystarczających informacji, dlatego najpierw przedstawię pewne założenia:

Liczba całkowita wynosi 32 bity z zakresu -2 147 483 648 do 2 147 483 647.

Pseudo kod:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}

Tak długo, jak robimy twórcze odpowiedzi, oto kolejna.

Użyj zewnętrznego programu do sortowania, aby posortować plik wejściowy numerycznie. Będzie to działać dla dowolnej ilości pamięci, którą możesz mieć (w razie potrzeby wykorzysta miejsce do przechowywania plików). Przeczytaj posortowany plik i wypisz pierwszą brakującą liczbę.

Eliminacja bitów

Jednym ze sposobów jest wyeliminowanie bitów, jednak może to nie dać rezultatu (istnieje szansa, że ​​tak się nie stanie). Psuedocode:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

Liczy się bit

Śledź liczbę bitów; i użyj bitów z najmniejszą ilością do wygenerowania wartości. Ponownie nie ma to gwarancji wygenerowania prawidłowej wartości.

Logika zasięgu

Śledź listę uporządkowanych zakresów (uporządkowanych według początku). Zakres jest określony przez strukturę:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

Przejrzyj każdą wartość w pliku i spróbuj usunąć ją z bieżącego zakresu. Ta metoda nie ma gwarancji pamięci, ale powinna działać całkiem dobrze.

2 ^{128 * 10 18} + 1 (czyli (2 ⁸ ) ^{16 * 10 18} + 1) - czy nie może to być odpowiedź uniwersalna na dziś? Jest to liczba, której nie można zapisać w pliku 16 EB, czyli maksymalny rozmiar pliku w dowolnym bieżącym systemie plików.

Myślę, że jest to rozwiązany problem (patrz wyżej), ale jest ciekawy przypadek uboczny, o którym należy pamiętać, ponieważ można go zapytać:

Jeśli istnieje dokładnie 4 294 967 295 (2 ^ 32 - 1) 32-bitowych liczb całkowitych bez powtórzeń, a zatem brakuje tylko jednego, istnieje proste rozwiązanie.

Rozpocznij sumę całkowitą od zera, a dla każdej liczby całkowitej w pliku dodaj tę liczbę całkowitą z 32-bitowym przepełnieniem (efektywnie, runningTotal = (runningTotal + nextInteger)% 4294967296). Po zakończeniu dodaj 4294967296/2 do bieżącej sumy, ponownie z 32-bitowym przepełnieniem. Odejmij to od 4294967296, a wynikiem będzie brakująca liczba całkowita.

Problem „tylko jednej brakującej liczby całkowitej” można rozwiązać tylko jednym uruchomieniem i tylko 64 bitami pamięci RAM przeznaczonymi na dane (32 dla łącznej liczby operacji, 32 do odczytu w następnej liczbie całkowitej).

Następstwo: bardziej ogólna specyfikacja jest niezwykle łatwa do dopasowania, jeśli nie martwi nas liczba bitów, jaką musi zawierać wynik liczby całkowitej. Po prostu generujemy na tyle dużą liczbę całkowitą, że nie może być zawarta w podanym pliku. Ponownie zajmuje to absolutnie minimalną pamięć RAM. Zobacz pseudokod.

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}

Jak powiedział Ryan w zasadzie, posortuj plik, a następnie przejrzyj liczby całkowite, a gdy pominiesz wartość, masz ją :)

EDYCJA u downvoters: OP wspomniał, że plik może być posortowany, więc jest to poprawna metoda.

Jeśli nie przyjmujesz ograniczenia 32-bitowego, po prostu zwróć losowo wygenerowaną liczbę 64-bitową (lub 128-bitową, jeśli jesteś pesymistą). Prawdopodobieństwo kolizji wynosi 1 in 2^64/(4*10^9) = 4611686018.4(około 1 na 4 miliardy). Przez większość czasu miałbyś rację!

(Żartuję ... w pewnym sensie.)