Pertanyaan Pertanyaan wawancara mudah semakin sulit: diberi nomor 1..100, temukan nomor yang hilang


Saya memiliki pengalaman wawancara kerja yang menarik beberapa waktu yang lalu. Pertanyaannya dimulai sangat mudah:

Q1: Kami memiliki tas yang berisi angka 1, 2, 3, ..., 100. Setiap angka muncul tepat satu kali, jadi ada 100 angka. Sekarang satu nomor secara acak diambil dari tas. Temukan nomor yang hilang.

Saya pernah mendengar pertanyaan wawancara ini sebelumnya, tentu saja, jadi saya sangat cepat menjawab di sepanjang baris:

A1: Nah, jumlah angka 1 + 2 + 3 + … + N aku s (N+1)(N/2) (Lihat Wikipedia: jumlah seri aritmatika). Untuk N = 100, jumlahnya 5050.

Jadi, jika semua angka ada di kantong, jumlahnya akan tepat 5050. Karena satu nomor hilang, jumlahnya akan kurang dari ini, dan selisihnya adalah angka itu. Jadi kita dapat menemukan nomor yang hilang itu O(N) waktu dan O(1) ruang.

Pada titik ini saya pikir saya telah melakukannya dengan baik, tetapi tiba-tiba pertanyaan itu berubah secara tak terduga:

Q2: Itu benar, tapi sekarang bagaimana Anda akan melakukan ini jika DUA nomor yang hilang?

Saya belum pernah melihat / mendengar / mempertimbangkan variasi ini sebelumnya, jadi saya panik dan tidak bisa menjawab pertanyaan itu. Pewawancara bersikeras untuk mengetahui proses berpikir saya, jadi saya menyebutkan bahwa mungkin kita bisa mendapatkan lebih banyak informasi dengan membandingkan dengan produk yang diharapkan, atau mungkin melakukan umpan kedua setelah mengumpulkan beberapa informasi dari umpan pertama, dll, tapi saya benar-benar hanya menembak dalam kegelapan daripada benar-benar memiliki jalan yang jelas menuju solusi.

Pewawancara berusaha untuk mendorong saya dengan mengatakan bahwa memiliki persamaan kedua memang salah satu cara untuk memecahkan masalah. Pada titik ini saya agak kesal (karena tidak mengetahui jawabannya sebelumnya), dan bertanya apakah ini adalah teknik pemrograman umum (baca: "berguna"), atau apakah itu hanya tipu muslihat / jawaban.

Jawaban pewawancara mengejutkan saya: Anda dapat menyamaratakan teknik untuk menemukan 3 nomor yang hilang. Bahkan, Anda dapat menyamaratakannya untuk menemukannya k nomor yang hilang.

Qk: Jika persis k nomor yang hilang dari tas, bagaimana Anda akan menemukannya secara efisien?

Ini beberapa bulan yang lalu, dan saya masih belum bisa mengetahui apa teknik ini. Tentunya ada a Ω(N) batas waktu yang lebih rendah karena kita harus memindai semua angka setidaknya sekali, tetapi pewawancara bersikeras bahwa WAKTU dan RUANG kompleksitas teknik penyelesaian (minus O(N) pemindaian input waktu) ditentukan dalam k tidak N.

Jadi pertanyaannya di sini sederhana:

  • Bagaimana Anda akan memecahkannya Q2?
  • Bagaimana Anda akan memecahkannya Q3?
  • Bagaimana Anda akan memecahkannya Qk?

Klarifikasi

  • Umumnya ada N angka dari 1 ..N, bukan hanya 1..100.
  • Saya tidak mencari solusi berbasis set yang jelas, mis. menggunakan sebuah set bit, encoding ada / tidaknya setiap nomor dengan nilai bit yang ditunjuk, karena itu menggunakan O(N)bit di ruang tambahan. Kami tidak bisa membeli ruang tambahan yang proporsional N.
  • Saya juga tidak mencari pendekatan pertama yang jelas. Ini dan pendekatan berbasis-set layak disebutkan dalam sebuah wawancara (mereka mudah dilaksanakan, dan tergantung pada N, bisa sangat praktis). Saya mencari solusi Holy Grail (yang mungkin atau mungkin tidak praktis untuk diterapkan, tetapi memiliki karakteristik asimtotik yang diinginkan tetap demikian).

Jadi sekali lagi, tentu saja Anda harus memindai masukan O(N), tetapi Anda hanya dapat menangkap sedikit informasi (didefinisikan dalam istilah k tidak N), dan kemudian harus mencari k nomor yang hilang entah bagaimana.


983
2017-08-16 10:26


asal


Jawaban:


Berikut ringkasannya Dimitris Andreou link.

Ingat jumlah kekuatan ke-i, di mana i = 1,2, .., k. Ini mengurangi masalah untuk memecahkan sistem persamaan

Sebuah1 + a2 + ... + ak = b1

Sebuah12 + a22 + ... + ak2 = b2

...

Sebuah1k + a2k + ... + akk = bk

Menggunakan Identitas Newton, mengetahui bsaya memungkinkan untuk menghitung

c1 = a1 + a2 + ... ak

c2 = a1Sebuah2 + a1Sebuah3 + ... + ak-1Sebuahk

...

ck = a1Sebuah2 ... Sebuahk

Jika Anda memperluas polinomial (x-a1) ... (x-ak) Koefisiennya akan tepat c1, ..., ck - Lihat Formula Viète. Karena setiap faktor polinomial unik (cincin polinomial adalah sebuah Domain Euclidean), ini berarti asaya ditentukan secara unik, hingga permutasi.

Ini mengakhiri bukti bahwa mengingat kekuatan sudah cukup untuk memulihkan angka. Untuk k konstan, ini adalah pendekatan yang baik.

Namun, ketika k bervariasi, pendekatan langsung komputasi c1, ..., ck sangat mahal, karena mis. ck adalah produk dari semua nomor yang hilang, besarnya n! / (n-k) !. Untuk mengatasinya, lakukan perhitungan dalam Zq field, di mana q adalah prime seperti n <= q <2n - itu ada oleh Postulat Bertrand. Buktinya tidak perlu diubah, karena formula masih berlaku, dan faktorisasi polinomial masih unik. Anda juga memerlukan algoritme untuk faktorisasi di atas bidang terbatas, misalnya yang oleh Berlekamp atau Cantor-Zassenhaus.

Tingkat pseudocode tinggi untuk konstanta k:

  • Hitung kekuatan ke-i dari bilangan yang diberikan
  • Kurangi untuk mendapatkan jumlah kekuatan ke-i dari nomor yang tidak dikenal. Call the sums bsaya.
  • Gunakan identitas Newton untuk menghitung koefisien dari bsaya; hubungi mereka csaya. Pada dasarnya, c1 = b1; c2 = (c1b1 - b2) / 2; lihat Wikipedia untuk rumus yang tepat
  • Faktorkan polinomial xk-c1xk-1 + ... + ck.
  • Akar dari polinomial adalah angka yang dibutuhkan a1, ..., Sebuahk.

Untuk berbagai k, cari prime n <= q <2n menggunakan mis. Miller-Rabin, dan melakukan langkah-langkah dengan semua angka dikurangi modulo q.

Sebagai Heinrich Apfelmus berkomentar, bukannya q prima Anda dapat menggunakan q = 2⌈log n⌉ dan tampil aritmatika di bidang terbatas.


512
2017-08-16 12:13



Anda akan menemukannya dengan membaca beberapa halaman Muthukrishnan - Algoritma Aliran Data: Teka-teki 1: Menemukan Angka yang Hilang. Ini menunjukkan persis generalisasi yang Anda cari. Mungkin inilah yang dibaca oleh pewawancara Anda dan mengapa ia mengajukan pertanyaan-pertanyaan ini.

Sekarang, jika hanya orang yang mulai menghapus jawaban yang dimasukkan atau digantikan oleh perlakuan Muthukrishnan, dan membuat teks ini lebih mudah ditemukan. :)


Juga lihat sdcvvc jawaban yang terkait langsung, yang juga termasuk pseudocode (hore! tidak perlu membaca formulasi matematika yang rumit :)) (terima kasih, kerja yang luar biasa!).


226
2017-08-16 11:26



Kita dapat memecahkan Q2 dengan menjumlahkan kedua angka itu sendiri, dan kotak dari angka-angka.

Kami kemudian dapat mengurangi masalah

k1 + k2 = x
k1^2 + k2^2 = y

Dimana x dan y seberapa jauh jumlah tersebut di bawah nilai yang diharapkan.

Substitusi memberi kita:

(x-k2)^2 + k2^2 = y

Yang kemudian bisa kita pecahkan untuk menentukan nomor yang hilang.


159
2017-08-16 10:37



Seperti yang ditunjukkan @j_random_hacker, ini sangat mirip dengan Menemukan duplikat dalam waktu O (n) dan O (1), dan adaptasi dari jawaban saya di sana juga bekerja di sini.

Dengan asumsi bahwa "tas" diwakili oleh larik berbasis 1 A[] ukuran N - k, kita bisa menyelesaikan Qk di O(N) waktu dan O(k) ruang tambahan.

Pertama, kami memperluas array kami A[] oleh k elemen, sehingga sekarang ukuran N. Ini adalah O(k) ruang tambahan. Kami kemudian menjalankan algoritma pseudo-code berikut:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

Loop pertama menginisialisasi k entri tambahan yang sama dengan entri pertama dalam larik (ini hanya nilai praktis yang kami tahu sudah ada dalam larik - setelah langkah ini, entri apa pun yang tidak ada dalam larik awal ukuran N-k masih hilang dalam array diperpanjang).

Loop kedua memungkinkan array diperpanjang sehingga jika elemen x hadir setidaknya sekali, maka salah satu entri tersebut akan berada di posisi A[x].

Perhatikan bahwa meskipun memiliki loop nested, ia masih berjalan O(N) waktu - swap hanya terjadi jika ada i seperti yang A[i] != i, dan setiap swap set setidaknya satu elemen seperti itu A[i] == i, di mana itu tidak benar sebelumnya. Ini berarti jumlah total swap (dan dengan demikian jumlah total eksekusi dari while tubuh loop) paling banyak N-1.

Lingkaran ketiga mencetak indeks-indeks dari array i yang tidak ditempati oleh nilai i - Ini artinya itu i pasti hilang.


120
2018-04-22 04:32



Saya meminta seorang 4 tahun untuk memecahkan masalah ini. Dia memilah angka dan kemudian menghitungnya. Ini memiliki kebutuhan ruang O (lantai dapur), dan bekerja dengan mudah namun banyak bola yang hilang.


114
2018-04-12 18:59



Tidak yakin, jika itu solusi yang paling efisien, tapi saya akan mengulang semua entri, dan menggunakan bitet untuk diingat, nomor mana yang ditetapkan, dan kemudian menguji 0 bit.

Saya suka solusi sederhana - dan saya bahkan percaya, bahwa itu mungkin lebih cepat daripada menghitung jumlah, atau jumlah kuadrat dll.


30
2017-08-16 10:38



Saya belum memeriksa matematika, tapi saya menduga komputasi itu Σ(n^2) di pass yang sama seperti yang kita hitung Σ(n) akan memberikan info yang cukup untuk mendapatkan dua nomor yang hilang, Do Σ(n^3) juga jika ada tiga, dan seterusnya.


29
2017-08-16 10:38



Masalah dengan solusi berdasarkan jumlah angka adalah mereka tidak memperhitungkan biaya penyimpanan dan bekerja dengan angka dengan eksponen besar ... dalam prakteknya, untuk bekerja untuk n yang sangat besar, pustaka angka besar akan digunakan. . Kami dapat menganalisis pemanfaatan ruang untuk algoritma ini.

Kita dapat menganalisis kompleksitas waktu dan ruang dari algoritma sdcvvc dan Dimitris Andreou.

Penyimpanan:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

Begitu l_j \in \Theta(j log n)

Total penyimpanan yang digunakan: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Ruang yang digunakan: mengasumsikan komputasi itu a^j dibutuhkan ceil(log_2 j) waktu, total waktu:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

Total waktu yang digunakan: \Theta(kn log n)

Jika waktu dan ruang ini memuaskan, Anda dapat menggunakan rekursif sederhana algoritma. Biarkan b! I menjadi entri engan di tas, n jumlah angka sebelumnya kepindahan, dan k jumlah penghapusan. Dalam sintaks Haskell ...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

Penyimpanan yang digunakan: O(k) untuk daftar, O(log(n)) untuk stack: O(k + log(n)) Algoritma ini lebih intuitif, memiliki kompleksitas waktu yang sama, dan menggunakan lebih sedikit ruang.


12
2017-09-02 11:41



Tunggu sebentar. Seperti yang dinyatakan, ada 100 angka di tas. Tidak peduli seberapa besar k, masalah dapat diselesaikan dalam waktu yang konstan karena Anda dapat menggunakan satu set dan menghapus angka dari set di paling banyak 100 - k iterasi loop. 100 konstan. Kumpulan angka yang tersisa adalah jawaban Anda.

Jika kita menggeneralisasi solusi ke angka dari 1 hingga N, tidak ada perubahan kecuali N bukan konstanta, jadi kita berada dalam O (N - k) = O (N) waktu. Sebagai contoh, jika kita menggunakan bit set, kita atur bit menjadi 1 dalam waktu O (N), iterate melalui angka, atur bit ke 0 saat kita pergi (O (Nk) = O (N)) dan kemudian kita punya jawabannya.

Sepertinya saya bahwa pewawancara bertanya kepada Anda bagaimana mencetak isi dari set akhir dalam waktu O (k) daripada waktu O (N). Jelas, dengan sedikit mengatur, Anda harus mengulang melalui semua bit N untuk menentukan apakah Anda harus mencetak angka atau tidak. Namun, jika Anda mengubah cara pengaturan ini diterapkan, Anda dapat mencetak angka dalam k iterasi. Ini dilakukan dengan menempatkan angka-angka ke dalam objek yang akan disimpan di kedua set hash dan daftar terkait ganda. Saat Anda menghapus objek dari himpunan hash, Anda juga menghapusnya dari daftar. Jawabannya akan tersisa di daftar yang sekarang panjangnya k.


10
2017-08-16 11:25