Seberapa pentingkah bagi seorang programmer untuk mengetahui cara mengimplementasikan algoritma QuickSort / MergeSort dari memori? [Tutup]

Saya sedang meninjau catatan saya dan menemukan implementasi algoritma penyortiran yang berbeda.

Ketika saya berusaha memahami implementasi QuickSort dan MergeSort, terlintas dalam benak saya bahwa walaupun saya melakukan pemrograman untuk mencari nafkah dan menganggap diri saya layak pada apa yang saya lakukan, saya tidak memiliki memori fotografis atau kemampuan otak semata untuk mengimplementasikan algoritme tersebut tanpa mengandalkan catatan saya. Yang saya ingat adalah bahwa beberapa algoritma itu stabil dan ada yang tidak. Beberapa mengambil O (nlog (n)) atau O (n ^ 2) waktu untuk menyelesaikan. Beberapa menggunakan lebih banyak memori daripada yang lain ...

Saya merasa tidak layak mendapatkan pekerjaan semacam ini jika bukan karena posisi saya tidak mengharuskan saya menggunakan algoritma penyortiran apa pun selain yang ditemukan di API standar. Maksud saya, berapa banyak dari Anda yang memiliki posisi pemrograman di mana sebenarnya penting agar Anda dapat mengingat atau membuat hal-hal seperti ini sendiri?

Mari kita tanyakan pada Albert dan lihat apa yang dia katakan tentang masalah ini:

"Aku tidak perlu tahu segalanya, aku hanya perlu tahu di mana menemukannya, ketika aku membutuhkannya"

- Albert Einstein , diparafrasekan

Amin, Bruder Albert, Amin.

Setelah Anda membuat survei yang baik tentang algoritma penting dalam disiplin ilmu tertentu (sort, pencarian, apa pun), Anda kemudian bisa melupakan detail implementasi sampai Anda benar-benar membutuhkan algo, dalam hal ini Anda mencari atau menggunakan Lib yang sudah ada. 25 tahun yang lalu saya membangun sistem pencarian utama menggunakan B * -trees, tapi hari ini saya perlu RTFM untuk menggunakannya dengan baik.

1. Ini bukan masalah menghafal. Ini masalah pemahaman mendalam tentang kelas umum dari algoritma seperti membagi dan menaklukkan. Jika Anda benar-benar memahami memecah belah dan menaklukkan, maka Anda tidak perlu menghafal quicksort. Anda dapat memperolehnya kembali di tempat sesuai kebutuhan. Selain itu, hasil nyata bahkan tidak mampu mendapatkan kembali quicksort sendiri, itu adalah bahwa Anda dapat mengenali kapan masalah baru dapat diterima untuk solusi pemecahan dan menaklukkan.

2. Tidak semua pekerjaan pemrograman sama. Beberapa pekerjaan memerlukan pengetahuan mendalam tentang algoritma, beberapa membutuhkan orang-orang yang memahami teori tipe, dan beberapa hanya membutuhkan orang-orang yang dapat mengikis data dari formulir web dan memindahkannya ke database. Beberapa pekerjaan bahkan membutuhkan semua keterampilan itu sekaligus. Pekerjaan seperti apa yang Anda inginkan?

Saya pikir satu-satunya waktu Anda perlu mengingat semuanya adalah ketika melamar pekerjaan ketika Anda harus datang dengan jawaban di tempat dan tidak memiliki sumber daya luar.

Saya telah meminta rekan kerja untuk menulis ulang quicksort dan yang lainnya, tetapi saya terus mengatakan kepada mereka untuk kembali menggunakan fungsi penyortiran bawaan yang ada dalam bahasa tersebut. Saya tahu bahwa tergantung pada jenis proyek yang kami kerjakan kami harus mengingat algoritma lain karena biasanya tidak termasuk dalam pustaka standar, tetapi pengurutan bukan salah satu yang muncul karena biasanya dibangun ke dalam bahasa.

Ketika kita perlu mengingat algoritma tersebut, kita biasanya beralih ke google atau buku, dan biasanya itu tidak mencari implementasi spesifik, tetapi apa yang akan menjadi implementasi terbaik untuk masalah kita.

Hanya dengan mengingat algoritma mana yang berguna dalam skenario apa, akan lebih dari cukup untuk membantu selama pekerjaan Anda. Pada kenyataannya, sebagian besar pekerjaan pemrograman tidak memerlukan penghafalan pendekatan, melainkan mereka tertarik pada cara Anda mengenali pola algoritmik ketika dihadapkan dengan masalah .

Faktanya, ada banyak informasi di kebanyakan blog pemrograman / artikel tentang topik algoritma. Dengan demikian, menghafal implementasi yang tepat tidak mementingkan. Sebagian besar informasi berharga akan mendapatkan ide dasar tentang jenis algoritma apa yang tersedia, dan masalah spesifik apa yang mereka pecahkan . Mencari implementasi yang tepat setelah Anda tahu apa yang Anda cari cukup cepat.

Singkatnya, selalu lebih baik untuk mengetahui apa yang Anda cari dan di mana referensi - yang akan memandu Anda ke sumbernya.

Implementasi yang tepat tidak terlalu penting. Tetapi prinsip di balik mergesort / quicksort - rekursi, partisi dll, sangat mendasar dan setiap programmer harus mengerti. Algoritma ini sebenarnya sangat sederhana untuk digambarkan dalam kata-kata begitu Anda mengerti.

Ini sebenarnya bukan masalah apakah Anda dapat mencarinya atau apakah Anda dapat google, melainkan apakah programmer memahami teknik pemecahan masalah ini dan dapat diterapkan pada situasi lain.

Saya dari dua pikiran tentang hal ini. Saya tahu banyak programmer yang tidak tahu apa itu algoritma pengurutan, tetapi melakukan pekerjaan mereka dengan cukup baik. Saya juga percaya pada prinsip-prinsip memahami agar benar-benar memahami domain.

Sulit bagi saya untuk memiliki jawaban yang tidak bias tentang hal ini karena saya telah memprogram begitu lama sehingga saya mungkin lupa lebih banyak algoritma yang saya tahu saat ini - tetapi saya masih tahu yang menyortir yang disebutkan dalam pertanyaan ini. Saya pikir para pemimpin pemikiran di Agile (misalnya Ron Jeffries, Alistair Cockburn) memiliki beberapa ide bagus di dekat ide ini (misalnya Shu-Ha-Ri).

Singkatnya untuk jawaban bertele-tele ini: Pasti menggunakan API (NIH adalah tanda ketidakdewasaan pengembang), tetapi selalu memahami prinsip-prinsip yang mendasarinya. Saya harap ini membantu.

Penyortiran dan pencarian sangat penting, baik Anda penggemar Donald Knuth atau ingin menjadi Larry Page berikutnya. Bergantung pada bisnis tempat Anda berada, dan tingkat persaingan yang dapat Anda perintahkan di antara kandidat Anda, saya akan merekomendasikan agar Anda memasukkan beberapa konsep berikut dalam wawancara.

Penyortiran

• Sketsa semacam algoritma penyortiran.
• Daftar beberapa contoh algoritma pengurutan.
• Bandingkan / kontraskan dua macam dengan karakteristik kinerja yang berbeda.
• Jika mereka tidak menyebutkan penggunaan memori, tanyakan hal itu.

Mencari

• Beri nama sebanyak mungkin algoritma pencarian.
• Bandingkan / kontraskan dua algoritma pencarian.
• Buat sketsa pencarian apa pun selain pencarian linear.

Beberapa orang mungkin mengatakan bahwa memerlukan kode untuk algoritma ini berlebihan kecuali pekerjaan itu di pulau sepi tanpa koneksi internet. Pertimbangan lain adalah bahwa jika Anda punya waktu 30 menit, dan Anda ingin bertanya tentang hal lain, bagi banyak kandidat, menerapkan semacam itu bisa memakan banyak waktu Anda.