[Powered by Google Translate] [Seminar: Temubual Teknikal]
[Kenny Yu, Universiti Harvard]
[Ini adalah CS50.] [CS50.TV]
Hi semua, Saya Kenny. Saya kini komputer junior belajar sains.
Saya seorang bekas CS TF, dan saya berharap saya mempunyai ini apabila saya adalah seorang underclassman,
dan itulah sebabnya saya memberi seminar ini.
Jadi saya berharap anda menikmati ia.
Seminar ini adalah mengenai wawancara teknikal,
dan semua sumber saya boleh didapati di pautan ini,
pautan ini di sini, beberapa sumber.
Jadi saya membuat senarai masalah, sebenarnya, agak beberapa masalah.
Juga sumber halaman umum di mana kita boleh mencari tips
mengenai cara untuk menyediakan untuk temuduga,
tips mengenai apa yang perlu anda lakukan semasa temu bual sebenar,
serta bagaimana untuk mendekati masalah dan sumber untuk rujukan masa depan.
Ia adalah semua talian.
Dan hanya kepada kata pengantar seminar ini, penafian,
seperti ini tidak sepatutnya - penyediaan temuduga anda
tidak harus terhad kepada senarai ini.
Ini hanya bertujuan untuk menjadi panduan,
dan anda pasti harus mengambil segala-galanya yang saya katakan dengan sebutir garam,
tetapi juga menggunakan segala-galanya yang saya digunakan untuk membantu anda dalam persediaan temuduga anda.
>> Saya akan mempercepatkan melalui beberapa slaid seterusnya
supaya kita boleh sampai ke kajian kes sebenar.
Struktur temu bual untuk postion kejuruteraan perisian,
biasanya ia adalah 30 hingga 45 minit,
pusingan berganda, bergantung kepada syarikat itu.
Selalunya anda akan kod di atas papan putih.
Jadi lembaga putih seperti ini, tetapi selalunya pada skala yang lebih kecil.
Jika anda mempunyai temu bual telefon, anda mungkin akan menggunakan
sama ada collabedit atau Google Doc supaya mereka boleh melihat anda hidup pengekodan
semasa anda sedang ditemuramah melalui telefon.
Temu bual itu sendiri adalah biasanya 2 atau 3 masalah
menguji pengetahuan sains komputer anda.
Dan ia hampir pasti akan melibatkan pengekodan.
Jenis-jenis soalan yang anda akan melihat biasanya struktur data dan algoritma.
Dan dalam melakukan ini jenis masalah,
mereka akan meminta anda, seperti, apakah masa dan kerumitan ruang, O besar?
Selalunya mereka juga bertanya soalan tahap tinggi,
begitu, mereka bentuk sistem,
bagaimana anda akan meletakkan kod anda?
Apakah antara muka, apa kelas, apa modul adakah anda mempunyai dalam sistem anda,
dan bagaimana ini berinteraksi bersama-sama?
Jadi struktur data dan algoritma serta merekabentuk sistem.
>> Beberapa tip umum sebelum kita menyelam ke dalam kajian kes kami.
Saya fikir peraturan yang paling penting sentiasa berfikir dengan kuat.
Temuduga sepatutnya menjadi peluang anda untuk menunjuk-nunjuk proses pemikiran anda.
Titik temuduga adalah untuk penemuduga untuk mengukur
bagaimana anda berfikir dan bagaimana anda pergi melalui masalah.
Perkara yang paling teruk anda boleh lakukan ialah menjadi senyap seluruh temuduga.
Itu hanya tidak baik.
Apabila anda diberi soalan, anda juga mahu pastikan anda memahami soalan.
Jadi mengulangi soalan kembali dalam perkataan anda sendiri
dan cuba untuk bekerja teliti kes-kes ujian beberapa mudah
pastikan anda memahami soalan.
Bekerja melalui beberapa kes-kes ujian juga akan memberi anda intuisi bagaimana untuk menyelesaikan masalah ini.
Anda juga mungkin menemui beberapa corak untuk membantu anda menyelesaikan masalah.
Hujung besar mereka adalah untuk tidak berasa kecewa.
Jangan berasa kecewa.
Temubual adalah mencabar, tetapi perkara yang paling buruk yang boleh anda lakukan,
di samping untuk menjadi senyap, akan kelihatan kecewa.
Anda tidak mahu untuk memberi gambaran bahawa penemuduga.
Satu perkara yang anda - jadi, ramai orang, apabila mereka pergi ke dalam satu temu bual,
mereka cuba untuk cuba mencari penyelesaian terbaik pertama,
apabila benar-benar, terdapat biasanya penyelesaian dgn berkilau jelas.
Ia mungkin menjadi perlahan, ia mungkin tidak cekap, tetapi anda hanya perlu menyatakan,
hanya supaya anda mempunyai titik permulaan dari mana untuk bekerja lebih baik.
Juga, menunjukkan penyelesaian adalah perlahan, dari segi
O besar masa kerumitan atau kerumitan ruang,
akan menunjukkan kepada penemuduga bahawa anda memahami
isu-isu ini apabila menulis kod.
Jadi jangan takut untuk tampil dengan algoritma mudah pertama
dan kemudian bekerja lebih baik dari sana.
Sebarang soalan setakat ini? Okay.
>> Jadi mari menyelam ke dalam masalah pertama kami.
"Memandangkan pelbagai integer n, menulis fungsi yang shuffles array
di tempat seperti yang semua pilih atur n integer adalah sama mungkin. "
Dan andaikan anda mempunyai penjana integer rawak
yang menjana integer dalam julat dari 0 ke i, separuh julat.
Adakah semua orang memahami soalan ini?
Saya memberi anda pelbagai integer n, dan saya mahu anda shuffle ia.
Dalam direktori saya, saya menulis beberapa program untuk menunjukkan apa yang saya maksudkan.
Saya akan shuffle pelbagai 20 elemen,
dari -10 ke 9,
dan saya mahu anda untuk menayangkan senarai seperti ini.
Jadi ini adalah input pelbagai saya disusun, dan saya mahu anda shuffle ia.
Kami akan melakukannya sekali lagi.
Adakah semua orang memahami soalan? Okay.
Jadi ia terpulang kepada anda.
Apa adalah beberapa idea? Anda boleh melakukannya sebagai n ^ 2, n log n, n?
Terbuka kepada cadangan.
Okay. Jadi, satu idea, yang dicadangkan oleh Emmy,
adalah pertama mengira nombor rawak, integer rawak, dalam pelbagai 0-20.
Jadi menganggap pelbagai kami mempunyai panjang 20.
Dalam rajah 20 elemen,
ini adalah pelbagai input kami.
Dan kini, cadangan beliau ialah untuk mewujudkan pelbagai baru,
jadi ini akan menjadi pelbagai output.
Dan berdasarkan i kembali oleh rand -
jadi jika i adalah, katakan, 17,
menyalin elemen ke-17 ke kedudukan pertama.
Sekarang kita perlu memadam - kita perlu beralih semua unsur-unsur di sini
supaya kita mempunyai jurang di hujung dan tiada lubang di tengah-tengah.
Dan sekarang kita mengulangi proses tersebut.
Sekarang kita memilih integer baru rawak antara 0 dan 19.
Kami mempunyai i baru di sini, dan kami menyalin elemen ini ke dalam kedudukan ini.
Kemudian kita beralih barangan lebih dan kita mengulangi proses tersebut sehingga kita mempunyai pelbagai penuh kami baru.
Apakah masa tayangan algoritma ini?
Nah, mari kita mempertimbangkan kesan ini.
Kami beralih setiap elemen.
Apabila kita keluarkan ini i, kita beralih semua unsur-unsur selepas ia ke kiri.
Dan itu adalah kos O (n)
kerana apa jika kita membuang elemen pertama?
Jadi, untuk setiap penghapusan, kita mengeluarkan -
penyingkiran setiap menanggung operasi O (n),
dan kerana kita telah n penarikan balik, ini membawa kepada shuffle O (n ^ 2).
Okay. Jadi permulaan yang baik. Permulaan yang baik.
>> Satu lagi cadangan adalah untuk menggunakan sesuatu yang dikenali sebagai shuffle Knuth,
atau shuffle Fisher-Yates.
Dan ia sebenarnya shuffle masa linear.
Dan idea adalah sangat serupa.
Sekali lagi, kita mempunyai pelbagai input kami,
tetapi sebaliknya menggunakan dua tatasusunan untuk input / output kita,
kita menggunakan bahagian pertama array menjejaki bahagian dikocok kami,
dan kita menjejaki, dan kemudian kami meninggalkan seluruh array kami untuk bahagian unshuffled.
Jadi di sini adalah apa yang saya maksudkan. Kita mulakan dengan - kita memilih i,
pelbagai 0-20.
Penunjuk semasa kami menunjuk kepada indeks pertama.
Kami memilih beberapa di sini saya
dan sekarang kita swap.
Jadi, jika ini adalah 5 dan ini adalah 4,
array yang terhasil akan mempunyai 5 di sini dan 4 di sini.
Dan sekarang kita perhatikan penanda di sini.
Semua ke kiri dikocok,
dan segala-galanya ke kanan unshuffled.
Dan kini kita boleh mengulangi proses tersebut.
Kami memilih indeks rawak antara 1 dan 20 sekarang.
Jadi andaikan baru i di sini.
Sekarang kita menukar i ini dengan kedudukan semasa baru kami di sini.
Jadi kita bertukar-tukar belakang dan sebagainya seperti ini.
Izinkan saya membawa sehingga kod untuk membuat ia lebih konkrit.
Kita mulakan dengan pilihan kami i -
kita mulakan dengan i sama kepada 0, kita memilih j lokasi rawak
di bahagian unshuffled array, i n-1.
Jadi, jika saya di sini, memilih indeks rawak antara di sini dan seluruh array,
dan kita swap.
Ini adalah semua kod yang diperlukan ke shuffle pelbagai anda.
Apa-apa soalan?
>> Nah, salah satu yang diperlukan soalan ini, mengapa ini betul?
Mengapa setiap pilihatur sama mungkin?
Dan aku tidak akan pergi melalui bukti ini,
tetapi banyak masalah dalam bidang sains komputer boleh dibuktikan melalui induksi.
Berapa ramai daripada anda biasa dengan induksi?
Okay. Sejuk.
Jadi, anda boleh membuktikan kesahihan algoritma ini secara aruhan mudah,
mana hipotesis induksi anda akan, menganggap bahawa
shuffle saya mengembalikan setiap pilihatur sama berkemungkinan
sehingga unsur-unsur i pertama.
Sekarang, pertimbangkan i + 1.
Dan dengan cara itu kita memilih j indeks kami untuk menukar,
ini membawa kepada - dan kemudian anda bekerja keluar butiran,
sekurang-kurangnya satu bukti penuh mengapa algoritma ini kembali
setiap pilihatur dengan kebarangkalian yang sama mungkin.
>> Baiklah, masalah seterusnya.
Jadi "diberi pelbagai integer, postive, sifar, negatif,
menulis fungsi yang mengira jumlah maksimum
daripada subarray sebarang continueous pelbagai input. "
Satu contoh di sini adalah, dalam kes di mana semua nombor adalah positif,
maka kini pilihan terbaik adalah untuk mengambil pelbagai keseluruhan.
1, 2, 3, 4, bersamaan 10.
Apabila anda mempunyai beberapa negatif di sana,
dalam kes ini, kita hanya mahu dua yang pertama
kerana memilih -1 dan / atau -3 akan membawa jumlah kita ke bawah.
Kadang-kadang kita mungkin mempunyai bermula pada pertengahan array.
Kadang-kadang kita mahu untuk memilih apa-apa pada semua, ia adalah yang terbaik untuk tidak mengambil apa-apa.
Dan kadang-kadang ia adalah lebih baik untuk mengambil kejatuhan,
kerana perkara selepas ia adalah super besar. Jadi apa-apa idea?
(Pelajar, difahami) >> Yeah.
Katakan saya tidak mengambil -1.
Kemudian sama ada saya memilih 1,000 dan 20,000,
atau saya hanya memilih 3 bilion.
Nah, pilihan terbaik adalah untuk mengambil semua nombor.
Ini -1, walaupun negatif,
jumlah keseluruhan adalah lebih baik daripada saya tidak mengambil -1.
Jadi salah satu tip yang saya sebutkan tadi adalah untuk menyatakan yang jelas jelas
dan daya penyelesaian kasar terlebih dahulu.
Apakah penyelesaian kekerasan dalam masalah ini? Yeah?
[Jane] Nah, saya fikir penyelesaian kekerasan
akan menambah sehingga semua kemungkinan kombinasi (difahami).
[Yu] Okay. Jadi idea Jane adalah untuk mengambil setiap mungkin -
Saya parafrasa - adalah untuk mengambil setiap subarray berterusan mungkin,
mengira jumlah, dan kemudian mengambil maksimum semua subarrays mungkin berterusan.
Apa yang unik mengenal pasti subarray dalam pelbagai input saya?
Seperti, apa dua perkara yang saya perlukan? Yeah?
(Pelajar, difahami) Hak. >>
A lebih rendah terikat pada indeks dan indeks terikat atas
unik menentukan subarray berterusan.
[Pelajar Perempuan] Adakah kita menganggarkan ia adalah pelbagai nombor yang unik?
[Yu] No Jadi persoalannya beliau, kita menganggap pelbagai kami -
adalah pelbagai kami semua nombor yang unik, dan jawapannya tidak.
>> Jika kita menggunakan penyelesaian kekerasan kami, maka indeks permulaan / akhir
unik menentukan subarray berterusan kami.
Jadi, jika kita melelar untuk semua catatan permulaan yang mungkin,
dan untuk semua catatan akhir> atau = untuk memulakan, dan <n,
anda mengira jumlah, dan kemudian kita mengambil jumlah maksimum yang telah kita lihat setakat.
Adakah ini jelas?
Apakah O besar daripada penyelesaian ini?
TimeWise.
Tidak cukup n ^ 2.
Perhatikan bahawa kita melelar dari 0 hingga n,
supaya satu untuk gelung.
Kami melelar lagi dari hampir awal hingga akhir, satu lagi untuk gelung.
Dan kini, dalam tempoh itu, kita perlu kepada jumlah kemasukan setiap,
jadi itulah satu lagi untuk gelung. Jadi, kita mempunyai tiga bersarang gelung, n ^ 3.
Okay. Ini berlaku sebagai titik permulaan.
Penyelesaian kami adalah tidak lebih buruk daripada n ^ 3.
Adakah semua orang memahami penyelesaian kekerasan?
>> Okay. Satu penyelesaian yang lebih baik menggunakan idea yang dipanggil pengaturcaraan dinamik.
Jika anda mengambil CS124, yang merupakan Algoritma dan Struktur Data,
anda akan menjadi sangat biasa dengan teknik ini.
Dan idea, cuba untuk membina penyelesaian kepada masalah yang lebih kecil pertama.
Apa yang saya maksudkan dengan ini ialah, kita kini perlu bimbang tentang dua perkara: mula dan akhir.
Dan itulah menjengkelkan. Bagaimana jika kita boleh menghilangkan salah mereka parameter?
Satu idea adalah untuk - Sign In Register New diberikan masalah asal kita,
mencari jumlah maksimum subarray mana-mana dalam pelbagai [O, n-1].
Dan sekarang kita mempunyai subproblem baru, di mana kita tahu, dalam indeks semasa kami i,
kita tahu kita mesti menyimpulkan di sana. Subarray kita mesti berakhir pada indeks semasa.
Jadi baki masalah, di mana kita harus memulakan subarray kami?
Adakah ini masuk akal? Okay.
Jadi saya telah dikodkan sehingga ini, dan mari kita melihat apa yang bermakna ini.
Dalam codirectory, terdapat program yang dipanggil subarray,
dan ia mengambil beberapa barangan,
dan ia kembali jumlah maksimum subarray dalam senarai dikocok saya.
Jadi dalam kes ini, subarray maksimum kami adalah 3.
Dan itu diambil dengan hanya menggunakan 2 dan 1.
Mari kita berjalan lagi. Ia juga 3.
Tetapi kali ini, perhatikan bagaimana kita mendapat 3.
Kami mengambil - kita hanya mengambil 3 sendiri
kerana ia dikelilingi oleh negatif di kedua-dua belah pihak,
yang akan membawa jumlah <3.
Mari kita berjalan di 10 item.
Kali ini ia adalah 7, kita ambil 3 terkemuka dan 4.
Kali ini ia adalah 8, dan kita mendapatkan bahawa dengan mengambil 1, 4 dan 3.
Jadi, untuk memberi anda intuisi tentang bagaimana kita boleh menyelesaikan masalah ini yang berubah,
mari kita melihat subarray ini.
Kami diberikan ini pelbagai input, dan kita tahu jawapannya ialah 8.
Kami mengambil 1, 4, dan 3.
Tetapi biarlah kita melihat bagaimana kita sebenarnya mendapat jawapan yang.
Mari kita melihat subarray maksimum yang berakhir pada setiap indeks ini.
Apa subarray maksimum yang telah berakhir pada kedudukan pertama?
[Pelajar] Sifar. >> Zero. Hanya tidak mengambil -5.
Di sini ia akan menjadi 0 serta. Yeah?
(Pelajar, tidak bijaksana yang)
[Yu] Oh, maaf, ia adalah -3.
Jadi ini adalah 2, ini adalah -3.
Okay. Jadi -4, apa yang subarray maksimum untuk menamatkan kedudukan itu
mana -4 adalah pada? Sifar.
Satu? 1, 5, 8.
Sekarang, saya mesti berakhir di lokasi mana -2 adalah pada.
Jadi 6, 5, 7, dan yang terakhir ialah 4.
Mengetahui bahawa ini adalah entri saya
untuk masalah berubah di mana saya mesti berakhir pada setiap indeks ini,
maka jawapan akhir saya hanya mengambil sapu di seluruh,
dan mengambil bilangan maksimum.
Jadi dalam kes ini ia adalah 8.
Ini menunjukkan bahawa subarray maksimum berakhir pada indeks ini,
dan bermula di suatu tempat sebelum ia.
Adakah semua orang faham ini subarray berubah?
>> Okay. Nah, mari kita memikirkan berulang untuk ini.
Mari kita pertimbangkan hanya beberapa entri pertama.
Jadi di sini ia adalah 0, 0, 0, 1, 5, 8.
Dan kemudian ada -2 di sini, dan yang dibawa ke 6.
Jadi, jika saya panggil kemasukan pada kedudukan i subproblem (i),
bagaimana saya boleh menggunakan jawapan kepada subproblem sebelumnya
untuk menjawab subproblem ini?
Jika saya melihat, katakan, kemasukan ini.
Bagaimana saya boleh mengira jawapan 6 dengan melihat
gabungan pelbagai ini dan jawapan kepada subproblems sebelumnya dalam pelbagai ini? Ya?
[Pelajar Perempuan] Anda mengambil pelbagai jumlah wang
dalam kedudukan yang betul sebelum ia, jadi 8,
dan kemudian anda menambah subproblem semasa.
[Yu] Jadi cadangan beliau adalah untuk melihat kedua-dua nombor,
nombor ini dan bilangan ini.
Jadi ini 8 merujuk kepada jawapan untuk subproblem (i - 1).
Dan mari kita memanggil A. pelbagai input saya
Dalam usaha untuk mencari subarray maksimum yang berakhir pada kedudukan i,
Saya mempunyai dua pilihan: saya sama ada boleh terus subarray
yang berakhir pada indeks sebelumnya, atau memulakan pelbagai baru.
Jika saya adalah untuk meneruskan subarray yang bermula pada indeks sebelumnya,
maka jumlah maksimum yang saya boleh mencapai adalah jawapan kepada subproblem sebelumnya
ditambah kemasukan array semasa.
Tetapi, saya juga mempunyai pilihan memulakan subarray baru,
di mana jumlah adalah 0.
Jadi jawapannya adalah max 0, subproblem i - 1, ditambah kemasukan array semasa.
Adakah berulangnya ini masuk akal?
Berulangnya kami, kerana kami hanya ditemui, adalah subproblem i
adalah bersamaan dengan maksimum subproblem sebelumnya ditambah kemasukan pelbagai semasa saya,
yang bermaksud meneruskan subarray sebelumnya,
atau 0, memulakan satu subarray pada indeks semasa saya baru.
Dan apabila kita telah membina jadual ini penyelesaian, maka jawapan akhir kita,
hanya melakukan menyapu linear merentasi pelbagai subproblem
dan mengambil bilangan maksimum.
Ini adalah pelaksanaan sebenar apa yang saya katakan.
Jadi kita mewujudkan pelbagai subproblem baru, subproblems.
Kemasukan pertama adalah sama ada 0 atau kemasukan pertama, maksimum kedua-dua.
Dan untuk rehat daripada subproblems
kita gunakan berulangnya sebenar kita hanya mendapati.
Sekarang kita mengira maksimum pelbagai subproblems kami, dan itulah jawapan akhir kami.
>> Jadi berapa banyak ruang yang kita gunakan dalam algoritma ini?
Jika anda hanya diambil CS50, maka anda tidak mungkin telah dibincangkan ruang yang sangat banyak.
Nah, salah satu perkara yang perlu diambil perhatian adalah bahawa saya dipanggil malloc sini dengan n saiz.
Apakah yang mencadangkan kepada anda?
Algoritma ini menggunakan ruang linear.
Bolehkah kita melakukan yang lebih baik?
Adakah terdapat apa-apa yang anda notis yang perlu untuk mengira jawapan akhir?
Saya rasa soalan yang lebih baik, apa maklumat
adakah kita tidak perlu untuk menjalankan sepanjang jalan hingga ke hujung?
Sekarang, jika kita melihat kedua-dua baris,
kita hanya menjaga tentang subproblem sebelumnya,
dan kita hanya mengambil berat tentang maksimum kita pernah dilihat setakat ini.
Untuk mengira jawapan akhir kita, kita tidak memerlukan pelbagai keseluruhan.
Kami hanya memerlukan nombor terakhir, dua nombor terakhir.
Nombor terakhir untuk pelbagai subproblem, dan nombor terakhir untuk maksimum.
Jadi, pada hakikatnya, kita boleh menggabungkan gelung ini bersama
dan pergi dari ruang linear ke angkasa malar.
Jumlah semasa setakat ini, di sini, menggantikan peranan subproblem, pelbagai subproblem kami.
Jumlah Jadi semasa, setakat ini, adalah jawapan kepada subproblem sebelumnya.
Dan jumlah wang itu, setakat ini, mengambil tempat max kami.
Kita mengira maksimum seperti yang kita pergi bersama-sama.
Dan supaya kita pergi dari ruang linear kepada ruang yang berterusan,
dan kami juga mempunyai penyelesaian linear kepada masalah subarray kami.
>> Ini jenis soalan yang anda akan mendapat dalam satu temu bual.
Apakah kerumitan masa; apakah kerumitan ruang?
Anda boleh melakukan lebih baik? Adakah terdapat perkara-perkara yang tidak perlu untuk menjaga sekitar?
Saya melakukan ini untuk menyerlahkan analisis yang anda perlu mengambil sendiri
kerana anda bekerja melalui masalah-masalah ini.
Sentiasa bertanya diri anda sendiri, "Bolehkah saya melakukan yang lebih baik?"
Malah, kita boleh melakukan lebih baik daripada ini?
Susun soalan helah. Anda tidak boleh, kerana anda perlu
sekurang-kurangnya membaca input kepada masalah ini.
Jadi hakikat bahawa anda perlu sekurang-kurangnya membaca input kepada masalah
bermakna bahawa anda tidak boleh melakukan yang lebih baik daripada masa linear,
dan anda tidak boleh melakukan lebih baik daripada ruang malar.
Jadi ini adalah, pada hakikatnya, penyelesaian terbaik untuk masalah ini.
Soalan? Okay.
>> Masalah pasaran saham:
"Memandangkan pelbagai integer n, positif, sifar, atau negatif,
yang mewakili harga saham sepanjang hari n,
menulis fungsi untuk mengira keuntungan maksimum anda boleh membuat
diberikan bahawa anda membeli dan menjual tepat 1 saham dalam hari ini n. "
Pada asasnya, kita mahu membeli rendah, menjual tinggi.
Dan kita mahu memikirkan keuntungan yang terbaik kita boleh membuat.
Akan kembali ke hujung saya, apa yang serta-merta jelas, jawapan yang paling mudah, tetapi ia perlahan?
Ya? (Pelajar, difahami) >> Ya.
>> Jadi anda hanya akan pergi walaupun dan melihat harga saham
pada setiap titik dalam masa (difahami).
[Yu] Okay, so penyelesaiannya - cadangan beliau pengkomputeran
terendah dan pengiraan tertinggi tidak semestinya bekerja
kerana tertinggi mungkin berlaku sebelum terendah.
Jadi apakah penyelesaian kekerasan kepada masalah ini?
Apakah dua perkara yang saya perlu unik menentukan keuntungan yang saya buat? Betul.
Penyelesaian kekerasan - oh, jadi, cadangan George adalah kita hanya perlu dua hari
untuk unik menentukan keuntungan kedua-dua hari.
Jadi kita mengira setiap pasangan, seperti membeli / menjual,
mengira keuntungan, yang boleh menjadi positif atau negatif atau sifar.
Kirakan keuntungan maksimum yang kita buat selepas iterating atas semua pasang hari.
Yang akan menjadi jawapan muktamad kita.
Dan penyelesaian yang akan O (n ^ 2), kerana terdapat n memilih dua pasang -
hari yang anda boleh memilih antara hari akhir.
Okay, jadi saya tidak akan pergi lebih penyelesaian tenaga kasar di sini.
Saya akan memberitahu anda bahawa terdapat penyelesaian n log n.
Apa algoritma tidak anda kini tahu bahawa n log n?
Ia bukan satu soalan helah.
>> Gabung apapun. Gabung apapun n log n,
dan pada hakikatnya, salah satu cara untuk menyelesaikan masalah ini adalah dengan menggunakan
jenis apapun bergabung idea yang dipanggil, secara umum, membahagi dan menakluk.
Dan idea adalah seperti berikut.
Anda mahu untuk mengira belian terbaik / menjual sepasang dalam separuh kiri.
Cari keuntungan terbaik anda boleh membuat, hanya dengan n pertama selama dua hari.
Maka anda mahu oompute belian terbaik / menjual sepasang pada separuh kanan,
jadi n lepas selama dua hari.
Dan kini persoalannya ialah, bagaimana kita menggabungkan penyelesaian ini kembali bersama-sama?
Ya? (Pelajar, tidak bijaksana yang)
>> Okay. Jadi biarlah saya melukis.
Ya? (George, difahami)
>> Tepat sekali. Penyelesaian George adalah betul-betul betul.
Jadi cadangan beliau ialah, pertama mengira terbaik membeli / menjual sepasang,
dan yang berlaku dalam separuh kiri, jadi mari kita panggil yang kiri, kiri.
Best membeli / menjual pasangan yang berlaku dalam separuh betul.
Tetapi jika kita hanya berbanding kedua-dua nombor, kita hilang kes
di mana kita membeli di sini dan menjual suatu tempat di separuh betul.
Kami membeli dalam separuh kiri, menjual pada separuh yang betul.
Dan cara terbaik untuk mengira terbaik membeli / menjual pasangan yang menjangkau kedua-dua bahagian
adalah untuk mengira sekurang-kurangnya di sini dan mengira maksimum di sini
dan mengambil perbezaan mereka.
Jadi kedua-dua kes di mana pasangan membeli / menjual berlaku hanya di sini,
hanya di sini, atau di kedua-dua bahagian ditakrifkan oleh tiga nombor.
Jadi algoritma kami untuk menggabungkan penyelesaian kami kembali bersama-sama,
kita mahu untuk mengira terbaik membeli / menjual sepasang
di mana kita membeli di separuh kiri dan menjual pada separuh betul.
Dan cara terbaik untuk berbuat demikian adalah untuk mengira harga terendah pada separuh pertama,
harga tertinggi dalam separuh betul, dan mengambil perbezaan mereka.
Yang terhasil tiga keuntungan, ketiga-tiga nombor, anda mengambil maksimum tiga,
dan itulah keuntungan terbaik anda boleh membuat ke atas hari ini pertama dan akhir.
Berikut garis penting adalah merah.
Ini adalah panggilan rekursi untuk mengira jawapan dalam separuh kiri.
Ini adalah panggilan rekursi untuk mengira jawapan dalam separuh betul.
Kedua-dua untuk gelung mengira min dan maks pada separuh kiri dan kanan, masing-masing.
Sekarang saya mengira keuntungan yang menjangkau kedua-dua bahagian,
dan jawapan akhir adalah maksimum ketiga-tiga.
Okay.
>> Jadi, pasti, kita mempunyai algoritma, tetapi soalan yang lebih besar,
apakah kerumitan masa ini?
Dan sebab mengapa saya sebutkan apapun merge adalah bahawa ini bentuk membahagikan jawapannya
kepada dua dan kemudian bergabung penyelesaian kami kembali bersama-sama
sebenarnya bentuk apapun merge.
Jadi biarlah saya pergi melalui tempoh.
Jika kita ditakrifkan fungsi t (n) untuk menjadi nombor langkah
untuk hari n,
2 panggilan rekursi kami
masing-masing akan kos t (n / 2),
dan terdapat dua panggilan ini.
Sekarang saya perlu untuk mengira sekurang-kurangnya separuh kiri,
yang boleh saya lakukan di n / 2 masa, ditambah dengan maksimum separuh betul.
Jadi ini hanya n.
Dan kemudian ditambah dengan beberapa pekerjaan tetap.
Dan persamaan ini berulang
tepat persamaan apapun merge untuk berulang.
Dan kita semua tahu bahawa apapun merge n log n masa.
Oleh itu, algoritma kami juga n log n masa.
Adakah lelaran ini masuk akal?
Hanya recap ringkas ini:
T (n) adalah beberapa langkah untuk mengira keuntungan maksimum
sepanjang hari n.
Cara kita berpecah panggilan rekursi kami
adalah dengan memanggil penyelesaian kami pada hari pertama n / 2,
supaya satu panggilan,
dan kemudian kita panggil sekali lagi pada separuh kedua.
Jadi itulah dua panggilan.
Dan kemudian kita dapati minimum di separuh kiri, yang boleh kita lakukan dalam masa linear,
mencari maksimum separuh betul, yang boleh kita lakukan dalam masa linear.
Jadi n / 2 + n / 2 adalah hanya n.
Kemudian kita mempunyai beberapa kerja yang berterusan, yang adalah seperti melakukan aritmetik.
Persamaan ini perulangan adalah tepat persamaan apapun merge untuk berulang.
Oleh itu, algoritma shuffle kami juga n log n.
Jadi berapa banyak ruang yang kita gunakan?
Mari kita kembali kepada kod.
>> Satu soalan yang lebih baik, berapa banyak bingkai tindanan yang kita pernah mempunyai pada bila-bila masa yang diberikan?
Sejak kita menggunakan rekursi,
bilangan bingkai tindanan menentukan penggunaan ruang kami.
Mari kita pertimbangkan n = 8.
Kami menyeru shuffle pada 8,
yang akan memanggil shuffle di empat penyertaan pertama,
yang akan memanggil shuffle pada dua penyertaan pertama.
Jadi timbunan kami - ini adalah timbunan kita.
Dan kemudian kita panggil shuffle lagi pada 1,
dan bahawa apa kes asas kami, jadi kita kembali dengan segera.
Adakah kita pernah mempunyai lebih daripada ini bingkai tindanan banyak?
No Kerana setiap kali kita lakukan doa,
doa rekursi shuffle,
kita bahagikan saiz kami pada separuh.
Jadi bilangan maksimum bingkai tindanan kita pernah pada bila-bila masa yang diberikan
adalah atas perintah bingkai log n timbunan.
Setiap bingkai tindanan mempunyai ruang yang berterusan,
dan oleh itu jumlah ruang,
jumlah maksimum ruang kita pernah menggunakan O (log n) ruang
di mana n adalah bilangan hari.
>> Sekarang, sentiasa bertanya kepada diri sendiri, "Bolehkah kita melakukan yang lebih baik?"
Dan khususnya, kita boleh mengurangkan ini kepada masalah kita sudah diselesaikan?
Bayangan A: kita hanya membincangkan dua masalah lain sebelum ini, dan ia tidak akan menjadi shuffle.
Kita boleh menukar ini masalah pasaran saham ke dalam masalah subarray yang maksimum.
Bagaimana kita boleh melakukan ini?
Salah satu anda? Emmy?
(Emmy, difahami)
[Yu] Tepat sekali.
Jadi masalah subarray yang maksimum,
kita sedang mencari sejumlah atas subarray berterusan.
Dan cadangan Emmy untuk masalah stok,
mempertimbangkan perubahan, atau delta.
Dan gambar ini - ini adalah harga saham,
tetapi jika kita mengambil perbezaan antara setiap hari berturut-turut -
jadi kita lihat bahawa harga maksimum, keuntungan maksimum kita boleh membuat
adalah jika kita membeli di sini dan menjual di sini.
Tetapi mari kita lihat di berterusan - mari kita melihat masalah subarray.
Jadi di sini, kita boleh membuat - pergi dari sini ke sini,
kita mempunyai perubahan positif, dan kemudian pergi dari sini ke sini, kita mempunyai perubahan negatif.
Tetapi kemudian, pergi dari sini ke sini kita mempunyai perubahan positif yang besar.
Dan ini adalah perubahan yang kita mahu untuk meringkaskannya untuk mendapatkan keuntungan akhir kami.
Kemudian kita mempunyai perubahan yang lebih negatif di sini.
Kunci untuk mengurangkan masalah saham kita ke masalah subarray maksimum kami
adalah untuk mempertimbangkan delta antara hari.
Jadi kita mewujudkan barisan baru yang dipanggil delta,
memulakan kemasukan pertama untuk menjadi 0,
dan kemudian untuk setiap delta (i), membiarkan yang menjadi perbezaan
pelbagai input saya (i), dan pelbagai (i - 1).
Kemudian kita panggil prosedur rutin kami untuk subarray satu maksimum
lulus dalam pelbagai delta.
Dan kerana subarray maksimum adalah masa yang linear,
dan pengurangan ini, proses ini mewujudkan pelbagai delta,
juga masa linear,
maka penyelesaian akhir bagi saham adalah O (n) kerja kerja ditambah O (n), adalah masih O (n) kerja.
Jadi kita mempunyai penyelesaian masa linear kepada masalah kita.
Adakah semua orang memahami transformasi ini?
>> Secara umum, idea yang baik yang anda perlu sentiasa ada
cuba untuk mengurangkan masalah baru yang anda lihat.
Jika ia kelihatan biasa kepada masalah yang lama,
cuba mengurangkan masalah lama.
Dan jika anda boleh menggunakan semua alat-alat yang anda telah digunakan pada masalah lama
untuk menyelesaikan masalah baru.
Jadi untuk membalut, temuduga teknikal yang mencabar.
Masalah-masalah ini mungkin beberapa masalah yang lebih sukar
yang anda mungkin lihat dalam satu temu bual,
jadi jika anda tidak memahami semua masalah yang saya hanya dilindungi, ia adalah okay.
Ini adalah beberapa masalah yang lebih mencabar.
Amalan, amalan, amalan.
Saya memberikan banyak masalah dalam nota, jadi pasti memeriksa mereka keluar.
Dan nasib baik temuduga anda. Semua sumber saya Hantar pada pautan ini,
dan salah satu daripada rakan-rakan kanan saya telah ditawarkan untuk melakukan wawancara teknikal olok-olok,
jadi jika anda berminat, e-mel Will Yao di alamat e-mel.
Jika anda mempunyai beberapa soalan, anda boleh bertanya kepada saya.
Adakah anda semua mempunyai soalan-soalan khusus yang berkaitan dengan temuduga teknikal
atau mana-mana masalah yang kita telah melihat setakat ini?
Okay. Nah, nasib baik temuduga anda.
[CS50.TV]