[Powered by Google Translate] [Seminar: Wawancara Teknis]
[Kenny Yu, Universitas Harvard]
[Ini adalah CS50.] [CS50.TV]
Hi semuanya, aku Kenny. Saat ini saya belajar ilmu komputer junior.
Aku CS mantan TF, dan aku berharap aku punya ini ketika saya masih seorang underclassman,
dan itulah sebabnya aku memberi seminar ini.
Jadi saya harap Anda menikmatinya.
Seminar ini adalah tentang wawancara teknis,
dan semua sumber daya yang saya dapat ditemukan di link ini,
link ini di sini, beberapa sumber daya.
Jadi saya membuat daftar masalah, sebenarnya, cukup beberapa masalah.
Juga seorang jenderal sumber halaman di mana kita dapat menemukan tips
tentang bagaimana mempersiapkan untuk wawancara,
tips tentang apa yang harus Anda lakukan selama wawancara yang sebenarnya,
serta bagaimana pendekatan masalah dan sumber daya untuk referensi di masa mendatang.
Ini semua secara online.
Dan hanya untuk Pendahuluan ini seminar, disclaimer,
seperti ini tidak seharusnya - persiapan wawancara Anda
seharusnya tidak terbatas pada daftar ini.
Ini hanya dimaksudkan untuk menjadi panduan,
dan Anda pasti harus mengambil semua yang saya katakan dengan sebutir garam,
tetapi juga menggunakan segala sesuatu yang saya digunakan untuk membantu Anda dalam persiapan wawancara Anda.
>> Aku akan mempercepat melalui beberapa slide berikutnya
sehingga kami bisa sampai ke studi kasus aktual.
Struktur wawancara untuk posisi yang rekayasa perangkat lunak,
biasanya itu adalah 30 sampai 45 menit,
beberapa putaran, tergantung pada perusahaan.
Sering kali Anda akan coding di papan putih.
Jadi papan putih seperti ini, tetapi sering pada skala yang lebih kecil.
Jika Anda memiliki sebuah wawancara telepon, Anda mungkin akan menggunakan
baik collabedit atau Doc Google sehingga mereka dapat melihat Anda hidup coding
saat Anda sedang diwawancarai melalui telepon.
Wawancara itu sendiri biasanya 2 atau 3 masalah
menguji pengetahuan ilmu komputer Anda.
Dan itu akan hampir pasti melibatkan coding.
Jenis-jenis pertanyaan yang Anda akan melihat biasanya struktur data dan algoritma.
Dan dalam melakukan jenis-jenis masalah,
mereka akan meminta Anda, seperti, apa waktu dan kompleksitas ruang, big O?
Seringkali mereka juga meminta pertanyaan tingkat yang lebih tinggi,
sehingga, merancang sistem,
bagaimana Anda lay out kode Anda?
Apa interface, apa kelas, apa modul yang Anda miliki di sistem anda,
dan bagaimana ini berinteraksi bersama-sama?
Jadi struktur data dan algoritma serta merancang sistem.
>> Beberapa tips umum sebelum kita menyelam ke studi kasus kami.
Saya pikir aturan yang paling penting adalah selalu berpikir keras.
Wawancara ini seharusnya menjadi kesempatan Anda untuk pamer proses berpikir Anda.
Titik wawancara adalah untuk pewawancara untuk mengukur
bagaimana Anda berpikir dan bagaimana Anda melewati masalah.
Hal terburuk yang dapat Anda lakukan adalah diam sepanjang wawancara keseluruhan.
Itu hanya tidak baik.
Bila Anda diberi pertanyaan, Anda juga ingin memastikan bahwa Anda memahami pertanyaan.
Jadi ulangi pertanyaan kembali kata-kata sendiri
dan berusaha untuk bekerja menyeluruh beberapa kasus tes sederhana
untuk memastikan bahwa Anda memahami pertanyaan.
Bekerja melalui uji kasus beberapa juga akan memberikan intuisi tentang bagaimana untuk memecahkan masalah ini.
Anda bahkan mungkin menemukan beberapa pola untuk membantu Anda memecahkan masalah.
Tip besar mereka adalah untuk tidak frustrasi.
Jangan frustrasi.
Wawancara yang menantang, tapi hal terburuk yang dapat Anda lakukan,
selain menjadi diam, yang akan tampak frustrasi.
Anda tidak ingin memberikan kesan bahwa untuk pewawancara.
Satu hal yang Anda - jadi, banyak orang, ketika mereka pergi ke sebuah wawancara,
mereka berusaha untuk mencoba untuk menemukan solusi terbaik pertama,
ketika benar-benar, biasanya ada solusi mencolok.
Mungkin lambat, mungkin tidak efisien, tetapi Anda hanya harus menyatakan hal itu,
hanya sehingga Anda memiliki titik awal dari mana untuk bekerja lebih baik.
Juga, menunjukkan solusinya adalah lambat, dalam hal
big O kompleksitas waktu atau kompleksitas ruang,
akan menunjukkan kepada pewawancara bahwa Anda memahami
isu-isu saat menulis kode.
Jadi jangan takut untuk datang dengan algoritma sederhana pertama
dan kemudian bekerja lebih baik dari sana.
Ada pertanyaan sejauh ini? Oke.
>> Jadi mari kita menyelam ke masalah pertama kami.
"Mengingat sebuah array bilangan bulat n, menulis fungsi yang mengocok array
di tempat sehingga semua permutasi dari bilangan bulat n kemungkinan yang sama. "
Dan menganggap Anda telah tersedia generator integer acak
yang menghasilkan integer dalam jangkauan dari 0 sampai i, jangkauan setengah.
Apakah semua orang mengerti pertanyaan ini?
Saya memberi Anda sebuah array bilangan bulat n, dan aku ingin kau shuffle itu.
Dalam direktori saya, saya menulis beberapa program untuk menunjukkan apa yang saya maksud.
Aku akan mengocok sebuah array dari 20 elemen,
dari -10 sampai +9,
dan saya ingin Anda untuk menampilkan daftar seperti ini.
Jadi ini adalah array input diurutkan saya, dan saya ingin Anda untuk mengocok itu.
Kita akan melakukannya lagi.
Apakah setiap orang memahami pertanyaan? Oke.
Jadi terserah Anda.
Apa adalah beberapa ide? Dapatkah Anda melakukannya sebagai n, ^ 2 n log n, n?
Terbuka untuk saran.
Oke. Jadi satu ide, disarankan oleh Emmy,
adalah pertama menghitung nomor acak, integer acak, dalam rentang dari 0 sampai 20.
Jadi berasumsi array kita memiliki panjang 20.
Dalam diagram kita dari 20 elemen,
ini adalah array masukan kami.
Dan sekarang, saran nya adalah untuk membuat array baru,
jadi ini akan menjadi output array.
Dan berdasarkan pada saya dikembalikan oleh rand -
jadi jika saya adalah, katakanlah, 17,
menyalin elemen ke-17 ke posisi pertama.
Sekarang kita perlu menghapus - kita perlu menggeser semua elemen di sini
lebih sehingga kita memiliki celah di akhir dan tidak ada lubang di tengah.
Dan sekarang kita ulangi proses.
Sekarang kita memilih integer acak baru antara 0 dan 19.
Kami memiliki i baru di sini, dan kami salin elemen ini dalam posisi ini.
Kemudian kita menggeser item lebih dan kami ulangi proses sampai kita memiliki array penuh baru kami.
Apa waktu berjalan dari algoritma ini?
Nah, mari kita mempertimbangkan dampak dari ini.
Kami pergeseran setiap elemen.
Ketika kita menghapus i, kita menggeser semua elemen setelah ke kiri.
Dan itu adalah O (n) biaya
karena apa jika kita menghapus elemen pertama?
Jadi untuk penghapusan masing-masing, kita hapus -
penghapusan masing-masing menimbulkan O (n) operasi,
dan karena kita memiliki n kepindahan, ini mengarah ke shuffle (n ^ 2) O.
Oke. Jadi baik awal. Awal yang baik.
>> Saran lain adalah dengan menggunakan sesuatu yang dikenal sebagai shuffle Knuth,
atau shuffle Fisher-Yates.
Dan itu benar-benar mengocok waktu linier.
Dan ide ini sangat mirip.
Sekali lagi, kami memiliki berbagai masukan kami,
tapi bukannya menggunakan dua array untuk masukan kami / output,
kita menggunakan bagian pertama dari array untuk melacak porsi kami dikocok,
dan kita melacak, dan kemudian kita meninggalkan sisa array kita untuk porsi unshuffled.
Jadi, inilah yang saya maksud. Kami memulai dengan - kita memilih suatu i,
sebuah array dari 0 sampai 20.
Pointer saat ini kami menunjuk ke indeks pertama.
Kami memilih beberapa i sini
dan sekarang kita bertukar.
Jadi jika ini adalah 5 dan ini adalah 4,
array yang dihasilkan akan memiliki 5 di sini dan di sini 4.
Dan sekarang kita perhatikan penanda di sini.
Semuanya ke kiri yang dikocok,
dan segala sesuatu ke kanan yang unshuffled.
Dan sekarang kita dapat mengulangi proses tersebut.
Kami memilih indeks acak antara 1 dan 20 sekarang.
Jadi misalkan baru kami i di sini.
Sekarang kita bertukar saya ini dengan posisi saat ini baru kami di sini.
Jadi kita yang swapping bolak-balik seperti ini.
Biarkan aku membawa kode untuk membuatnya lebih konkret.
Kita mulai dengan pilihan kami dari i -
kita mulai dengan i sama dengan 0, kita memilih j lokasi acak
di bagian unshuffled dari array, saya ke n-1.
Jadi jika aku di sini, memilih indeks acak antara sini dan seluruh array,
dan kami bertukar.
Ini semua kode yang diperlukan untuk mengocok array Anda.
Ada pertanyaan?
>> Nah, salah satu pertanyaan yang diperlukan, mengapa ini benar?
Mengapa setiap permutasi kemungkinan yang sama?
Dan aku tidak akan pergi melalui bukti ini,
tetapi banyak masalah dalam ilmu komputer dapat dibuktikan melalui induksi.
Berapa banyak dari Anda sudah familiar dengan induksi?
Oke. Cool.
Sehingga Anda dapat membuktikan kebenaran dari algoritma ini dengan induksi sederhana,
di mana hipotesis induksi Anda akan, menganggap bahwa
mengocok saya kembali setiap kemungkinan yang sama permutasi
sampai dengan elemen i pertama.
Sekarang, pertimbangkan i + 1.
Dan dengan cara kita memilih j indeks kami untuk swap,
ini mengarah ke - dan kemudian Anda menyusun rincian,
setidaknya bukti penuh mengapa algoritma ini kembali
setiap permutasi dengan probabilitas kemungkinan yang sama.
>> Semua, masalah sebelah kanan.
Jadi "diberikan sebuah array bilangan bulat, postive, nol, negatif,
menulis sebuah fungsi yang menghitung jumlah maksimum
dari setiap subarray continueous dari array masukan. "
Contoh di sini adalah, dalam kasus di mana semua nomor yang positif,
maka saat ini pilihan terbaik adalah untuk mengambil seluruh array.
1, 2, 3, 4, sama dengan 10.
Bila Anda memiliki beberapa negatif di sana,
dalam hal ini kita hanya ingin dua yang pertama
karena memilih -1 dan / atau -3 akan membawa jumlah kami turun.
Kadang-kadang kita mungkin harus mulai di tengah-tengah array.
Kadang-kadang kita ingin memilih apa-apa sama sekali, yang terbaik untuk tidak mengambil apa pun.
Dan kadang-kadang lebih baik untuk mengambil musim gugur,
karena hal setelah itu super besar. Jadi setiap ide?
(Mahasiswa, tidak dapat dimengerti) >> Ya.
Misalkan saya tidak mengambil -1.
Kemudian baik saya memilih 1.000 dan 20.000,
atau aku hanya memilih 3 miliar.
Nah, pilihan terbaik adalah untuk mengambil semua nomor.
Ini -1, meskipun negatif,
jumlah keseluruhan lebih baik daripada yang saya tidak mengambil -1.
Jadi salah satu tips yang saya sebutkan sebelumnya adalah untuk menyatakan secara jelas jelas
dan solusi brute force pertama.
Apa solusi kekerasan dalam masalah ini? Ya?
[Jane] Nah, saya pikir solusi brute force
akan menjumlahkan semua kombinasi yang mungkin (tidak dapat dimengerti).
[Yu] Oke. Jadi, ide Jane adalah untuk mengambil setiap kemungkinan -
Saya parafrase - adalah untuk mengambil setiap subarray terus menerus mungkin,
menghitung penjumlahan, dan kemudian mengambil maksimum dari semua subarrays terus menerus mungkin.
Apa yang unik mengidentifikasi subarray dalam berbagai masukan saya?
Seperti, apa dua hal yang saya butuhkan? Ya?
(Mahasiswa, tidak dapat dimengerti) >> Kanan.
Sebuah batas bawah pada indeks dan indeks batas atas
unik menentukan subarray terus menerus.
[Mahasiswa Wanita] Apakah kita memperkirakan itu array nomor unik?
[Yu] No Jadi pertanyaannya adalah, apakah kita mengasumsikan array kita -
adalah array kita semua nomor yang unik, dan jawabannya tidak.
>> Jika kita menggunakan kekerasan solusi kami, maka mulai / akhir indeks
unik menentukan subarray berkelanjutan kami.
Jadi jika kita iterate untuk semua entri permulaan yang memungkinkan,
dan untuk semua entri end> ​​atau = untuk memulai, dan <n,
Anda menghitung penjumlahan, dan kemudian kita mengambil jumlah maksimum yang telah kita lihat sejauh ini.
Apakah ini jelas?
Apa O besar dari solusi ini?
Timewise.
Tidak cukup n ^ 2.
Perhatikan bahwa kita iterate dari 0 sampai n,
jadi itu salah satu untuk loop.
Kami iterate lagi dari hampir awal sampai akhir, yang lain untuk loop.
Dan sekarang, dalam bahwa, kita harus meringkas setiap entri,
sehingga itu lain untuk loop. Jadi kami memiliki tiga bersarang untuk loop, n ^ 3.
Oke. Ini berjalan sebagai titik awal.
Solusi kami adalah tidak lebih buruk dari n ^ 3.
Apakah setiap orang memahami solusi kekerasan?
>> Oke. Sebuah solusi yang lebih baik adalah menggunakan ide yang disebut pemrograman dinamis.
Jika Anda mengambil CS124, yaitu Algoritma dan Struktur Data,
Anda akan menjadi sangat akrab dengan teknik ini.
Dan gagasan itu, cobalah untuk membangun solusi untuk masalah yang lebih kecil pertama.
Apa yang saya maksudkan dengan ini adalah, saat ini kami perlu khawatir tentang dua hal: awal dan akhir.
Dan itu menjengkelkan. Bagaimana jika kita bisa menyingkirkan salah satu parameter?
Satu ide adalah - kita mengingat masalah asli kami,
menemukan jumlah maksimum setiap subarray dalam range [O, n-1].
Dan sekarang kami memiliki subproblem baru, di mana kita tahu, dalam indeks kami saat i,
kita tahu bahwa kita harus menyimpulkan ada. Subarray kami harus berakhir di indeks saat ini.
Jadi masalah yang tersisa adalah, di mana harus kita mulai subarray kami?
Apakah ini masuk akal? Oke.
Jadi saya telah dikodekan up ini, dan mari kita lihat apa artinya ini.
Dalam codirectory, ada program yang disebut subarray,
dan dibutuhkan jumlah item,
dan mengembalikan jumlah subarray maksimal dalam daftar saya dikocok.
Jadi dalam hal ini, subarray maksimal kami adalah 3.
Dan itu diambil dengan hanya menggunakan 2 dan 1.
Mari kita jalankan lagi. Ini juga 3.
Tapi kali ini, perhatikan bagaimana kita mendapat 3.
Kami mengambil - kita hanya mengambil 3 itu sendiri
karena itu dikelilingi oleh negatif pada kedua belah pihak,
yang akan membawa penjumlahan <3.
Mari kita berjalan pada 10 item.
Kali ini 7, kita mengambil 3 terkemuka dan 4.
Kali ini 8, dan kita mendapatkan bahwa dengan mengambil 1, 4 dan 3.
Jadi untuk memberikan intuisi tentang bagaimana kita bisa memecahkan masalah ini berubah,
mari kita lihat subarray ini.
Kami diberi array masukan, dan kita tahu jawabannya adalah 8.
Kami mengambil 1, 4, dan 3.
Tapi mari kita lihat bagaimana kita benar-benar mendapat jawaban itu.
Mari kita lihat pada subarray maksimal yang berakhir pada masing-masing indeks.
Apa subarray maksimal yang harus berakhir di posisi pertama?
[Mahasiswa] Zero. >> Nol. Hanya tidak mengambil -5.
Di sini akan menjadi 0 juga. Ya?
(Mahasiswa, tidak dapat dimengerti)
[Yu] Oh, maaf, itu adalah -3.
Jadi ini adalah 2, ini adalah -3.
Oke. Jadi -4, apa subarray maksimal untuk mengakhiri posisi tersebut
mana -4 adalah pada? Nol.
Satu? 1, 5, 8.
Sekarang, saya harus berakhir di lokasi di mana -2 adalah di.
Jadi 6, 5, 7, dan yang terakhir adalah 4.
Mengetahui bahwa ini adalah entri saya
untuk masalah berubah di mana saya harus berakhir di masing-masing indeks,
maka jawaban akhir saya hanya, mengambil menyapu di seberang,
dan mengambil jumlah maksimum.
Jadi dalam hal ini itu 8.
Ini menyiratkan bahwa subarray maksimal berakhir pada indeks ini,
dan mulai di suatu tempat sebelum itu.
Apakah semua orang mengerti ini subarray berubah?
>> Oke. Nah, mari kita mengetahui kekambuhan untuk ini.
Mari kita mempertimbangkan hanya beberapa entri pertama.
Jadi di sini itu 0, 0, 0, 1, 5, 8.
Dan kemudian ada -2 sini, dan yang membawanya ke 6.
Jadi jika saya sebut masuk di posisi i subproblem (i),
bagaimana saya bisa menggunakan jawaban untuk subproblem sebelumnya
untuk menjawab subproblem ini?
Jika saya melihat, katakanlah, entri ini.
Bagaimana saya bisa menghitung jawaban 6 dengan melihat
kombinasi ini array dan jawaban atas subproblem sebelumnya dalam array ini? Ya?
[Mahasiswa Wanita] Anda mengambil array jumlah
dalam posisi tepat sebelum, jadi 8,
dan kemudian Anda menambahkan subproblem saat ini.
[Yu] Jadi saran nya adalah dengan melihat dua angka,
ini dan nomor ini.
Jadi ini 8 mengacu pada jawaban untuk subproblem yang (i - 1).
Dan mari kita sebut A. masukan array saya
Dalam rangka untuk menemukan subarray maksimal yang berakhir pada posisi i,
Aku punya dua pilihan: Saya dapat melanjutkan subarray tersebut
yang berakhir pada indeks sebelumnya, atau mulai array baru.
Jika saya melanjutkan subarray yang dimulai pada indeks sebelumnya,
maka jumlah maksimum yang dapat saya capai adalah jawaban atas subproblem sebelumnya
ditambah entri array saat ini.
Tapi, saya juga memiliki pilihan untuk memulai subarray baru,
dalam hal jumlah adalah 0.
Jadi jawabannya adalah max dari 0, subproblem i - 1, ditambah masuknya array saat ini.
Apakah kekambuhan ini masuk akal?
Kekambuhan kami, karena kami baru saja menemukan, adalah subproblem i
adalah sama dengan maksimum dari subproblem sebelumnya ditambah entri array saya saat ini,
yang berarti melanjutkan subarray sebelumnya,
atau 0, memulai subarray baru di index saya saat ini.
Dan setelah kami telah membangun tabel ini solusi, maka jawaban akhir kami,
hanya melakukan menyapu linier di array subproblem
dan mengambil jumlah maksimum.
Ini merupakan implementasi yang tepat dari apa yang saya katakan.
Jadi kita membuat array subproblem baru, submasalah.
Entri pertama adalah 0 atau entri pertama, maksimal dua.
Dan untuk sisa subproblem
kita menggunakan kekambuhan yang tepat kita hanya menemukan.
Sekarang kita menghitung maksimum array subproblem kami, dan itulah jawaban akhir kami.
>> Jadi berapa banyak ruang yang kita gunakan dalam algoritma ini?
Jika Anda hanya diambil CS50, maka Anda mungkin tidak dibahas ruang yang sangat banyak.
Nah, satu hal yang perlu diperhatikan adalah bahwa aku menelepon malloc sini dengan n ukuran.
Apa yang menyarankan kepada Anda?
Algoritma ini menggunakan ruang linier.
Bisakah kita berbuat lebih baik?
Apakah ada sesuatu yang Anda perhatikan bahwa tidak perlu untuk menghitung jawaban akhir?
Saya kira pertanyaan yang lebih baik adalah, informasi apa
kita tidak perlu membawa semua jalan sampai akhir?
Sekarang, jika kita melihat dua baris,
kita hanya peduli tentang subproblem sebelumnya,
dan kami hanya peduli tentang maksimum yang pernah kami lihat sejauh ini.
Untuk menghitung jawaban akhir kami, kita tidak perlu seluruh array.
Kita hanya perlu nomor terakhir, terakhir dua angka.
Terakhir nomor array subproblem, dan nomor terakhir untuk maksimum.
Jadi, pada kenyataannya, kita dapat sekering loop ini bersama-sama
dan pergi dari ruang ke ruang linier konstan.
Jumlah saat ini sejauh ini, di sini, menggantikan peran subproblem, array subproblem kami.
Jadi jumlah saat ini, sejauh ini, adalah jawaban untuk subproblem sebelumnya.
Dan jumlah itu, sejauh ini, mengambil tempat max kami.
Kami menghitung maksimal seperti yang kita pergi bersama.
Dan jadi kami pergi dari ruang ke ruang linier konstan,
dan kami juga memiliki solusi untuk masalah linear subarray kami.
>> Jenis pertanyaan Anda akan mendapatkan selama wawancara.
Apa kompleksitas waktu, apa kompleksitas ruang?
Dapatkah Anda berbuat lebih baik? Apakah ada hal-hal yang tidak perlu untuk menjaga sekitar?
Saya melakukan ini untuk menyoroti analisis yang harus Anda ambil sendiri
karena Anda bekerja melalui masalah ini.
Selalu bertanya pada diri sendiri, "Dapatkah saya melakukan lebih baik?"
Bahkan, bisa kita lakukan lebih baik daripada ini?
Semacam pertanyaan jebakan. Anda tidak bisa, karena Anda perlu
setidaknya membaca masukan untuk masalah ini.
Jadi fakta bahwa Anda perlu setidaknya membaca masukan untuk masalah
berarti bahwa Anda tidak dapat melakukan lebih baik dari waktu linier,
dan Anda tidak dapat melakukan lebih baik daripada ruang konstan.
Jadi ini adalah, pada kenyataannya, solusi terbaik untuk masalah ini.
Pertanyaan? Oke.
>> Pasar saham masalah:
"Mengingat sebuah array bilangan bulat n, positif, nol, atau negatif,
yang mewakili harga saham selama hari n,
menulis fungsi untuk menghitung keuntungan maksimum Anda dapat membuat
mengingat bahwa Anda membeli dan menjual saham dalam tepat 1 hari ini n. "
Pada dasarnya, kami ingin membeli dengan harga rendah, menjual tinggi.
Dan kami ingin mengetahui keuntungan terbaik yang kita bisa membuat.
Kembali ke saya tip, apa jawaban, segera jelas sederhana, tapi itu lambat?
Ya? (Mahasiswa, tidak dapat dimengerti) >> Ya.
>> Jadi Anda hanya akan pergi meskipun dan melihat harga saham
pada setiap titik waktu, (dipahami).
[Yu] Oke, jadi solusi nya - sarannya komputasi
yang terendah dan tertinggi komputasi tidak selalu bekerja
karena tertinggi mungkin terjadi sebelum terendah.
Jadi apa solusi brute force untuk masalah ini?
Apa dua hal yang saya perlu unik menentukan keuntungan saya buat? Benar.
Solusi kekerasan adalah - oh, jadi, saran George adalah kita hanya perlu dua hari
untuk secara unik menentukan keuntungan dari dua hari.
Jadi kita menghitung setiap pasangan, seperti membeli / menjual,
menghitung keuntungan, yang bisa negatif atau positif atau nol.
Hitung keuntungan maksimum yang kita buat setelah iterasi atas semua pasang hari.
Itu akan menjadi jawaban akhir kami.
Dan solusi yang akan menjadi O (n ^ 2), karena ada n memilih dua pasang -
hari yang Anda dapat memilih di antara hari akhir.
Oke, jadi aku tidak akan pergi ke solusi brute force di sini.
Aku akan memberitahu Anda bahwa ada sebuah solusi log n n.
Algoritma apa yang saat ini Anda tahu bahwa adalah n log n?
Ini bukan pertanyaan jebakan.
>> Merge sort. Merge sort adalah n log n,
dan pada kenyataannya, salah satu cara untuk memecahkan masalah ini adalah dengan menggunakan
semacam gabungan semacam ide yang disebut, secara umum, membagi dan menaklukkan.
Dan idenya adalah sebagai berikut.
Anda ingin menghitung pembelian terbaik / menjual pasangan di kiri setengah.
Temukan keuntungan terbaik Anda dapat membuat, hanya dengan n pertama selama dua hari.
Kemudian Anda ingin oompute pembelian terbaik / menjual pasangan di kanan setengah,
sehingga n terakhir lebih dari dua hari.
Dan sekarang pertanyaannya adalah, bagaimana kita menggabungkan solusi ini kembali bersama-sama?
Ya? (Mahasiswa, tidak dapat dimengerti)
Oke >>. Jadi biarkan aku menggambar.
Ya? (George, tidak dapat dimengerti)
>> Tepat. Solusi George yang tepat.
Jadi sarannya adalah, pertama menghitung pasangan membeli / menjual yang terbaik,
dan yang terjadi pada paruh kiri, jadi mari kita sebut bahwa kiri, kiri.
Terbaik membeli / menjual pasangan yang terjadi di sisi kanan.
Tetapi jika kita hanya membandingkan dua angka, kita kehilangan kasus
di mana kita membeli dan menjual di sini di suatu tempat di sisi kanan.
Kami membeli di kiri setengah, menjual di kanan setengah.
Dan cara terbaik untuk menghitung pasangan membeli / menjual terbaik yang mencakup kedua bagian
adalah untuk menghitung minimum di sini dan menghitung maksimal di sini
dan mengambil perbedaan mereka.
Jadi dua kasus di mana pasangan membeli / menjual terjadi hanya di sini,
hanya di sini, atau di kedua bagiannya ditentukan oleh tiga angka.
Jadi algoritma kami untuk menggabungkan solusi kami kembali bersama-sama,
kita ingin menghitung pasangan membeli / menjual terbaik
di mana kita membeli pada paruh kiri dan menjual di kanan setengah.
Dan cara terbaik untuk melakukannya adalah untuk menghitung harga terendah di babak pertama,
harga tertinggi di kanan setengah, dan mengambil perbedaan mereka.
Tiga dihasilkan keuntungan, tiga angka, Anda mengambil maksimal tiga,
dan itulah keuntungan terbaik Anda dapat membuat lebih dari hari-hari pertama dan akhir.
Berikut garis penting adalah merah.
Ini adalah panggilan rekursif untuk menghitung jawaban di kiri setengah.
Ini adalah panggilan rekursif untuk menghitung jawaban di sisi kanan.
Kedua untuk loop menghitung min dan max pada babak kiri dan kanan, masing-masing.
Sekarang saya menghitung keuntungan yang mencakup kedua bagian,
dan jawaban akhir adalah maksimal tiga.
Oke.
>> Jadi, tentu, kita memiliki sebuah algoritma, tapi pertanyaan besar adalah,
apa kompleksitas waktu ini?
Dan alasan mengapa saya sebutkan semacam gabungan adalah bahwa bentuk membagi jawabannya
menjadi dua dan kemudian menggabungkan solusi kami kembali bersama-sama
adalah persis bentuk gabungan semacam.
Jadi biarkan aku pergi melalui durasi.
Jika kita mendefinisikan fungsi t (n) menjadi jumlah langkah
untuk hari n,
kami dua rekursif panggilan
masing-masing akan biaya t (n / 2),
dan ada dua panggilan tersebut.
Sekarang saya perlu untuk menghitung minimum kiri setengah,
yang saya bisa lakukan dalam n / 2 waktu, ditambah maksimum kanan setengah.
Jadi ini hanya n.
Dan kemudian ditambah beberapa pekerjaan konstan.
Dan persamaan kekambuhan
adalah persis persamaan kambuh gabungan semacam.
Dan kita semua tahu bahwa gabungan semacam adalah n log n waktu.
Oleh karena itu, algoritma kami juga n log n waktu.
Apakah iterasi ini masuk akal?
Hanya rekap singkat ini:
T (n) adalah sejumlah langkah untuk menghitung keuntungan yang maksimal
selama hari n.
Cara kita berpisah panggilan rekursif kami
adalah dengan memanggil solusi kami pada hari n / 2 pertama,
jadi itulah satu panggilan,
dan kemudian kita sebut lagi pada babak kedua.
Jadi itu dua panggilan.
Dan kemudian kita menemukan minimal pada babak kiri, yang bisa kita lakukan dalam waktu linier,
menemukan maksimum kanan setengah, yang bisa kita lakukan dalam waktu linear.
Jadi n / 2 + n / 2 hanya n.
Lalu kami memiliki beberapa pekerjaan yang konstan, yang seperti melakukan aritmatika.
Persamaan ini kambuh adalah persis persamaan kambuh gabungan semacam.
Oleh karena itu, algoritma shuffle kami juga n log n.
Jadi berapa banyak ruang yang kita gunakan?
Mari kita kembali ke kode.
>> Sebuah pertanyaan yang lebih baik adalah, berapa banyak frame tumpukan yang kita pernah miliki pada saat tertentu?
Karena kita menggunakan rekursi,
jumlah frame tumpukan menentukan penggunaan ruang kami.
Mari kita menganggap n = 8.
Kami menyebutnya putar acak 8,
yang akan memanggil mengocok pada empat entri pertama,
yang akan memanggil shuffle pada dua entri pertama.
Jadi tumpukan kami adalah - ini adalah tumpukan kami.
Dan kemudian kita sebut mengocok lagi pada 1,
dan itulah yang kasus dasar kita, sehingga kita kembali segera.
Apakah kita pernah memiliki lebih dari ini frame tumpukan banyak?
Tidak Karena setiap kali kita melakukan sebuah doa,
pemanggilan rekursif untuk shuffle,
kita membagi ukuran kami di setengah.
Jadi jumlah maksimum stack frame yang pernah kita miliki pada saat tertentu
berada di urutan frame log n tumpukan.
Setiap stack frame memiliki ruang konstan,
dan oleh karena itu jumlah total ruang,
jumlah maksimum ruang yang pernah kita gunakan adalah O (log n) ruang
di mana n adalah jumlah hari.
>> Sekarang, selalu tanyakan pada diri sendiri, "Bisakah kita berbuat lebih baik?"
Dan khususnya, kita bisa mengurangi ini untuk masalah kita sudah diselesaikan?
Sebuah petunjuk: kita hanya membahas dua masalah lainnya sebelum ini, dan itu tidak akan mengocok.
Kita dapat mengkonversi masalah pasar saham ke dalam masalah subarray maksimal.
Bagaimana kita bisa melakukan ini?
Salah satu dari Anda? Emmy?
(Emmy, tidak dapat dimengerti)
[Yu] Tepat.
Jadi masalah subarray maksimal,
kita mencari penjumlahan atas subarray terus menerus.
Dan saran Emmy untuk masalah saham,
mempertimbangkan perubahan, atau delta.
Dan gambar ini adalah - ini adalah harga saham,
tetapi jika kita mengambil perbedaan antara setiap hari berturut-turut -
jadi kita melihat bahwa harga maksimum, keuntungan maksimum kita bisa membuat
adalah jika kita membeli di sini dan menjual di sini.
Tapi mari kita lihat terus menerus - mari kita lihat masalah subarray.
Jadi di sini, kita dapat membuat - pergi dari sini ke sini,
kita memiliki perubahan yang positif, dan kemudian pergi dari sini ke sini kita memiliki perubahan negatif.
Tapi kemudian, pergi dari sini ke sini kita memiliki perubahan positif yang sangat besar.
Dan ini adalah perubahan yang ingin kita meringkas untuk mendapatkan keuntungan yang akhir kami.
Lalu kami memiliki lebih banyak perubahan negatif di sini.
Kunci untuk mengurangi masalah stok kami ke masalah subarray maksimal kami
adalah untuk mempertimbangkan delta antara hari.
Jadi kita membuat array baru yang disebut delta,
menginisialisasi pertama masuk menjadi 0,
dan kemudian untuk setiap delta (i), membiarkan hal itu menjadi perbedaan
dari saya masukan array (i), dan array (i - 1).
Kemudian kita sebut prosedur rutin kami untuk subarray maksimal
lewat di array delta itu.
Dan karena subarray maksimal adalah waktu linier,
dan ini pengurangan, ini proses menciptakan array delta,
juga waktu linier,
maka solusi akhir untuk saham adalah O (n) kerja ditambah O (n) pekerjaan, masih O (n) bekerja.
Jadi kita memiliki solusi waktu linier untuk masalah kita.
Apakah semua orang mengerti transformasi ini?
>> Secara umum, ide yang baik bahwa Anda harus selalu memiliki
adalah mencoba untuk mengurangi masalah baru yang Anda lihat.
Jika tampak akrab bagi masalah lama,
cobalah mengurangi ke masalah lama.
Dan jika Anda dapat menggunakan semua alat yang Anda telah digunakan pada masalah lama
untuk memecahkan masalah baru.
Jadi untuk membungkus, wawancara teknis menantang.
Masalah-masalah ini mungkin beberapa masalah yang lebih sulit
yang mungkin Anda lihat dalam sebuah wawancara,
jadi jika Anda tidak mengerti semua masalah yang saya hanya tertutup, tidak apa-apa.
Ini adalah beberapa masalah yang lebih menantang.
Latihan, latihan, latihan.
Saya memberikan banyak masalah dalam handout, jadi pasti memeriksa mereka keluar.
Dan good luck pada wawancara Anda. Semua sumber daya yang diposting di link ini,
dan salah satu teman senior saya telah menawarkan untuk melakukan wawancara teknis tiruan,
jadi jika Anda tertarik, email Will Yao pada alamat email.
Jika Anda memiliki beberapa pertanyaan, Anda dapat bertanya kepada saya.
Apakah kalian memiliki pertanyaan spesifik yang berhubungan dengan wawancara teknis
atau masalah yang telah kita lihat sejauh ini?
Oke. Nah, semoga sukses pada wawancara Anda.
[CS50.TV]