Bagian algoritmik dengan kode penulisan di papan tulis atau kertas adalah salah satu tahap terpenting dari wawancara kerja bagi pengembang untuk mendapatkan pekerjaan di Yandex. Kami memutuskan untuk berbicara lebih terinci tentang bagaimana bagian-bagian ini disusun untuk membantu calon yang akan datang dalam persiapan. Selain itu, saya berharap bahwa banyak dari mereka yang tidak berani datang ke Yandex untuk wawancara, takut ujian terlalu sulit, setelah cerita ini akan mengerti bahwa pada kenyataannya semuanya tidak begitu menakutkan!
Jadi kami telah menyiapkan bahan-bahan berikut untuk Anda:
- Kontes khusus yang berisi tugas-tugas yang mirip dengan yang kami berikan untuk wawancara.
- Posting ini Ini menjelaskan mengapa Anda perlu melakukan bagian tersebut, serta memahami semua tugas kontes.
- Dua video di mana tugas dari kontes diurutkan: di pertama - tugas lebih mudah, di kedua - dua tugas lebih sulit. Dari video ini Anda akan belajar tentang kesalahan khas yang dibuat ketika melewati bagian algoritmik, dan saat menulis kode produksi.
Bagaimana kami mewawancarai pengembang
Wawancara dengan pengembang apa pun terdiri dari beberapa tahap:
- bagian awal dengan perekrut;
- wawancara skype teknis;
- beberapa bagian penuh waktu;
- wawancara terakhir dengan manajer perekrutan.
Pada bagian awal, perekrut berkenalan dengan kandidat, mempelajari minat dan motifnya untuk memahami posisi apa yang masuk akal untuk mempertimbangkannya. Wawancara skype teknis dimaksudkan untuk penilaian awal keterampilan kandidat dan menghilangkan mereka yang pasti tidak akan mampu mengatasi bagian penuh waktu.
Bagian penuh waktu - panggung utama. Bagian penuh-waktu itulah yang memberikan jawaban atas pertanyaan apa yang bisa dilakukan seorang kandidat. Bagian algoritma adalah salah satu bagian teknis penuh waktu. Selain algoritmik, ada tes tatap muka lainnya: misalnya, calon pengembang senior harus melalui bagian arsitektur, dan pemimpin masa depan juga akan menjawab pertanyaan tentang mengelola tim dan proyek. Secara umum, jika seorang kandidat memiliki kekuatan di bidang tertentu (pembelajaran mesin, optimasi tingkat rendah, pengembangan sistem yang sangat sarat muatan, pengembangan ponsel, atau lainnya), kami akan mengatur bagian dengan spesialis khusus.
Bagian algoritmik memeriksa apakah kandidat dapat menemukan algoritme untuk menyelesaikan masalah sederhana, mengevaluasi kompleksitas algoritme ini dan mengimplementasikannya tanpa kesalahan, sambil menjaga keseimbangan antara kualitas pengujian dan kecepatan solusi.
Mengapa menulis kode di papan tulis atau kertas
Keadaan alami bagi seorang programmer adalah pemrograman dalam lingkungan pengembangan terintegrasi dengan penyorotan sintaksis dan ketertelusuran. Oleh karena itu, ide saat wawancara untuk menulis kode di papan tulis atau kertas pada awalnya sepertinya tidak terlalu alami. Namun, metode ini memungkinkan Anda untuk memeriksa dua properti yang sangat penting untuk setiap pengembang.
Yang pertama dari mereka adalah kemampuan untuk dengan cepat menangani kinerja kode "oleh mata". Bayangkan ketika menulis setiap siklus yang muncul dalam program, pengembang perlu meluangkan waktu untuk memverifikasi kinerjanya dengan melacak; atau bahwa ketika layanan macet dalam produksi, ia selalu perlu menjalankan kode di bawah debugger. Jelas bahwa menulis dan men-debug bahkan program sederhana akan memakan waktu lama baginya. Tentu saja, berguna untuk dapat membaca kode dengan ulasan kode.
Properti penting kedua adalah kemampuan untuk memikirkan rencana solusi terlebih dahulu dan kemudian mengikutinya. Jika tidak ada rencana, ini akan menyebabkan sejumlah besar koreksi, dicoret (di atas kertas) dan penulisan ulang potongan kode besar. Dalam kehidupan nyata, semua ini sangat memperlambat pengembangan, tetapi sebagian tertutupi oleh kecepatan kerja dalam editor kode. Papan dan kertas dalam hal ini adalah permukaan tanpa ampun.
Secara alami, kami memperhitungkan bahwa menulis kode dengan tangan tidak terlalu cepat. Oleh karena itu, tugas kami biasanya melibatkan penyelesaian tidak lebih dari selusin baris, dan jumlah tugas yang perlu diselesaikan dalam satu bagian biasanya dua atau tiga.
Bagian algoritmik dan pemrograman olahraga
Pemrograman olahraga berkembang di pengembang masa depan, antara lain, dan kemampuan untuk dengan cepat dan tanpa kesalahan menerapkan algoritma sederhana sesuai dengan rencana yang telah ditentukan. Oleh karena itu, kandidat dengan pengalaman dalam pemrograman olahraga, sungguh, melakukan pekerjaan dengan baik dengan bagian algoritmik dalam wawancara. Seringkali Anda dapat mengamati situasi di mana peserta yang akan datang dapat dengan mudah mengatasi bagian algoritmik, menyelesaikan semua masalah dalam 15-20 menit, sementara programmer yang lebih berpengalaman menghabiskan seluruh jam pada tugas yang sama.
Pada saat yang sama, bagian algoritmik dengan kode penulisan hanyalah salah satu bagian yang menguji keterampilan minimum yang diperlukan untuk setiap pengembang. Bagian ini akan ditangani tidak hanya oleh programmer Olimpiade, tetapi juga oleh pengembang industri yang berpengalaman. Pengembang senior atau pemimpin tim di masa depan pasti sedang menunggu bagian arsitektur, di mana ia akan dapat mengungkapkan kekuatannya; Tentu saja, bagian ini tidak pernah diberikan kepada trainee dan pengembang junior.
Kontes Persiapan Wawancara
Terutama agar Anda dapat membayangkan kira-kira isi tugas yang kami berikan di bagian algoritmik, kami telah mengumpulkan kontes yang dapat digunakan sebagai persiapan untuk wawancara. Cobalah untuk menyelesaikan semua masalah tanpa menjalankan debugger sekali; menulis solusi di Notepad tanpa penyorotan sintaksis; datang dengan solusi sesingkat mungkin yang akan lulus semua tes; pikirkan semua masalah yang mungkin terjadi terlebih dahulu dan lewati solusinya pertama kali.
Kontes berisi lima tugas. Anda dapat mencoba menyelesaikannya sendiri, atau Anda dapat membaca analisisnya terlebih dahulu: itu akan tetap berguna, karena Anda akan dapat melatih keterampilan Anda coding bebas kesalahan dari algoritma yang dikenal sebelumnya.
Analisis tugas kontesTugas A. Batu dan perhiasan
Dua baris karakter Latin kecil diberikan: string J dan string S. Karakter yang termasuk dalam string J adalah "perhiasan" dan termasuk dalam string S adalah "batu". Perlu untuk menentukan berapa banyak karakter dari S yang secara bersamaan "permata". Sederhananya, Anda perlu memeriksa berapa banyak karakter dari S dalam J.
Ini adalah tugas pemanasan yang sangat sederhana, yang mencakup solusi dalam beberapa bahasa pemrograman, sehingga peserta dapat terbiasa dengan sistem pengujian.
Algoritma ini cukup sederhana: Anda perlu membangun satu set dari sebuah baris dengan "perhiasan", kemudian pergi sepanjang garis dengan "batu" dan periksa setiap karakter untuk dimasukkan dalam set ini. Gunakan implementasi himpunan tersebut untuk menjamin kompleksitas linear dari solusi yang dihasilkan, terlepas dari kenyataan bahwa jalur input sangat pendek dan oleh karena itu dimungkinkan untuk melewati bahkan algoritma kuadratik dalam kompleksitas.
Masalah B. Unit yang berurutan
Diperlukan untuk menemukan urutan unit terpanjang dalam vektor biner dan mencetak panjangnya.
Algoritma solusinya adalah sebagai berikut: berjalan melalui semua elemen array; ketika Anda bertemu satu, Anda perlu menambah penghitung untuk panjang urutan saat ini, dan ketika Anda bertemu nol, Anda perlu mengatur ulang penghitung ini. Pada akhirnya, Anda harus menampilkan nilai maksimum yang diambil penghitung.
Periksa apakah Anda menangani situasi ketika array berakhir dengan urutan unit yang diinginkan. Dengan implementasi yang cermat, situasi ini tidak memerlukan pemrosesan khusus.
Coba gunakan hanya jumlah memori tambahan yang konstan.
Tugas C. Penghapusan Duplikat
Array bilangan bulat 32-bit yang dipesan dalam urutan yang tidak menurun diberikan. Diperlukan untuk menghapus semua pengulangan dari itu.
Algoritma yang benar secara berurutan memproses elemen-elemen array, membandingkannya dengan output terakhir. Anda harus ingat untuk memperbarui variabel yang mengandung elemen terakhir yang ditampilkan dan, selain itu, tidak membuat kesalahan saat memproses elemen terakhir.
Saat memecahkan masalah ini, Anda juga tidak perlu menggunakan memori tambahan.
Tugas D. Menghasilkan urutan braket
Diberi bilangan bulat . Diperlukan untuk mencetak semua urutan panjang braket yang benar dipesan secara leksikografis (lihat https://ru.wikipedia.org/wiki/Lexographic_order ). Hanya tanda kurung yang digunakan dalam tugas.
Ini adalah contoh masalah algoritmik yang relatif kompleks. Kami akan menghasilkan urutan satu karakter; pada setiap saat, kita dapat menetapkan braket pembuka atau braket penutup untuk urutan saat ini. Anda dapat menambahkan braket pembuka jika kurang dari n braket pembuka telah ditambahkan sebelumnya, dan braket penutup jika dalam urutan saat ini jumlah braket pembuka melebihi jumlah braket penutup. Algoritme seperti itu, dengan implementasi yang cermat, secara otomatis menjamin urutan leksikografis dalam jawabannya; bekerja dalam waktu yang sebanding dengan produk dari jumlah elemen dalam respons terhadap n; ini membutuhkan jumlah memori tambahan linier.
Contoh dari algoritma yang tidak efektif adalah sebagai berikut: kami menghasilkan semua urutan braket yang mungkin, dan kemudian kami hanya menampilkan yang ternyata benar. Pada saat yang sama, volume jawaban tidak akan memungkinkan penyelesaian masalah lebih cepat daripada algoritma yang akan dihasilkan di atas.
Masalah E. Anagram
Tugas yang agak sederhana ini adalah contoh khas dari masalah, untuk solusi yang perlu untuk menggunakan array asosiatif. Saat memutuskan, Anda perlu mempertimbangkan bahwa karakter dapat diulang, jadi Anda harus menggunakan bukan set, tetapi kamus. Oleh karena itu, solusinya adalah sebagai berikut: kami menyusun dari setiap baris sebuah kamus, yang untuk setiap karakter akan menyimpan jumlah pengulangannya; lalu bandingkan kamus yang dihasilkan. Jika mereka bertepatan, perlu untuk mencetak unit, jika tidak - nol.
Solusi alternatif: mengurutkan jalur input, dan kemudian membandingkannya. Solusi ini lebih buruk karena berjalan lebih lambat dan juga mengubah input. Tetapi solusi ini tidak menggunakan memori tambahan.
Jika selama wawancara Anda memiliki beberapa solusi yang berbeda dalam karakteristiknya, beri tahu kami. Itu selalu bagus ketika pengembang tahu beberapa opsi untuk memecahkan masalah dan dapat berbicara tentang kekuatan dan kelemahan mereka.
Tugas F. Gabung daftar diurutkan
Diberikan array bilangan bulat non-negatif yang diurutkan dalam urutan non-menurun, yang masing-masing tidak melebihi 100. Diperlukan untuk menyusun hasil merger mereka: sebuah array yang diurutkan dalam urutan non-menurun yang berisi semua elemen asli array. Panjang setiap larik tidak melebihi .
Untuk setiap array, buat pointer; awalnya, masing-masing pointer terletak di awal array yang sesuai. Kami akan menempatkan elemen yang sesuai dengan posisi pointer dalam struktur data apa pun yang mendukung ekstraksi minimum - bisa berupa multiset atau, misalnya, heap. Selanjutnya, kita akan mengekstrak elemen minimum dari struktur ini, menanggapinya, menggeser posisi pointer dalam array yang sesuai dan menempatkan elemen berikutnya dari array ini dalam struktur data.
Dalam tugas ini, banyak mengalami kesulitan dengan format input. Harap dicatat bahwa elemen pertama dari garis tidak menggambarkan elemen array, mereka menggambarkan panjang array!
FAQ Kontes
A: Saya pasti menulis kode yang benar, tetapi tes gagal; mungkin ada kesalahan di dalamnya?
T: Tidak, semua tes sudah benar. Pikirkan: Anda mungkin tidak melihat adanya situasi yang tidak biasa.
A: Saya menulis dalam X, itu pasti membutuhkan lebih banyak memori dalam tugas Y. Naikkan batas!
T: Semua batas ditetapkan sedemikian rupa sehingga solusi dimungkinkan menggunakan bahasa apa pun yang tersedia. Coba periksa apakah Anda secara tidak sengaja membaca seluruh file input dalam tugas dengan batas memori yang ketat.
A: Beberapa tugas dapat diselesaikan lebih mudah karena keterbatasan yang ditunjukkan. Kenapa kamu melakukan ini?
T: Kami secara khusus menyederhanakan input dalam beberapa tugas, sehingga akan lebih mudah bagi peserta untuk fokus pada implementasi algoritma dan tidak berpikir, misalnya, tentang kecepatan mengunduh data atau beberapa hal lain yang penting dalam pemrograman olahraga. Cobalah untuk mengimplementasikan algoritma yang kami sarankan - hanya dalam situasi ini Anda akan mendapatkan manfaat maksimal dari kontes.
A: Saya tidak ingin lulus kontes. Tidak bisakah aku
T: Tentu saja! Kontes ini tidak mengikat semua kandidat. Namun, saya masih merekomendasikan untuk menyelesaikannya: ini akan berguna dalam hal apa pun.
A: Apa lagi yang akan Anda rekomendasikan untuk persiapan?
T: Baca kiat kami di halaman resmi tentang wawancara di Yandex: https://yandex.ru/jobs/ya-interview . Saya akan menambahkan sendiri bahwa menyelesaikan masalah di leetcode.com sangat berguna untuk pengembang yang berlatih, terlepas dari apakah ia berencana untuk menjalani wawancara dalam waktu dekat atau berpartisipasi dalam kompetisi pemrograman. Bahkan sedikit latihan memungkinkan Anda merasa lebih percaya diri saat menyelesaikan tugas pekerjaan.
Kesimpulan
Saya sering menghadiri konferensi untuk pengembang dan manajer pengembangan, saya adalah anggota dari banyak obrolan pengembangan, telah melakukan beberapa ratus wawancara dan menyewa sejumlah besar pengembang di Yandex. Pengalaman menunjukkan bahwa bagian algoritmik dengan kode tulisan di papan tulis atau kertas sering menimbulkan pertanyaan. Kesimpulannya, saya akan menjawab yang paling populer di antara mereka.
Mengapa wawancara dalam kondisi yang sangat berbeda dari kondisi kerja pengembang yang sebenarnya?
Ini memungkinkan Anda untuk memahami apakah kandidat dapat menemukan masalah dalam program tanpa memulai debugger; apakah dia dapat membuat rencana algoritma terlebih dahulu dan kemudian secara akurat mengikutinya; dapatkah dia menghasilkan serangkaian tes yang kecil tetapi cukup dan kemudian memeriksa implementasinya terhadap serangkaian tes ini.
Apakah bagian seperti itu memberikan keuntungan yang tidak adil bagi programmer olahraga?
Pemrograman olahraga mengembangkan beberapa keterampilan yang sangat berguna dalam pengembang, sehingga peserta dalam pemrograman olimpiade benar-benar berhasil di bagian algoritmik. Jadi ada keuntungan, tapi itu adil. Bagian algoritmik hanya satu dari banyak, sehingga setiap kandidat akan memiliki cukup kesempatan untuk menunjukkan kekuatannya!
Mengapa melakukan bagian algoritmik jika semua algoritme telah diterapkan untuk waktu yang lama, dan Anda hanya perlu dapat mencari implementasinya di perpustakaan yang sudah jadi?
Pada bagian algoritmik yang umum untuk semua pengembang, kami hanya menguji keterampilan minimum yang diperlukan: kemampuan untuk menghasilkan dan tanpa kesalahan untuk mengimplementasikan algoritma sederhana yang berisi loop, memeriksa kondisi, dan mungkin membutuhkan penggunaan array asosiatif. Jenis kode ini secara konstan ditulis untuk mengimplementasikan layanan pengguna.
Apa gunanya bagian yang tidak menguji banyak keterampilan pengembang?
Bagian algoritmik, memang, hanya memeriksa serangkaian keterampilan minimum yang diperlukan untuk pengembang apa pun. Kami menguji keterampilan lain dengan bantuan bagian lain.
Apakah Anda melakukan bagian algoritmik untuk pengembang semua spesialisasi?
Ya Bagian algoritmik diadakan untuk pengembang backend, analis, pengembang mobile dan front-end, pengembang infrastruktur dan metode pembelajaran mesin, dan sebagainya.