Saya telah diberikan pertanyaan wawancara ini:

Diberikan file input dengan empat miliar bilangan bulat, berikan algoritma untuk menghasilkan bilangan bulat yang tidak terkandung dalam file. Asumsikan Anda memiliki memori 1 GB. Tindak lanjuti apa yang akan Anda lakukan jika Anda hanya memiliki 10 MB memori.

Analisis saya:

Ukuran file adalah 4 × 10 ⁹ × 4 byte = 16 GB.

Kita dapat melakukan penyortiran eksternal, sehingga memberi tahu kita kisaran bilangan bulat.

Pertanyaan saya adalah apa cara terbaik untuk mendeteksi bilangan bulat yang hilang dalam rangkaian bilangan bulat besar yang diurutkan?

Pemahaman saya (setelah membaca semua jawaban):

Dengan asumsi kita berbicara tentang bilangan bulat 32-bit, ada 2 ³² = 4 * 10 ⁹ bilangan bulat yang berbeda.

Kasus 1: kami memiliki 1 GB = 1 * 10 ⁹ * 8 bit = 8 miliar bit memori.

Larutan:

Jika kita menggunakan satu bit yang mewakili satu integer yang berbeda, itu sudah cukup. kita tidak perlu menyortir.

Penerapan:

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

Kasus 2: 10 MB memori = 10 * 10 ⁶ * 8 bit = 80 juta bit

Larutan:

Untuk semua kemungkinan awalan 16-bit, ada 2 ¹⁶ jumlah bilangan bulat = 65536, kita membutuhkan 2 ¹⁶ * 4 * 8 = 2 juta bit. Kita perlu membangun 65536 ember. Untuk setiap bucket, kita membutuhkan 4 byte yang menyimpan semua kemungkinan karena kasus terburuk adalah semua 4 miliar bilangan bulat milik bucket yang sama.

1. Buat konter setiap bucket melalui pass pertama melalui file.
2. Pindai ember, temukan yang pertama yang memiliki kurang dari 65536 hit.
3. Bangun bucket baru dengan awalan 16-bit yang tinggi, kami temukan di langkah 2 hingga pass kedua file
4. Pindai ember yang ada di langkah 3, temukan ember pertama yang tidak memiliki hit.

Kode ini sangat mirip dengan yang di atas.

Kesimpulan: Kami mengurangi memori melalui peningkatan pass file.

^{Klarifikasi untuk mereka yang datang terlambat: Pertanyaan, seperti yang ditanyakan, tidak mengatakan bahwa ada tepat satu bilangan bulat yang tidak terdapat dalam file — setidaknya itu bukan cara kebanyakan orang mengartikannya. Banyak komentar di thread komentar yang tentang itu variasi tugas, meskipun. Sayangnya komentar yang memperkenalkannya ke utas komentar kemudian dihapus oleh penulisnya, jadi sekarang sepertinya balasan yatim untuk itu hanya salah mengerti segalanya. Sangat membingungkan, maaf.}

Dengan asumsi bahwa "integer" berarti 32 bit : 10 MB ruang lebih dari cukup bagi Anda untuk menghitung berapa banyak angka yang ada dalam file input dengan awalan 16-bit yang diberikan, untuk semua awalan 16-bit yang mungkin dalam satu melewati masukan file. Setidaknya satu dari ember akan terkena kurang dari 2 ¹⁶ kali. Lakukan operan kedua untuk menemukan nomor mana yang mungkin dalam ember yang sudah digunakan.

Jika itu berarti lebih dari 32 bit, tetapi masih berukuran terbatas : Lakukan seperti di atas, abaikan semua nomor input yang berada di luar kisaran 32-bit (yang ditandatangani atau tidak ditandatangani; pilihan Anda).

Jika "integer" berarti integer matematis : Baca input sekali dan pantau panjang bilangan terbesar dari bilangan terpanjang yang pernah Anda lihat. Setelah selesai, hasilkan maksimum ditambah satu angka acak yang memiliki satu digit lagi. (Salah satu angka dalam file mungkin bignum yang membutuhkan lebih dari 10 MB untuk mewakili secara tepat, tetapi jika inputnya adalah file, maka Anda setidaknya dapat mewakili panjang apa pun yang cocok di dalamnya).

Algoritma yang diinformasikan secara statistik memecahkan masalah ini menggunakan lebih sedikit operan daripada pendekatan deterministik.

Jika bilangan bulat yang sangat besar diizinkan maka seseorang dapat menghasilkan angka yang cenderung unik dalam waktu O (1). Bilangan bulat 128-bit pseudo-acak seperti GUID hanya akan bertabrakan dengan salah satu dari empat miliar bilangan bulat dalam set dalam waktu kurang dari satu dari setiap 64 miliar miliar miliar kasus.

Jika bilangan bulat dibatasi hingga 32 bit, maka seseorang dapat menghasilkan angka yang cenderung unik dalam satu kali lintasan menggunakan jauh lebih sedikit dari 10 MB. Kemungkinan bahwa integer 32-bit semu akan bertabrakan dengan salah satu dari 4 miliar bilangan bulat yang ada adalah sekitar 93% (4e9 / 2 ^ 32). Peluang bahwa 1000 bilangan bulat pseudo-acak semua akan bertabrakan kurang dari satu dalam 12.000 miliar miliar miliar (odds-of-one-collision ^ 1000). Jadi, jika suatu program mempertahankan struktur data yang berisi 1000 kandidat pseudo-acak dan iterasi melalui bilangan bulat yang diketahui, menghilangkan kecocokan dari para kandidat, semuanya pasti akan menemukan setidaknya satu bilangan bulat yang tidak ada dalam file.

Diskusi terperinci tentang masalah ini telah dibahas dalam Jon Bentley "Kolom 1. Pemecahan Kerang" Programming Pearls Addison-Wesley hal.3-10

Bentley membahas beberapa pendekatan, termasuk pengurutan eksternal, Gabung Sortir menggunakan beberapa file eksternal, dll., Namun metode terbaik yang disarankan Bentley adalah algoritma lintasan tunggal menggunakan bidang bit , yang dengan lucu ia sebut "Wonder Sort" :) Datang ke masalah, 4 miliar angka dapat direpresentasikan dalam:

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

Kode untuk mengimplementasikan bitset itu sederhana: (diambil dari halaman solusi )

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

Algoritma Bentley membuat satu melewati file, setting bit yang sesuai dalam array dan kemudian memeriksa array ini menggunakan testmakro di atas untuk menemukan nomor yang hilang.

Jika memori yang tersedia kurang dari 0,466 GB, Bentley menyarankan algoritma k-pass, yang membagi input menjadi rentang tergantung pada memori yang tersedia. Untuk mengambil contoh yang sangat sederhana, jika hanya 1 byte (yaitu memori untuk menangani 8 angka) tersedia dan rentangnya dari 0 hingga 31, kami membaginya dalam rentang 0 hingga 7, 8-15, 16-22 dan seterusnya. dan menangani kisaran ini di setiap 32/8 = 4lintasan.

HTH.

Karena masalahnya tidak menentukan bahwa kita harus menemukan angka sekecil mungkin yang tidak ada dalam file kita hanya bisa menghasilkan angka yang lebih panjang daripada file input itu sendiri. :)

Untuk varian RAM 1 GB Anda dapat menggunakan vektor sedikit. Anda perlu mengalokasikan 4 milyar bit == 500 MB byte byte. Untuk setiap angka yang Anda baca dari input, atur bit yang sesuai ke '1'. Setelah selesai, ulangi bit-bitnya, temukan bit pertama yang masih '0'. Indeksnya adalah jawabannya.

Jika mereka adalah bilangan bulat 32-bit (kemungkinan dari pilihan ~ 4 miliar angka mendekati 2 ³² ), daftar 4 miliar angka Anda akan menggunakan paling banyak 93% dari bilangan bulat yang mungkin (4 * 10 ⁹ / (2 ³² ) ). Jadi jika Anda membuat bit-array 2 ³² bit dengan masing-masing bit diinisialisasi ke nol (yang akan memakan waktu 2 ²⁹ byte ~ 500 MB RAM; ingat satu byte = 2 ³ bit = 8 bit), bacalah daftar integer Anda dan untuk setiap int atur elemen bit-array yang sesuai dari 0 hingga 1; dan kemudian baca seluruh bit-array Anda dan kembalikan bit pertama yang masih 0.

Jika RAM Anda lebih sedikit (~ 10 MB), solusi ini perlu sedikit dimodifikasi. 10 MB ~ 83886080 bit masih cukup untuk melakukan bit-array untuk semua angka antara 0 dan 83886079. Jadi, Anda dapat membaca daftar int; dan hanya catat #s yang berada di antara 0 dan 83886079 dalam larik bit Anda. Jika jumlahnya didistribusikan secara acak; dengan probabilitas luar biasa (berbeda 100% sekitar 10 ^-2592069 ), Anda akan menemukan int yang hilang). Bahkan, jika Anda hanya memilih angka 1 hingga 2048 (dengan hanya 256 byte RAM), Anda masih akan menemukan angka yang hilang dengan persentase yang luar biasa (99,9999999999999999999999999999999999999999999999999999999999999999999995%) saat itu.

Tetapi katakanlah alih-alih memiliki sekitar 4 miliar angka; Anda memiliki sekitar 2 ³² - 1 angka dan kurang dari 10 MB RAM; jadi setiap rentang int yang kecil hanya memiliki kemungkinan kecil untuk tidak mengandung nomor tersebut.

Jika Anda dijamin bahwa setiap int dalam daftar itu unik, Anda dapat menjumlahkan angka dan mengurangi jumlah dengan satu # hilang dengan jumlah penuh (½) (2 ³² ) (2 ³² - 1) = 9223372034707292160 untuk menemukan int yang hilang . Namun, jika sebuah int terjadi dua kali, metode ini akan gagal.

Namun, Anda selalu dapat membagi dan menaklukkan. Metode naif, akan membaca array dan menghitung jumlah angka yang ada di babak pertama (0 hingga 2 ³¹ -1) dan babak kedua (2 ³¹ , 2 ³² ). Kemudian pilih rentang dengan angka yang lebih sedikit dan ulangi membagi rentang itu menjadi dua. (Katakan jika ada dua angka kurang dalam (2 ³¹ , 2 ³² ) maka pencarian Anda berikutnya akan menghitung angka dalam kisaran (2 ³¹ , 3 * 2 ³⁰ -1), (3 * 2 ³⁰ , 2 ³² ). ulangi sampai Anda menemukan rentang dengan angka nol dan Anda memiliki jawaban Anda. Harus mengambil O (lg N) ~ 32 membaca melalui array.

Metode itu tidak efisien. Kami hanya menggunakan dua bilangan bulat di setiap langkah (atau sekitar 8 byte RAM dengan bilangan bulat 4 byte (32-bit)). Metode yang lebih baik adalah dengan membagi menjadi sqrt (2 ³² ) = 2 ¹⁶ = 65536 nampan, masing-masing dengan 65536 angka dalam bin. Setiap bin membutuhkan 4 byte untuk menyimpan hitungannya, jadi Anda perlu 2 ¹⁸ byte = 256 kB. Jadi bin 0 adalah (0 hingga 65535 = 2 ¹⁶ -1), bin 1 adalah (2 ¹⁶ = 65536 hingga 2 * 2 ¹⁶ -1 = 131071), bin 2 adalah (2 * 2 ¹⁶ = 131072 hingga 3 * 2 ¹⁶ - 1 = 196607). Dengan python Anda akan memiliki sesuatu seperti:

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)

Bacalah daftar integer ~ 4 miliar; dan hitung berapa banyak int yang jatuh di masing-masing 2 ¹⁶ nampan dan temukan tidak lengkap_bin yang tidak memiliki semua 65536 angka. Kemudian Anda membaca daftar bilangan bulat 4 miliar lagi; tapi kali ini hanya perhatikan ketika bilangan bulat berada dalam kisaran itu; membalik sedikit ketika Anda menemukannya.

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

Mengapa membuatnya begitu rumit? Anda meminta bilangan bulat yang tidak ada dalam file?

Menurut aturan yang ditentukan, satu-satunya hal yang Anda butuhkan untuk menyimpan adalah bilangan bulat terbesar yang Anda temui sejauh ini dalam file. Setelah seluruh file dibaca, kembalikan angka 1 lebih besar dari itu.

Tidak ada risiko memukul maxint atau apa pun, karena menurut aturan, tidak ada batasan untuk ukuran bilangan bulat atau jumlah yang dikembalikan oleh algoritma.

Ini dapat diselesaikan dalam ruang yang sangat sedikit menggunakan varian pencarian biner.

1. Mulai dengan rentang angka yang diizinkan, 0hingga 4294967295.

2. Hitung titik tengahnya.

3. Loop melalui file, menghitung berapa angka yang sama, kurang dari atau lebih tinggi dari nilai titik tengah.

4. Jika tidak ada angka yang sama, Anda selesai. Nomor titik tengah adalah jawabannya.

5. Jika tidak, pilih rentang yang memiliki angka paling sedikit dan ulangi dari langkah 2 dengan rentang baru ini.

Ini akan membutuhkan hingga 32 pemindaian linear melalui file, tetapi hanya akan menggunakan beberapa byte memori untuk menyimpan rentang dan jumlah.

Ini pada dasarnya sama dengan solusi Henning , kecuali menggunakan dua tempat sampah bukannya 16k.

EDIT Ok, ini tidak cukup dipikirkan karena mengasumsikan bilangan bulat dalam file mengikuti beberapa distribusi statis. Tampaknya mereka tidak perlu melakukannya, tetapi meskipun demikian orang harus mencoba ini:

Ada .34,3 miliar bilangan bulat 32-bit. Kami tidak tahu bagaimana mereka didistribusikan dalam file, tetapi kasus terburuk adalah yang dengan entropi Shannon tertinggi: distribusi yang sama. Dalam hal ini, kemungkinan salah satu integer tidak muncul dalam file adalah

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

Semakin rendah entropi Shannon, semakin tinggi probabilitas ini pada rata-rata, tetapi bahkan untuk kasus terburuk ini kami memiliki peluang 90% untuk menemukan nomor yang tidak berulang setelah 5 tebakan dengan bilangan bulat acak. Cukup buat angka seperti itu dengan generator pseudorandom, simpan dalam daftar. Kemudian baca int setelah int dan bandingkan dengan semua tebakan Anda. Ketika ada kecocokan, hapus entri daftar ini. Setelah melalui semua file, kemungkinan Anda akan memiliki lebih dari satu tebakan tersisa. Gunakan salah satunya. Dalam peristiwa langka (10% bahkan pada kasus terburuk) tanpa tebakan tersisa, dapatkan satu set bilangan bulat acak baru, mungkin lebih banyak kali ini (10-> 99%).

Konsumsi memori: beberapa lusin byte, kompleksitas: O (n), overhead: neclectable karena sebagian besar waktu akan dihabiskan dalam mengakses hard disk yang tidak dapat dihindari daripada membandingkan ints pula.

Jika Anda memiliki satu bilangan bulat yang hilang dari rentang [0, 2 ^ x - 1] maka cukup kombinasikan semuanya. Sebagai contoh:

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

(Saya tahu ini tidak menjawab pertanyaan dengan tepat , tetapi ini adalah jawaban yang bagus untuk pertanyaan yang sangat mirip.)

Mereka mungkin mencari untuk melihat apakah Anda pernah mendengar tentang Bloom Filter probabilistik yang dapat sangat efisien menentukan secara absolut jika suatu nilai bukan bagian dari set besar, (tetapi hanya dapat menentukan dengan probabilitas tinggi itu adalah anggota set tersebut.)

Berdasarkan kata-kata saat ini dalam pertanyaan awal, solusi paling sederhana adalah:

Temukan nilai maksimum dalam file, lalu tambahkan 1 ke dalamnya.

Gunakan a BitSet. 4 miliar bilangan bulat (dengan asumsi hingga 2 ^ 32 bilangan bulat) yang dikemas ke dalam BitSet pada 8 per byte adalah 2 ^ 32/2 ^ 3 = 2 ^ 29 = sekitar 0,5 Gb.

Untuk menambahkan sedikit lebih detail - setiap kali Anda membaca angka, atur bit yang sesuai di BitSet. Kemudian, lakukan lewati BitSet untuk menemukan nomor pertama yang tidak ada. Bahkan, Anda bisa melakukan ini sama efektifnya dengan berulang kali memilih nomor acak dan menguji jika ada.

Sebenarnya BitSet.nextClearBit (0) akan memberi tahu Anda bit pertama yang tidak disetel.

Melihat pada BitSet API, tampaknya hanya mendukung 0..MAX_INT, jadi Anda mungkin memerlukan 2 BitSets - satu untuk nomor + ve dan satu untuk-sudah nomor - tetapi persyaratan memori tidak berubah.

Jika tidak ada batasan ukuran, cara tercepat adalah mengambil panjang file, dan menghasilkan panjang file + 1 angka acak (atau hanya "11111 ..."). Keuntungan: Anda bahkan tidak perlu membaca file, dan Anda dapat meminimalkan penggunaan memori hampir nol. Kekurangan: Anda akan mencetak miliaran digit.

Namun, jika satu-satunya faktor adalah meminimalkan penggunaan memori, dan tidak ada yang penting, ini akan menjadi solusi optimal. Bahkan mungkin memberi Anda penghargaan "penyalahgunaan terburuk aturan".

Jika kita mengasumsikan bahwa rentang angka akan selalu 2 ^ n (kekuatan genap 2), maka eksklusif-atau akan berfungsi (seperti yang ditunjukkan oleh poster lain). Sejauh mengapa, mari kita buktikan:

Teori

Dengan rentang integer berbasis 0 yang memiliki 2^nelemen dengan satu elemen hilang, Anda dapat menemukan elemen yang hilang hanya dengan xor-ing nilai yang diketahui bersama-sama untuk menghasilkan angka yang hilang.

Bukti

Mari kita lihat n = 2. Untuk n = 2, kita dapat mewakili 4 bilangan bulat unik: 0, 1, 2, 3. Mereka memiliki pola bit:

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

Sekarang, jika kita perhatikan, masing-masing dan setiap bit diatur tepat dua kali. Oleh karena itu, karena ditetapkan beberapa kali, dan eksklusif-atau dari angka akan menghasilkan 0. Jika satu angka hilang, eksklusif-atau akan menghasilkan angka bahwa ketika eksklusif-ored dengan angka yang hilang akan menghasilkan 0. Oleh karena itu, nomor yang hilang, dan nomor eksklusif yang dihasilkan sama persis. Jika kita menghapus 2, xor yang dihasilkan akan 10(atau 2).

Sekarang, mari kita lihat n +1. Mari kita panggil berapa kali setiap bit diatur n, xdan berapa kali setiap bit diatur n+1 y. Nilai yakan sama dengan y = x * 2karena ada xelemen dengan n+1bit yang diatur ke 0, dan xelemen dengan n+1bit yang diatur ke 1. Dan karena 2xakan selalu genap, n+1akan selalu ada setiap bit yang menetapkan angka genap berapa kali.

Oleh karena itu, sejak n=2berfungsi, dan n+1berfungsi, metode xor akan bekerja untuk semua nilai n>=2.

Algoritma Untuk Rentang Berbasis 0

Ini cukup sederhana. Ia menggunakan 2 * n bit memori, jadi untuk rentang apa pun <= 32, 2 bilangan bulat 32 akan bekerja (mengabaikan semua memori yang dikonsumsi oleh deskriptor file). Dan itu membuat satu pass file.

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

Algoritma Untuk Ranges Berbasis Sewenang-wenang

Algoritma ini akan bekerja untuk rentang dari setiap angka awal ke angka akhir mana pun, asalkan total rentangnya sama dengan 2 ^ n ... Ini pada dasarnya mendasarkan kembali rentang untuk memiliki minimum pada 0. Tetapi diperlukan 2 lintasan melalui file (yang pertama untuk meraih minimum, yang kedua untuk menghitung int yang hilang).

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;

Ranges sewenang-wenang

Kita dapat menerapkan metode yang dimodifikasi ini untuk satu set rentang arbitrer, karena semua rentang akan melintasi kekuatan 2 ^ n setidaknya sekali. Ini hanya berfungsi jika ada satu bit yang hilang. Dibutuhkan 2 pass dari file yang tidak disortir, tetapi akan menemukan nomor yang hilang setiap kali:

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;

Pada dasarnya, basiskan kembali rentang sekitar 0. Kemudian, ia menghitung jumlah nilai yang tidak disortir untuk ditambahkan saat menghitung eksklusif-atau. Kemudian, ia menambahkan 1 ke hitungan nilai yang tidak disortir untuk menjaga nilai yang hilang (hitung yang hilang). Kemudian, pertahankan xoring nilai n, bertambah 1 setiap kali hingga n adalah kekuatan 2. Hasilnya kemudian kembali berdasarkan basis asli. Selesai

Berikut algoritma yang saya uji dalam PHP (menggunakan array bukan file, tetapi konsep yang sama):

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

Diberikan dalam array dengan rentang nilai apa pun (saya uji termasuk negatif) dengan satu di dalam rentang yang hilang, itu menemukan nilai yang benar setiap kali.

Pendekatan Lain

Karena kita dapat menggunakan penyortiran eksternal, mengapa tidak memeriksa celahnya saja? Jika kami menganggap file diurutkan sebelum menjalankan algoritma ini:

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;

Tipuan pertanyaan, kecuali jika dikutip dengan tidak tepat. Cukup baca file sekali untuk mendapatkan integer maksimum n, dan kembali n+1.

Tentu saja Anda akan memerlukan rencana cadangan jika seandainya n+1menyebabkan integer overflow.

Periksa ukuran file input, output maka setiap jumlah yang terlalu besar untuk diwakili oleh sebuah file yang ukuran. Ini mungkin tampak seperti trik murah, tetapi ini adalah solusi kreatif untuk masalah wawancara, itu dengan rapi menghindari masalah memori, dan secara teknis 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);
    }
}

Harus mencetak 10 ^bitcount - 1 , yang akan selalu lebih besar dari 2 ^bitcount . Secara teknis, angka yang harus Anda kalahkan adalah 2 ^bitcount - (4 * 10 ⁹ - 1) , karena Anda tahu ada (4 miliar - 1) bilangan bulat lain dalam file, dan bahkan dengan kompresi sempurna mereka akan mengambil setidaknya masing-masing sedikit.

• Pendekatan paling sederhana adalah menemukan angka minimum dalam file, dan mengembalikan 1 kurang dari itu. Ini menggunakan O (1) penyimpanan, dan O (n) waktu untuk file n angka. Namun, itu akan gagal jika rentang angka terbatas, yang bisa membuat min-1 bukan-angka.

• Metode sederhana dan mudah menggunakan bitmap telah disebutkan. Metode itu menggunakan O (n) waktu dan penyimpanan.

• Metode 2-pass dengan 2 ^ 16 menghitung-ember juga telah disebutkan. Bunyinya 2 * n integer, jadi gunakan O (n) waktu dan O (1) penyimpanan, tetapi tidak dapat menangani dataset dengan lebih dari 2 ^ 16 angka. Namun, itu mudah diperluas ke (misalnya) 2 ^ 60 bilangan bulat 64-bit dengan menjalankan 4 lintasan alih-alih 2, dan mudah disesuaikan dengan menggunakan memori kecil dengan menggunakan hanya banyak sampah yang sesuai dengan memori dan meningkatkan jumlah lintasan yang sesuai, di case run time tidak lagi O (n) tetapi sebaliknya O (n * log n).

• Metode XOR'ing semua angka bersama, disebutkan sejauh ini oleh rfrankel dan panjangnya oleh ircmaxell menjawab pertanyaan yang diajukan dalam stackoverflow # 35185 , seperti yang ditunjukkan oleh ltn100. Ini menggunakan O (1) penyimpanan dan O (n) waktu berjalan. Jika untuk saat ini kita mengasumsikan bilangan bulat 32-bit, XOR memiliki probabilitas 7% untuk menghasilkan angka yang berbeda. Dasar Pemikiran: diberikan ~ angka-angka berbeda 4G XOR bersama, dan ca. 300M tidak dalam file, jumlah bit yang ditetapkan di setiap posisi bit memiliki peluang yang sama untuk menjadi ganjil atau genap. Dengan demikian, 2 ^ 32 angka memiliki kemungkinan yang sama muncul sebagai hasil XOR, di mana 93% sudah ada dalam file. Perhatikan bahwa jika angka-angka dalam file tidak semuanya berbeda, probabilitas keberhasilan metode XOR meningkat.

Untuk beberapa alasan, segera setelah saya membaca masalah ini saya memikirkan diagonalisasi. Saya mengasumsikan bilangan bulat besar sewenang-wenang.

Baca angka pertama. Kiri-pad dengan nol bit hingga Anda memiliki 4 miliar bit. Jika bit pertama (tingkat tinggi) adalah 0, output 1; selain itu output 0. (Anda tidak benar-benar harus meninggalkan-pad: Anda hanya output 1 jika tidak ada cukup bit dalam jumlahnya.) Lakukan hal yang sama dengan angka kedua, kecuali gunakan bit kedua. Lanjutkan melalui file dengan cara ini. Anda akan menghasilkan bit nomor 4 miliar satu bit pada satu waktu, dan angka itu tidak akan sama dengan yang ada di file. Bukti: itu sama dengan angka ke-n, maka mereka akan menyetujui bit ke-n, tetapi mereka tidak dengan konstruksi.

Anda bisa menggunakan tanda bit untuk menandai apakah integer ada atau tidak.

Setelah melintasi seluruh file, pindai setiap bit untuk menentukan apakah jumlahnya ada atau tidak.

Dengan asumsi masing-masing integer adalah 32 bit, mereka akan cocok dengan 1 GB RAM jika bit flagging dilakukan.

Lepaskan spasi putih dan karakter non numerik dari file dan tambahkan 1. File Anda sekarang berisi satu nomor yang tidak tercantum dalam file asli.

Dari Reddit oleh Carbonetc.

Hanya demi kelengkapan, berikut ini adalah solusi lain yang sangat sederhana, yang kemungkinan besar akan membutuhkan waktu yang sangat lama untuk dijalankan, tetapi menggunakan sedikit memori.

Biarkan semua integer yang memungkinkan menjadi rentang dari int_minhingga int_max, dan bool isNotInFile(integer)fungsi yang mengembalikan true jika file tidak mengandung integer tertentu dan false lainnya (dengan membandingkan integer tertentu itu dengan setiap integer dalam file)

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

Untuk batasan memori 10 MB:

1. Ubah angka menjadi representasi binernya.
2. Buat pohon biner di mana kiri = 0 dan kanan = 1.
3. Masukkan setiap angka di pohon menggunakan representasi binernya.
4. Jika nomor sudah dimasukkan, daun sudah akan dibuat.

Setelah selesai, ambil jalur yang belum pernah dibuat sebelumnya untuk membuat nomor yang diminta.

4 miliar angka = 2 ^ 32, artinya 10 MB mungkin tidak cukup.

EDIT

Optimalisasi dimungkinkan, jika dua ujung daun telah dibuat dan memiliki induk yang sama, maka mereka dapat dihapus dan induk ditandai sebagai bukan solusi. Ini memotong cabang dan mengurangi kebutuhan akan memori.

EDIT II

Tidak perlu membangun pohon sepenuhnya juga. Anda hanya perlu membangun cabang yang dalam jika jumlahnya sama. Jika kita memotong cabang juga, maka solusi ini mungkin akan berhasil.

Saya akan menjawab versi 1 GB:

Tidak ada informasi yang cukup dalam pertanyaan, jadi saya akan menyatakan beberapa asumsi pertama:

Integer adalah 32 bit dengan kisaran -2,147.483.648 hingga 2.147.483.647.

Kode semu:

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

Selama kita melakukan jawaban kreatif, ini satu lagi.

Gunakan program pengurutan eksternal untuk mengurutkan file input secara numerik. Ini akan bekerja untuk sejumlah memori yang Anda miliki (ini akan menggunakan penyimpanan file jika diperlukan). Baca melalui file yang diurutkan dan output nomor pertama yang hilang.

Penghapusan bit

Salah satu caranya adalah dengan menghilangkan bit, namun ini mungkin tidak benar-benar menghasilkan hasil (kemungkinan tidak akan). Psuedocode:

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

Hitungan bit

Melacak jumlah bit; dan gunakan bit dengan jumlah paling sedikit untuk menghasilkan nilai. Sekali lagi ini tidak memiliki jaminan menghasilkan nilai yang benar.

Rentang Logika

Melacak rentang daftar yang dipesan (dipesan oleh awal). Rentang ditentukan oleh struktur:

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

Telusuri setiap nilai dalam file dan coba serta hapus dari rentang saat ini. Metode ini tidak memiliki jaminan memori, tetapi harus dilakukan dengan cukup baik.

2 ^{128 * 10 18} +1 (yaitu (2 ⁸ ) ^{16 * 10 18} +1) - tidak bisakah itu menjadi jawaban universal untuk hari ini? Ini merupakan angka yang tidak dapat disimpan dalam 16 file EB, yang merupakan ukuran file maksimum dalam sistem file saat ini.

Saya pikir ini adalah masalah yang diselesaikan (lihat di atas), tetapi ada kasus sampingan yang menarik untuk diingat karena mungkin ditanyakan:

Jika ada persis 4.294.967.295 (2 ^ 32 - 1) bilangan bulat 32-bit tanpa pengulangan, dan karena itu hanya satu yang hilang, ada solusi sederhana.

Mulai total berjalan di nol, dan untuk setiap integer dalam file, tambahkan integer itu dengan 32-bit overflow (efektif, runningTotal = (runningTotal + nextInteger)% 4294967296). Setelah selesai, tambahkan 4294967296/2 ke total yang berjalan, lagi dengan 32-bit overflow. Kurangi ini dari 4294967296, dan hasilnya adalah bilangan bulat yang hilang.

Masalah "hanya satu integer yang hilang" dapat dipecahkan dengan hanya satu kali dijalankan, dan hanya 64 bit RAM yang didedikasikan untuk data (32 untuk total yang berjalan, 32 untuk dibaca pada integer berikutnya).

Konsekuensi: Spesifikasi yang lebih umum sangat sederhana untuk dicocokkan jika kita tidak peduli dengan berapa banyak bit yang harus dimiliki oleh hasil integer. Kami hanya menghasilkan integer yang cukup besar sehingga tidak dapat dimuat dalam file yang kami berikan. Sekali lagi, ini membutuhkan RAM yang sangat minim. Lihat kodesemu.

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

Seperti kata Ryan pada dasarnya, urutkan file dan kemudian pergi ke bilangan bulat dan ketika nilai dilewati di sana Anda memilikinya :)

EDIT at downvoters: OP menyebutkan bahwa file dapat diurutkan jadi ini adalah metode yang valid.

Jika Anda tidak menganggap batasan 32-bit, kembalikan nomor 64-bit yang dihasilkan secara acak (atau 128-bit jika Anda pesimis). Peluang tabrakan adalah 1 in 2^64/(4*10^9) = 4611686018.4(kira-kira 1 banding 4 milyar). Anda benar sebagian besar waktu!

(Bercanda ... agak.)