Dapatkan 100 angka tertinggi dari daftar tanpa batas

Salah satu teman saya ditanyai pertanyaan wawancara ini -

"Ada aliran angka konstan yang datang dari daftar angka tak terbatas yang darinya Anda perlu mempertahankan struktur data untuk mengembalikan 100 angka tertinggi teratas pada suatu titik waktu tertentu. Anggap semua angka itu hanya angka utuh."

Ini sederhana, Anda perlu menyimpan daftar yang diurutkan dalam urutan menurun dan melacak pada nomor terendah dalam daftar itu. Jika nomor baru yang diperoleh lebih besar dari angka terendah itu maka Anda harus menghapus angka terendah itu dan memasukkan nomor baru itu dalam daftar yang disortir sesuai kebutuhan.

Kemudian pertanyaan diperpanjang -

"Bisakah kamu memastikan bahwa Orde untuk penyisipan harus O (1)? Apakah mungkin?"

Sejauh yang saya tahu, bahkan jika Anda menambahkan nomor baru ke daftar dan mengurutkannya lagi menggunakan algoritma apa pun, yang terbaik adalah O (logn) untuk quicksort (saya pikir). Jadi teman saya mengatakan itu tidak mungkin. Tapi dia tidak yakin, dia meminta untuk mempertahankan struktur data lain daripada daftar.

Saya berpikir tentang pohon Biner seimbang, tetapi bahkan di sana Anda tidak akan mendapatkan penyisipan dengan urutan 1. Jadi pertanyaan yang sama saya miliki sekarang juga. Ingin tahu apakah ada struktur data seperti itu yang dapat melakukan penyisipan dalam Urutan 1 untuk masalah di atas atau tidak mungkin sama sekali.

Katakanlah k adalah jumlah angka tertinggi yang ingin Anda ketahui (100 dalam contoh Anda). Kemudian, Anda bisa menambahkan nomor baru O(k)yang juga ada O(1). Karena O(k*g) = O(g) if k is not zero and constant.

Biarkan daftar tidak disortir. Mencari tahu apakah memasukkan nomor baru atau tidak akan memakan waktu lebih lama, tetapi penyisipannya adalah O (1).

Ini mudah. Ukuran daftar konstan, oleh karena itu waktu pengurutan daftar adalah konstan. Operasi yang dijalankan dalam waktu konstan dikatakan sebagai O (1). Oleh karena itu pengurutan daftar adalah O (1) untuk daftar ukuran tetap.

Setelah Anda melewati 100 angka, biaya maksimum yang akan Anda keluarkan untuk angka berikutnya adalah biaya untuk memeriksa apakah angka itu dalam angka 100 tertinggi (mari kita beri label CheckTime ) ditambah biaya untuk memasukkannya ke dalam set itu dan mengeluarkan terendah (sebut saja EnterTime ), yang merupakan waktu konstan (setidaknya untuk nomor yang dibatasi), atau O (1) .

Worst = CheckTime + EnterTime

Selanjutnya, jika distribusi angka adalah acak, biaya rata-rata berkurang semakin banyak angka yang Anda miliki. Misalnya, peluang Anda harus memasukkan angka ke-101 ke dalam set maksimum adalah 100/101, peluang untuk angka ke-1000 adalah 1/10, dan peluang untuk nomor ke-100 adalah 100 / n. Dengan demikian, persamaan kami untuk biaya rata-rata adalah:

Average = CheckTime + EnterTime / n

Jadi, ketika n mendekati tak terhingga, hanya CheckTime yang penting:

Average = CheckTime

Jika angka-angka terikat, CheckTime adalah konstan, dan karena itu saatnya O (1) .

Jika angka tidak terikat, waktu pemeriksaan akan bertambah dengan lebih banyak angka. Secara teoritis, ini karena jika angka terkecil dalam set maksimum mendapat cukup besar, waktu pemeriksaan Anda akan lebih besar karena Anda harus mempertimbangkan lebih banyak bit. Itu membuatnya tampak akan sedikit lebih tinggi dari waktu yang konstan. Namun, Anda juga bisa berargumen bahwa peluang bahwa angka berikutnya dalam himpunan tertinggi mendekati nol ketika n mendekati tak terhingga sehingga kemungkinan Anda perlu mempertimbangkan lebih banyak bit juga mendekati 0, yang akan menjadi argumen untuk O (1) waktu.

Saya tidak positif, tetapi nyali saya mengatakan bahwa ini saatnya O (log (log)) . Ini karena kemungkinan peningkatan angka terendah adalah logaritmik, dan peluang bahwa jumlah bit yang perlu Anda pertimbangkan untuk setiap cek adalah logaritmik juga. Saya tertarik pada orang lain mengambil ini, karena saya tidak begitu yakin ...

ini mudah jika Anda tahu Binary Heap Trees . Biner tumpukan mendukung penyisipan dalam waktu konstan rata-rata, O (1). Dan memberi Anda akses mudah ke elemen x pertama.

Jika dengan pertanyaan pewawancara benar-benar bermaksud untuk bertanya "dapatkah kita memastikan setiap nomor yang masuk diproses dalam waktu yang konstan", maka seperti yang sudah ditunjukkan oleh banyak orang (mis. Lihat jawaban @ duedl0r), solusi teman Anda sudah O (1), dan itu akan terjadi bahkan jika dia menggunakan daftar yang tidak disortir, atau menggunakan semacam gelembung, atau apa pun yang lainnya. Dalam hal ini pertanyaannya tidak masuk akal, kecuali pertanyaan yang sulit atau Anda ingat salah.

Saya menganggap pertanyaan pewawancara itu bermakna, bahwa dia tidak bertanya bagaimana membuat sesuatu menjadi O (1) yang sudah sangat jelas itu.

Karena kompleksitas algoritma pertanyaan hanya masuk akal ketika ukuran input tumbuh tanpa batas, dan satu-satunya input yang dapat tumbuh di sini adalah 100 — ukuran daftar; Saya berasumsi pertanyaan sebenarnya adalah "bisakah kita memastikan kita mendapatkan pengeluaran N Top O (1) waktu per nomor (bukan O (N) seperti dalam solusi teman Anda), apakah mungkin?".

Hal pertama yang terlintas dalam pikiran adalah menghitung sort, yang akan membeli kompleksitas O (1) waktu per angka untuk Top-N-masalah untuk harga menggunakan ruang O (m), di mana m adalah panjang rentang angka yang masuk . Jadi ya, itu mungkin.

Gunakan antrian min-prioritas yang diimplementasikan dengan tumpukan Fibonacci , yang memiliki waktu penyisipan konstan:

1. Insert first 100 elements into PQ
2. loop forever
       n = getNextNumber();
       if n > PQ.findMin() then
           PQ.deleteMin()
           PQ.insert(n)

Tugasnya jelas untuk menemukan algoritma yang O (1) dalam panjang N dari daftar angka yang diperlukan. Jadi tidak masalah jika Anda membutuhkan 100 angka teratas atau 10.000 angka, waktu penyisipan harus O (1).

Kuncinya di sini adalah bahwa meskipun persyaratan O (1) disebutkan untuk memasukkan daftar, pertanyaannya tidak mengatakan apa-apa tentang urutan waktu pencarian di seluruh ruang bilangan, tetapi ternyata ini dapat dilakukan O (1) demikian juga. Solusinya adalah sebagai berikut:

1. Atur hashtable dengan angka untuk kunci dan pasangan pointer daftar tertaut untuk nilai. Setiap pasangan pointer adalah awal dan akhir dari urutan daftar tertaut. Ini biasanya hanya akan menjadi satu elemen kemudian yang berikutnya. Setiap elemen dalam daftar tertaut berada di sebelah elemen dengan angka tertinggi berikutnya. Dengan demikian, daftar tertaut berisi urutan nomor yang disortir. Buat catatan angka terendah.

2. Ambil nomor baru x dari aliran acak.

3. Apakah lebih tinggi dari angka terendah yang terakhir dicatat? Ya => Langkah 4, Tidak => Langkah 2

4. Hit tabel hash dengan nomor yang baru saja diambil. Apakah ada entri? Ya => Langkah 5. Tidak => Ambil nomor baru x-1 dan ulangi langkah ini (ini adalah pencarian linier sederhana, tahan dengan saya di sini, ini dapat ditingkatkan dan saya akan menjelaskan caranya)

5. Dengan elemen daftar yang baru saja diperoleh dari tabel hash, masukkan nomor baru tepat setelah elemen dalam daftar tertaut (dan perbarui hash)

6. Ambil angka terendah yang saya rekam (dan hapus dari hash / daftar).

7. Hit tabel hash dengan nomor yang baru saja diambil. Apakah ada entri? Ya => Langkah 8. Tidak => Ambil nomor baru l + 1 dan ulangi langkah ini (ini adalah pencarian linear sederhana ke atas)

8. Dengan hit positif, angka tersebut menjadi angka terendah baru. Lanjutkan ke langkah 2

Untuk memungkinkan nilai duplikat, hash sebenarnya perlu mempertahankan awal dan akhir dari urutan daftar elemen yang duplikat. Menambah atau menghapus elemen pada kunci yang diberikan dengan demikian menambah atau mengurangi rentang yang ditunjuk.

Sisipan di sini adalah O (1). Pencarian yang disebutkan adalah, saya kira sesuatu seperti, O (perbedaan rata-rata antara angka). Perbedaan rata-rata meningkat dengan ukuran ruang angka, tetapi berkurang dengan panjang yang diperlukan dari daftar angka.

Jadi strategi pencarian linier sangat buruk, jika jumlah ruang besar (misalnya untuk tipe int 4 byte, 0 hingga 2 ^ 32-1) dan N = 100. Untuk mengatasi masalah kinerja ini, Anda dapat menyimpan kumpulan hashtable paralel, di mana angkanya dibulatkan ke besaran yang lebih tinggi (mis. 1s, 10s, 100s, 1000s) untuk membuat kunci yang sesuai. Dengan cara ini Anda dapat meningkatkan dan menurunkan gigi untuk melakukan pencarian yang dibutuhkan dengan lebih cepat. Kinerja kemudian menjadi O (log numberrange), saya pikir, yang konstan, yaitu O (1) juga.

Untuk memperjelas ini, bayangkan Anda memiliki nomor 197. Anda menekan hash table 10s, dengan '190', itu dibulatkan ke sepuluh terdekat. Apa pun? Tidak. Jadi Anda turun dalam 10-an sampai Anda menekan katakan 120. Kemudian Anda bisa mulai pada 129 dalam hashtable 1s, kemudian coba 128, 127 sampai Anda menekan sesuatu. Anda sekarang telah menemukan di mana dalam daftar tertaut untuk memasukkan nomor 197. Sementara memasukkannya, Anda juga harus memperbarui hashtable 1s dengan entri 197, hass 10s dengan angka 190, 100s dengan 100, dll. Langkah-langkah terbanyak Yang harus Anda lakukan di sini adalah 10 kali log dari kisaran angka.

Saya mungkin salah mengerti, tetapi karena ini adalah pertukaran programmer, dan konteksnya adalah wawancara, saya berharap jawaban di atas adalah jawaban yang cukup meyakinkan untuk situasi itu.

EDIT Saya menambahkan beberapa detail tambahan di sini untuk menjelaskan skema hashtable paralel dan bagaimana artinya pencarian linear yang buruk yang saya sebutkan dapat diganti dengan pencarian O (1). Saya juga menyadari bahwa tentu saja tidak perlu mencari angka terendah berikutnya, karena Anda dapat langsung menuju ke sana dengan melihat hashtable dengan angka terendah dan maju ke elemen berikutnya.

Bisakah kita berasumsi bahwa angka-angka dari tipe data tetap, seperti Integer? Jika demikian, maka simpan penghitungan dari setiap nomor yang ditambahkan. Ini adalah operasi O (1).

1. Deklarasikan array dengan elemen sebanyak-banyaknya karena ada angka yang memungkinkan:
2. Baca setiap nomor saat streaming.
3. Tally jumlahnya. Abaikan saja jika angka itu sudah dihitung 100 kali karena Anda tidak akan pernah membutuhkannya. Ini mencegah luapan dari penghitungan jumlah yang tak terbatas.
4. Ulangi dari langkah 2.

VB.Net code:

Const Capacity As Integer = 100

Dim Tally(Integer.MaxValue) As Integer ' Assume all elements = 0
Do
    Value = ReadValue()
    If Tally(Value) < Capacity Then Tally(Value) += 1
Loop

Ketika Anda mengembalikan daftar, Anda dapat mengambil selama yang Anda suka. Cukup beralih dari akhir daftar dan buat daftar baru dari 100 nilai tertinggi yang direkam. Ini adalah operasi O (n), tapi itu tidak relevan.

Dim List(Capacity) As Integer
Dim ListCount As Integer = 0
Dim Value As Integer = Tally.Length - 1
Dim ValueCount As Integer = 0
Do Until ListCount = List.Length OrElse Value < 0
    If Tally(Value) > ValueCount Then
        List(ListCount) = Value
        ValueCount += 1
        ListCount += 1
    Else
        Value -= 1
        ValueCount = 0
    End If
Loop
Return List

Sunting: Sebenarnya, tidak masalah apakah itu tipe data tetap. Karena tidak ada batasan pada konsumsi memori (atau hard disk), Anda dapat membuatnya bekerja untuk berbagai bilangan bulat positif.

Seratus angka mudah disimpan dalam sebuah array, ukuran 100. Pohon apa pun, daftar atau set berlebihan, diberi tugas.

Jika nomor yang masuk lebih tinggi dari yang terendah (= terakhir) dalam array, lewati semua entri. Setelah Anda menemukan yang pertama lebih kecil dari nomor baru Anda (Anda dapat menggunakan pencarian mewah untuk melakukan itu), jalankan melalui sisa array, mendorong setiap entri "turun" oleh satu.

Karena Anda menjaga daftar diurutkan dari awal, Anda tidak perlu menjalankan algoritma pengurutan sama sekali. Ini O (1).

Anda bisa menggunakan Binary Max-Heap. Anda harus melacak pointer ke simpul minimum (yang bisa tidak diketahui / null).

Anda mulai dengan memasukkan 100 angka pertama ke dalam tumpukan. Maks akan berada di atas. Setelah ini selesai, Anda akan selalu menyimpan 100 angka di sana.

Lalu ketika Anda mendapatkan nomor baru:

if(minimumNode == null)
{
    minimumNode = findMinimumNode();
}
if(newNumber > minimumNode.Value)
{
    heap.Remove(minimumNode);
    minimumNode = null;
    heap.Insert(newNumber);
}

Sayangnya findMinimumNodeO (n), dan Anda dikenakan biaya satu kali per sisipan (tetapi tidak selama sisipan :). Menghapus simpul minimum dan memasukkan simpul baru, rata-rata, O (1) karena mereka cenderung menuju bagian bawah tumpukan.

Sebaliknya dengan Binary Min-Heap, min berada di atas, yang bagus untuk menemukan min untuk perbandingan, tetapi menyebalkan ketika Anda harus mengganti minimum dengan angka baru yang> min. Itu karena Anda harus menghapus min node (selalu O (logN)) dan kemudian memasukkan simpul baru (rata-rata O (1)). Jadi, Anda masih memiliki O (logN) yang lebih baik daripada Max-Heap, tetapi tidak O (1).

Tentu saja, jika N konstan, maka Anda selalu memiliki O (1). :)