[Powered by Google Translate] [Семинар на тема: Технички Интервјуа]
[Kenny Ју, Универзитетот Харвард]
[Ова е CS50.] [CS50.TV]
Здраво на сите, јас сум Кени. Во моментов сум помлад студираат компјутерски науки.
Јас сум поранешен CS ТФ, а јас посакувам да сум имал оваа кога бев underclassman,
и тоа е зошто сум даваат овој семинар.
Па се надевам дека ќе уживам во тоа.
Овој семинар е за технички интервјуа,
и сите мои ресурси може да се најде на овој линк,
овој линк тука, неколку ресурси.
Па сум направил листа на проблеми, всушност, неколку проблеми.
Исто така, општо ресурси страница каде што може да се најдат совети
за тоа како да се подготват за едно интервју,
совети за она што треба да направите за време на вистински интервју,
како и како да им пријде на проблеми и ресурси за во иднина.
Тоа е за сите на интернет.
И само да предговор овој семинар, одрекување,
како тоа не треба да - вашата интервју подготовка
не треба да биде ограничена на оваа листа.
Ова е само замислена да биде водич,
и ти дефинитивно треба да се земе сè велам со зрно од сол,
но, исто така, се користи сè што се користи за да ви помогнат во интервју подготовка.
>> Одам да се забрза преку следните неколку слајдови
па можеме да дојдеме до вистинските студии на случај.
Структурата на интервјуто за софтверското инженерство postion,
обично тоа е 30 до 45 минути,
повеќе рунди, во зависност од компанијата.
Често ќе се кодирање на бела табла.
Значи, бела табла, како таков, но често во помал обем.
Ако имаш телефонски разговор, најверојатно ќе биде со користење на
или collabedit или Google Doc така што тие можат да те видат во живо кодирање
додека сте се интервјуирани преку телефон.
Интервју по себе е обично 2 или 3 проблеми
тестирање на вашето компјутерски науки знаење.
И тоа речиси сигурно ќе вклучи кодирање.
Видовите на прашања кои ќе ги видите се обично податочни структури и алгоритми.
И со тоа овие видови на проблеми,
тие ќе побара од вас, како, што е времето и просторот комплексност, голем О?
Често тие, исто така, побара од повисоко ниво прашања,
така, дизајнирање на системот,
како ќе нокаутирам вашиот код?
Што интерфејси, она што класи, што модули имате во вашиот систем,
и како овие комуницирате заедно?
Значи податочни структури и алгоритми како и дизајнирање системи.
>> Некои општи совети пред да нурне во нашите студии на случај.
Мислам дека најважно правило е секогаш да се размислува гласно.
Интервјуто треба да биде вашата шанса да ја покажат својата процес на мислење.
Поентата на интервјуто е за интервјуерот да се измери
како мислите и како ќе поминат низ проблем.
Најлошото нешто што можете да направите е да се молчи во текот на целиот разговор.
Тоа е само не е добро.
Кога ќе се даде на прашање, вие сакате да бидете сигурни дека ги разбирате прашање.
Значи повторувам прашањето назад со свои зборови
и обид да се работи темелно неколку едноставни тест случаи
да бидете сигурни дека ви е јасно прашањето.
Работа низ неколку тест случаи, исто така, ќе ви даде интуиција за тоа како да се реши овој проблем.
Може дури и да ја откриете неколку модели за да помогне да се реши проблемот.
Нивниот голем бакшиш е да не се фрустрирани.
Не се фрустрирани.
Интервјуа се предизвикувачки, но најлошото нешто што можете да направите,
во прилог на се молчи, да се видливо фрустрирани.
Вие не сакате да им даде впечаток дека на интервјуерот.
Едно нешто што - така, многу луѓе, кога тие одат во едно интервју,
тие се обидуваат да се обидат да најдат најдобро решение прво,
кога, навистина, има обично блескаво очигледна решение.
Тоа може да биде бавен, тоа може да биде неефикасна, но вие само треба да го наведе,
само така ќе имаат почетна точка од која треба да работат подобро.
Исто така, се укажува на решение е бавен, во смисла на
голема O време комплексност или простор сложеност,
ќе ја покажат на интервјуерот дека ви е јасно
овие прашања кога пишувате код.
Затоа, не плашете се да излезе со наједноставниот алгоритам првиот
а потоа работат подобро од таму.
Било какви прашања досега? Во ред.
>> Значи, да се нурне во нашите првиот проблем.
"Со оглед низа од n цели броеви, напише функција која меша низата
во место, така што сите пермутации од n цели броеви се подеднакво веројатно. "
И претпоставувам имате на располагање случаен број генератор
кој генерира број во опсег од 0 до јас, половина опсег.
Дали сите се разбере ова прашање?
Јас ви даде низа од n цели броеви, и сакам да се влага неа.
Во мојот именик, напишав неколку програми за да се покаже она што сакам да кажам.
Одам да се влага низа од 20 елементи,
од -10 до 9,
и сакам на излез да даде листа вака.
Значи ова е мојот подредени внесување низа, и сакам да се влага неа.
Ние ќе го направат тоа повторно.
Дали сите се разбере прашањето? Во ред.
Така, тоа е до вас.
Кои се некои идеи? Можете да го направите како n ^ 2, n најавите n, n?
Отворени за сугестии.
Во ред. Значи една идеја, предложен од Еми,
е првиот пресмета случаен број, случаен број, во опсег од 0 до 20.
Значи се претпостави нашата низа има должина од 20.
Во нашата дијаграм на 20 елементи,
ова е нашиот влез низа.
И сега, нејзиниот предлог е да се создаде нова низа,
па ова ќе биде излез низа.
И врз основа на вратив од ранд -
Значи, ако јас беше, да речеме, 17,
копија на 17-ти елемент во првата позиција.
Сега ние треба да го избришете - ние треба да го пренасочат сите елементи тука
над, така што имаме празнина на крајот и нема дупки во средината.
И сега ние се повторува процесот.
Сега ние избере нов случаен број помеѓу 0 и 19.
Имаме нов i тука, а ние го копирате овој елемент во оваа позиција.
Тогаш ние смена предмети и ние се повторува процесот додека имаме нашата целосна нова низа.
Што е во бегство за време на овој алгоритам?
Па, ајде да се разгледа влијанието на оваа.
Ние се менуваат секој елемент.
Кога ќе го отстраните овој i, ние се префрлаат сите елементи по налево.
А тоа е О (n) цена
затоа што ако ние го отстраниш првиот елемент?
Значи за секој отстранување, ги отстраниме -
секоја отстранување настануваат О (n) операција,
и бидејќи имаме n отстранувања, ова води кон О (n ^ 2) shuffle.
Во ред. Па добар почеток. Добар почеток.
>> Друг предлог е да се користи нешто познато како shuffle Кнут,
или Фишер-Јејтс shuffle.
А тоа е всушност еден линеарен пат shuffle.
И идејата е многу сличен.
Повторно, ние имаме влез низа,
но наместо користење на две низи за нашите влез / излез,
ние ги користиме на првиот дел од низата да ги пратите на нашата мешаат дел,
и ние да ги пратите, а потоа ние ја напушти остатокот од нашите низа за unshuffled дел.
Значи тука е она што сакам да кажам. Ние започнете со - ние изберете i,
низа од 0 до 20.
Нашата актуелна покажувачот се укажува на првиот индекс.
Ние изберете некои i тука
а сега ние трампа.
Значи, ако ова беше 5 и ова беше 4,
како резултат на низа ќе имаат 5 тука и 4 овде.
И сега ние се напомене маркер тука.
Сè што лево се мешаат,
и сè на правото е unshuffled.
И сега можеме да се повторува процесот.
Ние изберете случаен индекс помеѓу 1 и 20 часот.
Па претпоставувам нашите нови i е тука.
Сега ние се разменуваат оваа ми со нашите сегашни нова позиција тука.
Па ние се направи Замена напред и назад се допаѓа ова.
Дозволете ми да ги пренесат на кодот да се направи повеќе бетон.
Ние започнуваме со нашиот избор на i -
ние започнуваме со i еднаква на 0, ние изберете случаен локација ѕ
во unshuffled дел од низата, јас до n-1.
Значи, ако јас сум тука, изберете случаен индекс помеѓу тука и остатокот од низа,
и ние трампа.
Ова е сите го кодот потребно да се влага вашиот низа.
Било какви прашања?
>> Па, еден е потребно прашањето е, зошто е ова точно?
Зошто е секој пермутација подеднакво најверојатно?
И јас не ќе оди преку доказ за тоа,
но многу проблеми во компјутерски науки може да се докаже преку индукција.
Колкумина од вас се запознаени со индукција?
Во ред. Кул.
Така може да се докаже исправноста на овој алгоритам со едноставни индукција,
каде што вашите индукција хипотеза ќе биде, да се претпостави дека
мојата shuffle враќа секој пермутација подеднакво најверојатно
до првиот i елементи.
Сега, сметаат i + 1.
И од начинот на кој ние го бираме нашиот индекс ѕ да се разменуваат,
ова води кон - и потоа да работат надвор детали,
најмалку една целосна доказ за тоа зошто овој алгоритам се враќа
секој пермутација со подеднакво најверојатно веројатност.
>> Добро, следниот проблем.
Така, "дадени низа од цели броеви, postive, нула, негативна,
напише функција која пресметува максималната сума
на било continueous subarray на внесување низа. "
Еден пример е тука, во случај кога сите броеви се позитивни,
тогаш моментов најдобар избор е да се земе целиот спектар.
1, 2, 3, 4, изнесува 10.
Кога имате некои негативни таму,
во овој случај ние само сакаме првите две
бидејќи изборот -1 и / или -3 ќе донесе нашите сума надолу.
Понекогаш ние можеби ќе мора да започне во средината на низата.
Понекогаш сакаме да избере ништо, тоа е најдобро да не се земе нешто.
И понекогаш е подобро да се земе на есента,
бидејќи нешто по тоа е супер големи. Така сите идеи?
(Студент, неразбирливо) >> Да.
Претпоставувам дека не се -1.
Тогаш или изберам 1.000 и 20.000,
или јас само го избере 3 милијарди долари.
Па, најдобар избор е да ги преземе сите броеви.
Ова -1, и покрај тоа негативно,
целата сума е подобро отколку јас да не земат -1.
Значи еден од совети што споменав порано беше да се наведе јасно очигледно
и брутална сила решение во прв план.
Што е брутална сила решение на овој проблем? Да?
[Јане] Па, мислам дека брутална сила решение
ќе биде да додадете сите можни комбинации (неразбирливо).
[Ју] Во ред. Значи идејата Јане е да ги преземат сите можни -
Јас сум парафразирајќи - е да ги преземат сите можни континуирано subarray,
пресмета неговата сума, а потоа да ги преземат максимум од сите можни континуирано subarrays.
Што уникатно идентификува subarray во мојот влез низа?
Како, што две работи ми е потребно? Да?
(Студент, неразбирливо) >> Право.
Пониската врска на индекс и горна граница индекс
уникатно определува континуирана subarray.
[Жена студент] Дали ние проценка тоа е низа на единствени броеви?
[Ју] бр Значи нејзиното прашање е, дали сме претпоставувајќи нашите низа -
е нашата низа сите единствени броеви, а одговорот е не.
>> Ако ние ги користиме нашите брутална сила решение, тогаш почетокот / крајот индекси
уникатно определува нашето континуирано subarray.
Значи, ако ние iterate за сите можни почеток записи,
и за сите крајни записи> или = да започне, и <n,
ќе се пресмета сумата, а потоа го земеме максимална сума видовме досега.
Дали е ова јасно?
Што е голема О на ова решение?
Timewise.
Не е сосема n ^ 2.
Имајте на ум дека ние iterate од 0 до n,
па тоа е еден за телефонска линија.
Ние iterate повторно од речиси почетокот до крајот, уште еден за телефонска линија.
И сега, во рамките на тоа, ние мора да се сумира секој влез,
па тоа е уште еден за телефонска линија. Значи имаме три вгнездени јамки, n ^ 3.
Во ред. Ова оди како појдовна точка.
Нашето решение не е полошо отколку n ^ 3.
Дали сите се разбере брутална сила решение?
>> Во ред. А подобро решение е користење идеја нарекува, динамични програмирање.
Ако се земе CS124, која е Алгоритми и структури на податоци,
ќе стане многу запознаени со оваа техника.
И идејата е, обидете се да се изгради решенија за помали проблеми во прв план.
Што мислам со ова е, ние во моментов мора да се грижите за две работи: почеток и крај.
А тоа е досадно. Што ако ние би можеле да се ослободи од еден од оние параметри?
Една идеја е да - we're дадена нашата изворна проблем,
најде максималниот износ на било subarray во опсегот [O, N-1].
И сега имаме нов subproblem, каде што знаеме, во нашите сегашни индексот i,
знаеме ние мора да заклучиме таму. Нашите subarray мора да заврши на сегашниот индекс.
Па преостанат проблем е, каде што треба да почне нашата subarray?
Дали ова има смисла? Во ред.
Па јас кодирани овој горе, и ајде да погледнеме во она што тоа значи.
Во codirectory, има програма наречена subarray,
и е потребно број на предмети,
и го враќа максималната subarray сума во мојот мешаат листа.
Значи во овој случај, нашата максимална subarray е 3.
И дека е донесена само со користење на 2 и 1.
Ајде да се кандидира повторно. Тоа е исто така 3.
Но овој пат, забележуваат како добивме 3.
Ние го зеде - ние само ги преземе 3 себе
бидејќи тоа е опкружен со негативи на двете страни,
која ќе донесе сума <3.
Ајде да се кандидира за 10 предмети.
Овој пат тоа е 7, ние се водечки 3 и 4.
Овој пат тоа е 8, а ние се добие дека со 1, 4 и 3.
Па да ви даде интуиција за тоа како може да го решиме овој трансформира проблем,
ајде да ги разгледаме во оваа subarray.
Ние си даде овој влез низа, а ние го знаеме одговорот е 8.
Земаме 1, 4, и 3.
Но, ајде да погледнеме како ние всушност доби тој одговор.
Да ги погледнеме на максималната subarray кој заврши во секоја од овие индекси.
Што е максималниот subarray дека мора да заврши на првата позиција?
[Студентски] Zero. >> Нула. Само не преземе -5.
Тука тоа нема да биде 0, како и. Да?
(Студент, неразбирливо)
[Ју] О, извинете, тоа е -3.
Значи ова е 2, ова е -3.
Во ред. Значи -4, што е максимална subarray да се стави крај на таа позиција
каде -4 е? Нула.
Еден? 1, 5, 8.
Сега, јас мора да заврши на локацијата каде -2 е.
Значи 6, 5, 7, а последниот е 4.
Знаејќи дека овие се моите записи
за трансформира проблем, каде што мора да заврши на секој од овие индекси,
тогаш мојот конечен одговор е само, да земе замав низ,
и ќе ги преземе максималниот број.
Значи во овој случај тоа е 8.
Ова значи дека максималната subarray завршува на овој индекс,
и почна некаде пред него.
Дали сите се разбере ова трансформира subarray?
>> Во ред. Па, ајде да дознаам повторување за ова.
Да се ​​разгледа само првите неколку записи.
Значи тука е 0, 0, 0, 1, 5, 8.
И тогаш имаше -2 тука, и дека тоа се сведе на 6.
Значи, ако јас го нарекувам влез во позиција i subproblem (i),
Како можам да користам одговорот на претходната subproblem
да одговориме на ова subproblem?
Ако гледам во, да речеме, овој запис.
Како можам да се пресмета одговорот 6 од страна гледајќи во
комбинација од оваа низа и одговорите на претходните subproblems во оваа низа? Да?
[Жена студент] Вие преземе низа на суми
во позиција токму пред неа, па 8,
а потоа додадете тековната subproblem.
[Ју] Па ја предлог е да се погледне во овие два броја,
овој број и овој број.
Значи ова 8 се однесува на одговорот за subproblem (i - 1).
И ајде да се јавам на мојот влез низа А
Со цел да се најде максималниот subarray кој завршува во позиција I,
Имам две опции: јас или може да продолжи subarray
која заврши на претходниот индекс, или започнете нова низа.
Ако јас да се продолжи subarray која започна во претходниот индекс,
тогаш максималниот износ што може да се постигне е одговор на претходното subproblem
плус тековната низа влез.
Но, јас исто така имаат избор на отпочнување на нов subarray,
во кој случај сума е 0.
Значи одговорот е максимум од 0, subproblem i - 1, плус на тековната низа влез.
Дали ова повторување смисла?
Нашите повторување, како што само открив, е subproblem i
е еднаков на максимум од претходната subproblem плус тековната ми низа влез,
што значи продолжување на претходната subarray,
или 0, започнете нова subarray во тековната ми индекс.
И еднаш имаме изградено оваа табела на решенија, тогаш нашата конечниот одговор,
само направете една линеарна замав низ subproblem низа
и ќе ги преземе максималниот број.
Ова е точно спроведување на она што штотуку го кажав.
Значи ние создаваме нова subproblem низа, subproblems.
Првото влегување е или 0 или првото влегување, максималната на овие две.
И за остатокот од subproblems
ние ги користиме на точната повторување ние само открив.
Сега ние се пресмета максималната на нашите subproblems низа, и тоа е нашиот конечен одговор.
>> Значи колку простор сме со користење на овој алгоритам?
Ако сте само преземени CS50, тогаш не може да се дискутира простор многу.
Па, една работа е да се напомене е дека јавив Примерок тука со големина n.
Што значи дека укажуваат на вас?
Овој алгоритам користи линеарна простор.
Можеме да направиме подобро?
Постои ли нешто што ќе забележите дека е потребно да се пресмета конечниот одговор?
Претпоставувам А подобро прашање е, она што информации
не треба да се носат на целиот пат низ до крај?
Сега, ако гледаме на овие две линии,
ние само се грижат за претходната subproblem,
а ние само се грижат за максимално сме виделе досега.
Да се ​​пресмета нашите конечниот одговор, ние не треба целата низа.
Ние треба само последниот број, последните два броја.
Последниот број за subproblem низа, и последниот број за максимум.
Значи, во Всушност, можеме да осигурач овие петелки заедно
и да си одат од линеарни простор за постојана простор.
Сегашната сума досега, еве, го заменува улогата на subproblem, нашите subproblem низа.
Значи сегашната сума, досега, е одговор на претходното subproblem.
И таа сума, досега, го зема местото на нашите макс.
Ние пресмета максималната како што одиме понатаму.
И така одиме од линеарни простор за постојана простор,
и ние исто така имаат линеарна решение за нашите subarray проблем.
>> Овие видови на прашања ќе добиете за време на интервјуто.
Што е времето комплексност, што е простор комплексноста?
Можете да го направите подобро? Дали има работи кои што се непотребни да се задржи околу?
Го направив ова за да се потенцира анализи кои треба да се преземат за своја
како си работат во текот на овие проблеми.
Секогаш да се бара себеси, "Може ли да се направи подобро?"
Всушност, можеме да направиме подобро од ова?
Вид на трик прашање. Вие не може, затоа што треба да
најмалку прочитате влез на проблемот.
Значи фактот дека треба да се најмалку прочитате влез на проблемот
значи дека не можете да го направите подобро од линеарни време,
и не можете да го направите подобро од постојана простор.
Значи ова е, всушност, најдобро решение за овој проблем.
Прашања? Во ред.
>> Берза проблем:
"Со оглед низа од n цели броеви, позитивна, нула или негативна,
кои претставуваат цената на акциите во текот n дена,
напише функција за пресметување на максимална добивка може да се направи
со оглед на тоа што купува и продава точно 1 акција во рамките на овие n дена. "
Во суштина, ние сакаме да се купи ниски, продава високо.
И ние сакаме да дознаам најдобар профит може да се направи.
Да се ​​вратам на мојот врвот, што е веднаш јасно, Наједноставниот одговор, но тоа е бавен?
Да? (Студент, неразбирливо) >> Да.
>> Така да само ќе одат иако и се погледне на цените на акциите
на секоја точка во времето, (неразбирливо).
[Ју] Океј, па нејзиното решение - ја сугестијата на компјутери
најниската и компјутери највисок не мора да работат
бидејќи највисокиот може да се појават пред најниска.
Значи она што е брутална сила решение за овој проблем?
Што се двете работи кои треба да уникатно утврди добивката можам да направам? Право.
На брутална сила решението е - О, па така, предлог Џорџ е ние треба само два дена
еднозначно да се утврди добивката на тие два дена.
Значи ние се пресмета секој пар, како купување / продавање,
пресмета профит, што би можело да биде негативен или позитивен или нула.
Пресмета максималната добивка што правиме после процесирањето над сите пара дена.
Тоа ќе биде нашиот конечен одговор.
И дека решението ќе биде О (n ^ 2), бидејќи не е n изберете два пара -
на денови кои можете да изберете меѓу крајот дена.
Океј, па јас не одам да си во текот на брутална сила решение тука.
Одам да ви кажам дека има еден n најавите n решение.
Што алгоритам не сте во моментов се знае дека е n најавите n?
Тоа не е трик прашање.
>> Се спојат вид. Се спојат вид е n најавите n,
и всушност, еден начин на решавање на овој проблем е да се користи
еден вид спој вид на идеја нарекува, во целина, поделба и освојување.
И идејата е како што следува.
Сакате да се пресмета најдобар купува / продава пар во левата половина.
Најди ги најдобрите профит може да се направи, само со првите n над два дена.
Тогаш ќе сакате да oompute најдобрите купува / продава пар на десната половина,
па во последните n над два дена.
И сега прашањето е, како ние да се спојат овие решенија повторно заедно?
Да? (Студент, неразбирливо)
>> Океј. Значи, дозволете ми нацрта слика.
Да? (Џорџ, неразбирливо)
>> Токму така. Решение Џорџ е точно во право.
Значи неговиот предлог е, прво се пресмета најдобар купува / продава пар,
и што се случува во левата половина, па ајде да го наречеме тоа лево, лево.
Најдобра купува / продава пар што се случува во десната половина.
Но, ако ние само споредба на овие два броја, ние сме недостасува случај
каде што купуваат тука и го продаде некаде во десната половина.
Ние купуваме во левата половина, продаваат во десната половина.
И најдобар начин да се пресмета најдобар купува / продава пар што ги спојува двете половини
е да се пресмета минимална тука и пресмета максималната тука
и да се нивните разлики.
Па два случаи каде што се купува / продава пар се случува само тука,
само овде, или на двете половини е дефинирано од страна на овие три броја.
Па нашите алгоритам за да се логирате нашите решенија назад заедно,
ние сакаме да се пресмета најдобар купува / продава пар
каде да се купи на левата половина и го продаде на десната половина.
И најдобар начин да го направите тоа е да се пресмета најниска цена во првата половина,
највисока цена во десната половина, и да се нивните разлики.
Како резултат на три добивка, овие три броја, да ве однесе на максимум од три,
и тоа е најдобар профит може да се направи во текот на овие првите и на крајот дена.
Овде е важно линии се во црвено.
Ова е рекурзивен повик да се пресмета одговорот во левата половина.
Ова е рекурзивен повик да се пресмета одговорот во десната половина.
Овие два за петелки пресмета мин и макс на левата и десната половина, соодветно.
Сега јас се пресмета профит што ги спојува двете половини,
и конечниот одговор е максимум од овие три.
Во ред.
>> Значи, сигурни, имаме алгоритам, но поголем прашање е,
она што е време комплексноста на ова?
А причината зошто јас спомнав логирате вид е дека оваа форма на поделба на одговор
во два, а потоа се соединуваат нашите решенија повторно заедно
е токму форма на спојување вид.
Па дозволете ми да одат преку рок на траење.
Ако ние дефинирана функција t (n) да биде бројот на чекори
за n дена,
нашите две рекурзивните повици
се едни ќе чини t (n / 2),
и има две од овие повици.
Сега е потребно да се пресмета минимум на левата половина,
што можам да направам во n / 2 време, плус максимална на десната половина.
Значи ова е само n.
А потоа плус некои постојана работа.
И ова повторување равенката
е токму повторување равенка за спојување вид.
И сите знаеме дека логирате вид е n најавите n време.
Затоа, нашите алгоритам е, исто така, n најавите n време.
Дали ова повторување смисла?
Само кратко повториме на ова:
T (n) е бројот на чекори за да се пресмета максимална добивка
во текот на n дена.
Начинот на кој ние поделени нашата рекурзивните повици
е со повикување на решение за првите денови n / 2,
па тоа е еден повик,
а потоа ние го нарекуваме повторно на второто полувреме.
Значи тоа е два повици.
И тогаш ќе најдеме минимум на левата половина, што можеме да направиме во линеарна време,
најдете максимум на десната половина, што можеме да направиме во линеарна време.
Значи n / 2 + n / 2 е само n.
Потоа имаме некои постојана работа, која е како прави аритметика.
Ова повторување равенка е точно повторување равенка за спојување вид.
Оттука, нашите shuffle алгоритам е, исто така, n најавите n.
Значи колку простор сме користите?
Да се ​​вратиме на кодот.
>> А подобро прашање е, колку магацинот рамки ние некогаш имаат во секој даден момент?
Бидејќи ние сме користење на рекурзија,
бројот на магацинот рамки определува нашето искористеноста на просторот.
Да се ​​разгледа n = 8.
Ние го нарекуваме shuffle на 8,
кои ќе се јавите shuffle на првите четири записи,
кои ќе се јавите на shuffle на првите две ставки.
Така, нашето магацинот е - тоа е нашата оџак.
А потоа ние го нарекуваме shuffle повторно на 1,
и тоа е она што нашата база случај е, па ние се врати веднаш.
Дали некогаш имаат повеќе од ова многу магацинот рамки?
Не Затоа што секој пат кога правиме повикување,
рекурзивен повик да се влага,
ние делиме нашата големина на половина.
Значи максималниот број на магацинот рамки некогаш имаат во секој даден момент
е од редот на најавите n магацинот рамки.
Секоја магацинот рамка има постојана простор,
и затоа вкупниот износ на просторот,
максималниот износ на просторот што некогаш го користите е О (log n) простор
каде n е бројот на денови.
>> Сега, секогаш се запрашате, "можеме да направиме подобро?"
А особено, ние може да ја намали оваа на проблемот што веќе решен?
Навестување: ние само дискутира две други проблеми пред тоа, и тоа нема да биде shuffle.
Ние може да се конвертира овој пазар проблем во максималната subarray проблем.
Како можеме да го направите ова?
Еден од вас? Еми?
(Еми, неразбирливо)
[Ју] Токму така.
Па максималната subarray проблем,
ние сме во потрага за сума над континуиран subarray.
И предлог на Emmy за акциите проблем,
разгледа промените, или делти.
И слика од ова е - ова е цената на акциите,
но ако ние ја разликата меѓу секој следен ден -
па ќе видиме дека максималната цена, максимална добивка би можеле да направат
е ако се купи тука и продаваат тука.
Но, ајде да се погледне на непрекината - ајде да се погледне на subarray проблем.
Па еве, ние може да се направи - одат од тука до тука,
имаме позитивна промена, а потоа одат од тука до тука имаме негативна промена.
Но, тогаш, одејќи од тука до тука ние имаме огромна позитивна промена.
И овие се промени што сакате да се сумира да се добие нашата крајна добивка.
Тогаш ние имаме повеќе негативни промени тука.
Клучот за намалување на нашите акции проблем во нашата максимална subarray проблем
е да се разгледа на делти помеѓу дена.
Значи ние создаваме нова низа наречен делти,
иницијализира на првото влегување да биде 0,
а потоа за секој делта (i), нека биде разликата
на мојот влез низа (i), и низа (i - 1).
Тогаш ние го нарекуваме нашиот рутинска процедура за максимална subarray
поминува во низа на делтата.
И затоа максимално subarray е линеарна време,
и ова намалување, овој процес на создавање на оваа делта низа,
Исто така линеарно време,
тогаш конечно решение за акции е О (n) работа плус О (n) работа, се уште е О (n) работа.
Значи имаме еден линеарен пат решение за нашиот проблем.
Дали сите се разбере оваа трансформација?
>> Во принцип, добра идеја дека секогаш треба да имаат
се обиде да го намали нов проблем кој што го гледате.
Ако изгледа познат на еден стар проблем,
обидете се намалување до еден стар проблем.
И ако може да ги користи сите алатки кои сте користеле на стариот проблем
за решавање на нови проблеми.
Така да се заврши, технички интервјуа се предизвик.
Овие проблеми се веројатно некои од потешките проблеми
кои може да се види во едно интервју,
па ако не го разбираат сите проблеми што јас само се опфатени, тоа е во ред.
Ова се некои од повеќе предизвикувачки проблеми.
Пракса, пракса, пракса.
Дадов многу проблеми во судбина, па дефинитивно се провери оние надвор.
И со среќа на вашиот интервјуа. Сите мои ресурси се испратени на овој линк,
и еден од моите високи пријатели понуди да се направи се потсмеваат на технички интервјуа,
па ако сте заинтересирани, e-mail ќе Јао во е-мејл адреса.
Ако имате некои прашања, може да ме прашате.
Дали момци имаат конкретни прашања поврзани со техничките разговори
или било какви проблеми сме виделе досега?
Во ред. Па, со среќа на вашиот интервјуа.
[CS50.TV]