Anda diberi file yang berisi semua angka yang mungkin pada arsitektur 32-bit. 4 nomor hilang dari file itu. Temukan 4 nomor yang hilang

Ini adalah pertanyaan wawancara yang telah saya temui beberapa kali, dan saya benar-benar tidak yakin bagaimana menyelesaikannya mengingat empat angka hilang. Saya terbiasa dengan algoritme untuk menemukan satu atau dua angka yang hilang, tetapi saya tidak melihat cara untuk menggeneralisasikan keduanya menjadi empat.

Baik itu untuk wawancara atau pekerjaan aktual, prioritas pertama Anda harus menjadi solusi kerja yang masuk akal bagi Anda . Itu biasanya berarti Anda harus menawarkan solusi pertama yang dapat Anda pikirkan yang sederhana dan mudah untuk Anda jelaskan.

Bagi saya, itu berarti mengurutkan angka dan memindai celah. Tapi, saya bekerja pada sistem bisnis dan aplikasi web. Saya tidak mengutak-atik bit, dan saya tidak ingin tim saya melakukannya!

Jika Anda mewawancarai pekerjaan tingkat rendah, lebih dekat dengan logam, "menyortir" mungkin akan dipenuhi dengan tatapan kosong. Mereka ingin Anda menjadi pemikiran yang nyaman tentang bit dan sebagainya. Jawaban pertama Anda seharusnya ada, "Oh, saya akan menggunakan Bitmap." (Atau bit array, atau bit set.)

Dan kemudian, bagaimanapun juga - bahkan jika Anda memberikan solusi "salah", jika pewawancara Anda (atau bos!) Mendesak untuk itu , Anda dapat menyarankan beberapa perbaikan atau alternatif, dengan fokus pada bidang perhatian khusus manajer.

• RAM sangat terbatas? Kurang dari 512MB?
  Sortir di tempat, di disk. Anda dapat menggunakan jumlah RAM yang sebagian besar arbitrer untuk mengoptimalkan dan / atau buffer blok yang diurutkan.
• Waktu terbatas?
  Gunakan RAM itu! Penyortiran sudah O(n*log(n)). (Atau O (n) untuk jenis integer-bucket!)
• Kemampuan perawatan?
  Apa yang bisa lebih mudah daripada menyortir ?!
• Tidak menunjukkan pengetahuan tentang bendera / bidang bit? ( BitSet/ BitMap/ BitArray)
  Baiklah OK ... silakan dan gunakan BitArrayuntuk menandai "angka yang ditemukan." Dan kemudian memindai 0.
• Kompleksitas "real-time" yang dapat diprediksi ?
  Gunakan solusi bitmap. Ini adalah satu melewati file dan satu lagi melewatiBitArray/BitSet(untuk menemukan0itu). Yang iniO(n), saya pikir!

Atau terserah.

Atasi masalah yang sebenarnya Anda miliki. Selesaikan dulu masalahnya, gunakan solusi naif jika perlu. Jangan buang waktu semua orang untuk mengatasi masalah yang belum ada.

Karena ini adalah file, saya berasumsi Anda diizinkan membuat beberapa lintasan. Pertama buat array 256 penghitung, beralih di atas file dan untuk setiap kenaikan angka penghitung diindeks sebagai byte pertama nomor tersebut. Ketika Anda selesai, sebagian besar penghitung harus di 2 ^ 24, tetapi 1 hingga 4 penghitung harus memiliki nilai yang lebih rendah. Masing-masing indeks ini mewakili byte pertama dari salah satu angka yang hilang (jika ada kurang dari 4 itu karena beberapa angka yang hilang berbagi byte pertama yang sama).

Untuk masing-masing indeks ini, buat array lain dari 256 penghitung, dan buat lintasan kedua pada file. Kali ini, jika byte pertama adalah salah satu nilai dari sebelumnya, tambahkan penghitung di lariknya berdasarkan byte kedua . Setelah selesai, cari lagi penghitung yang lebih rendah dari 2 ^ 16, dan Anda akan memiliki byte kedua dari angka yang hilang, masing-masing cocok dengan byte pertama itu.

Lakukan lagi untuk byte ketiga (perhatikan bahwa Anda membutuhkan maksimum 4 array di setiap pass, meskipun setiap byte dapat diikuti hingga 4 byte yang berbeda) dan untuk byte keempat, dan Anda telah menemukan semua angka yang hilang.

Kompleksitas waktu - Kompleksitas O(n * log n)
ruang - konstan !

Edit:

Sebenarnya, saya menganggapnya n=2^32sebagai parameter, tetapi jumlah angka yang hilang k=4juga merupakan parameter. Dengan asumsi k<<nini berarti kompleksitas ruang adalah O(k).

Memperbarui:

Hanya untuk bersenang-senang (dan karena saya saat ini mencoba untuk belajar Rust) Saya menerapkannya di Rust: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f . Saya memilih untuk memiliki representasi tekstual, karena seseorang akan menjalankannya dengan ~ 2 ^ 32 angka ...

Jika ini Java, Anda bisa menggunakan BitSet. Yah, dua dari mereka, karena mereka tidak bisa memegang semua angka 32 bit. Kode kerangka, mungkin buggy:

BitSet bitsetForPositives = new Bitset(2^31);  // obviously not 2^31 but you get the idea
BitSet bitsetForNegatives = new Bitset(2^31);

for (int value: valuesTheyPassInSomehow) {
  if ((value & 0x80000000) == 0)
     bitsetForPositives.set(value );
  else
     bitsetForNegatives.set(value & ~0x80000000);
}

Kemudian gunakan BitSet.nextClearBit()untuk menemukan siapa yang hilang.

Catatan ditambahkan jauh kemudian:

Perhatikan bahwa dengan algoritma ini, cukup mudah untuk menjalankan bagian yang memakan waktu secara paralel . Katakanlah file asli telah dipecah menjadi empat bagian yang kira-kira sama. Alokasikan 4 pasang BitSets (2GB, masih dapat dikelola).

1. Memiliki empat utas, secara paralel, masing-masing memproses satu file menjadi sepasang BitSet mereka sendiri.
2. Ketika selesai, kembali ke utas tunggal, atau Bit (waktu sepele), lalu panggil nextClearBit empat kali (juga waktu yang cukup sepele).

Saya berharap I / O masih menjadi langkah pembatasan tingkat, tetapi jika secara ajaib semua angka ada di memori Anda benar-benar dapat mempercepat.

Pertanyaan ini dapat diselesaikan dengan menggunakan array bit (true / false). Ini harus menjadi struktur yang paling efisien untuk menyimpan jawaban untuk semua angka menggunakan indeks array untuk menyimpan apakah nomor tertentu ditemukan.

C #

var bArray = new BitArray(Int32.MaxValue);

//Assume the file has 1 number per line
using (StreamReader sr = File.OpenText(fileName))
{
        string s = String.Empty;
        while ((s = sr.ReadLine()) != null)
        {
            var n = int32.Parse(s);
            bArray[n] = true;
        }
}

Kemudian hanya beralih melalui array dan untuk nilai-nilai yang masih salah mereka tidak ada dalam file.

Anda dapat memecah file menjadi potongan-potongan yang lebih kecil tetapi saya dapat mengalokasikan array ukuran maks int32 penuh (2147483647) pada laptop 16.0 GB saya yang menjalankan Windows 7 (64 bit).

Bahkan jika saya tidak menjalankan 64 bit saya bisa mengalokasikan bit array yang lebih kecil. Saya akan melakukan pra-proses file membuat satu set file yang lebih kecil masing-masing dengan kisaran [0-64000] [64001-128000], dll angka di dalamnya yang akan cocok untuk sumber daya lingkungan yang tersedia. Pergi melalui file besar dan tulis masing-masing angka ke file set yang sesuai. Kemudian proses setiap file yang lebih kecil. Ini akan memakan waktu sedikit lebih lama karena langkah pra-pemrosesan, tetapi ini akan mengatasi keterbatasan sumber daya jika ada sumber daya yang terbatas.

Karena ini adalah pertanyaan wawancara, saya akan menunjukkan kepada pewawancara beberapa pemahaman tentang kendala. Lalu, apa artinya "semua angka yang mungkin"? Apakah ini benar-benar 0 ... 2 <(32-1) seperti dugaan semua orang? Arsitektur 32-bit biasa dapat bekerja dengan lebih dari sekedar angka 32 bit. Itu hanya masalah representasi, jelas.

Apakah itu harus diselesaikan pada sistem 32-bit, atau apakah itu lebih merupakan bagian dari pembatasan angka? Misalnya, sistem 32-bit yang khas tidak akan dapat memuat file ke dalam RAM sekaligus. Saya juga menyebutkan bahwa sistem 32-bit sering tidak dapat memiliki file yang berisi semua angka karena batasan ukuran file. Ya, kecuali jika ada beberapa pengkodean yang cerdas, seperti "Semua angka kecuali keempatnya", dalam hal ini masalahnya diselesaikan dengan mudah.

Tetapi jika Anda benar-benar ingin memahami pertanyaan sebagai "Diberikan file dengan semua angka dari 0 ... 2 ^ (32-1) kecuali beberapa, beri saya yang hilang" (dan ini besar jika !), Lalu ada banyak cara untuk menyelesaikannya.

Sepele tetapi tidak dapat diterima: Untuk setiap nomor yang mungkin, pindai file dan lihat apakah ada di sana.

Dengan 512 MB RAM dan file single pass through: tandai setiap angka (= atur bit pada indeks itu) baca dari file, dan setelah itu lulus RAM sekali dan lihat yang hilang.

Salah satu pendekatan yang mudah diingat dan mudah diartikulasikan dalam wawancara adalah dengan menggunakan fakta bahwa jika Anda melihat semua angka dalam N bit, setiap bit akan diatur tepat setengah dari nilai-nilai itu dan tidak diatur di setengah lainnya. .

Jika Anda mengulangi semua nilai dalam file dan menyimpan 32 jumlah nilai di akhir, Anda akan berakhir dengan 32 nilai yang persis (2 ^ 32/2) atau sedikit kurang dari nilai itu. Perbedaan yang maksimum (2 ^ 32/2) dan total memberi Anda total bit yang diatur di setiap posisi dari nilai yang hilang.

Setelah Anda memilikinya, Anda dapat menentukan semua set yang mungkin dari 4 nilai yang dapat memberikan total tersebut. Karena itu, Anda kemudian dapat menelusuri nilai-nilai dalam file lagi memeriksa nilai apa pun yang merupakan bagian dari kombinasi tersebut. Saat Anda menemukannya, kombinasi yang mengandung nilai tersebut dihilangkan sebagai kemungkinan. Setelah Anda hanya memiliki satu kemungkinan kombinasi yang tersisa, Anda memiliki jawabannya.

Misalnya menggunakan nibble, Anda memiliki nilai berikut:

1010
0110
1111
0111
1101
1001
0100
0101
0001
1011
1100
1110

Total bit yang diatur di setiap posisi adalah:

7867

Mengurangkan mereka dari 8 (4 ^ 2/2) kita dapatkan:

1021

Yang berarti ada 4 set nilai berikut yang mungkin:

1000
0000
0011
0010

1010
0001
0010
0000

(maafkan saya jika saya melewatkan sesuatu, saya hanya melakukan ini dengan melihat)

Dan kemudian melihat angka aslinya lagi, kami menemukan 1010 segera yang berarti set pertama adalah jawabannya.

Dengan asumsi bahwa file tersebut diurutkan dengan meningkatnya angka:

Pastikan bahwa itu memang berisi (2³²-4) angka.
Sekarang jika file selesai (atau jika 4 angka yang hilang adalah 4 yang terakhir), membaca kata apa pun di file pada posisi N akan mengembalikan nilai yang cocok N.

Gunakan pencarian dikotomi pada posisi [0..2³²-4-1) untuk mencari untuk menemukan nomor X1 pertama yang tidak diharapkan.
Setelah menemukan nomor yang hilang pertama, lakukan pencarian diktotomi lagi pada posisi [X1 .. (2³²-4-1)] untuk menemukan angka kedua yang hilang, X2: Kali ini, membaca kata pada posisi N harus mengembalikan nilai kecocokan N-1 jika tidak ada lagi nomor yang hilang (karena Anda telah melewati satu nomor yang hilang).
Iterasi juga untuk dua angka yang tersisa. Pada iterasi ketiga, kata yang dibaca pada posisi N harus kembali N-2, dan pada keempat, itu harus mengembalikan N-3.

Peringatan: Saya belum menguji ini. Tapi saya pikir itu harus berhasil. :)

Sekarang dalam kehidupan nyata, saya setuju dengan jawaban lain: pertanyaan pertama adalah tentang lingkungan. Apakah kita memiliki RAM yang tersedia (berapa banyak), adalah file pada perangkat penyimpanan akses langsung, apakah ini operasi satu-shot (tidak diperlukan optimasi) atau yang kritis (setiap siklus dihitung), apakah kita memiliki utilitas sortir eksternal yang tersedia , dll.
Kemudian temukan kompromi yang dapat diterima untuk konteksnya. Ini setidaknya menunjukkan bahwa Anda mulai menganalisis masalah sebelum mencari algoritma.

Seperti semua pertanyaan standar, solusinya adalah dengan Google sebelum wawancara.

Pertanyaan dan variasi ini memiliki jawaban 'benar' yang pasti yang melibatkan XORing semua angka. Seharusnya menunjukkan Anda memahami indeks dalam database atau sesuatu. Jadi nol poin untuk 'mungkin bekerja tetapi tidak apa yang tertulis di atas kertas' jawaban banyak.

Di sisi positifnya ada serangkaian pertanyaan yang terbatas, revisi beberapa jam akan membuat Anda terlihat seperti jenius. Ingatlah untuk berpura-pura Anda mengerjakannya di kepala Anda.

Edit. Ahh sepertinya untuk 4 ada pendekatan yang berbeda dari XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

Edit. Downvoters: Ini adalah solusi buku teks O (n) yang dipublikasikan untuk masalah persis yang dinyatakan dalam OP.