[Powered by Google Translate] [Семинар: Технички Интервјуи]
[Кени Иу, Универзитет Харвард]
[Ово је ЦС50.] [ЦС50.ТВ]
Здраво свима, ја сам Кени. Тренутно сам млађи студирања компјутерских наука.
Ја сам бивши ЦС ТФ, и волео бих имао ово кад сам био ундерцлассман,
и то је разлог зашто сам давао овај семинар.
Надам се да ћете уживати.
Овај семинар је о техничким разговорима,
и сви моји ресурси могу се наћи на овом линку,
овај линк овде, пар ресурса.
Тако сам направио списак проблема, заправо, доста проблема.
Такође, општи ресурси страница где можемо наћи савете
како да се припремите за интервју,
савети о томе шта би требало да урадите током актуелног интервјуа,
као и како да приђу проблемима и ресурсе за будућу употребу.
То је све на мрежи.
И само да предговор овај семинар, одрицању,
овако не треба - ваш интервју припреме
не би требало да буде ограничен на овој листи.
Ово је само требало да буде за употребу,
и дефинитивно треба узети све што кажем са резервом,
али такође користе све сам користио да вам помогне у разговору припреми.
>> Идем да убрза кроз наредних неколико слајдова
тако да можемо да дођемо до конкретних студија случаја.
Структура интервјуу за позицији софтверског инжењерства,
обично је 30 до 45 минута,
више рунди, у зависности од компаније.
Често ћете бити кодирање на белој табли.
Дакле бела табла овако, али често у мањем обиму.
Ако имате телефонски интервју, вероватно ћете користити
било цоллабедит или Гоогле Доц тако да могу да виде живите кодирање
док сте се обавља разговор преко телефона.
Сам интервју је обично 2 или 3 проблема
тестирање рачунара науку знање.
И то ће скоро сигурно укључити кодирање.
Врсте питања које ћете видети су углавном структуре података и алгоритми.
И радите ове врсте проблема,
они ће вас, као, шта је време и простор комплексност, велики О?
Често они такође питају вишег нивоа питања,
па, пројектовање система,
како би ти изнесе своју шифру?
Шта интерфејса, шта класе, шта модула имате у вашем систему,
и како то интеракцију заједно?
Дакле структуре података и алгоритми, као и пројектовање система.
>> Неке опште савете пре него што уронимо у нашим студијама случаја.
Мислим да је најважније правило је увек размишља наглас.
Интервју је требало да буде ваша шанса да покажу свој процес размишљања.
Поента разговора је за разговор да се утврди
како мислите и како идете кроз проблем.
Најгоре што можете да урадите је да ћутимо током целог разговора.
То једноставно није добар.
Када су дати питање, такође желите да будете сигурни да разумете питање.
Дакле, понављам питање поново у својим речима
и покушај да раде темељну неколико једноставних случајевима тестирања
да ли сте разумели питање.
Рад кроз неколико тестова случајева ће вам такође дати интуицију о томе како да се реши овај проблем.
Можда чак открити неколико обрасци ће вам помоћи да решите проблем.
Њихов велики савет је да се не исфрустрирани.
Немојте се фрустриран.
Интервјуи су изазовне, али најгора ствар коју можете да урадите,
поред тога што ћути, јесте да се видно фрустриран.
Ви не желите да тај утисак на испитивача.
Једна ствар која ти - тако, многи људи, када оду у једном интервјуу,
они покушавају да покуша да нађе најбоље решење,
кад стварно, обично постоји блештаво очигледно решење.
То може бити спор, то може бити неефикасан, али само треба да га наведе,
Само тако имате полазну тачку са које раде боље.
Такође, указујући на решење спора, у смислу
Велики О времену сложеност или простор сложеност,
ће показати да интервјуише који разумете
ова питања приликом писања кода.
Дакле, не плашите се да дођу до најједноставнијем алгоритам прво
и онда боље раде од тамо.
Сва питања до сада? Ок.
>> Дакле, хајде да зароните у нашем првом проблему.
"Имајући у виду низ од н целих бројева, написати функцију која меша вредност у низу
на месту те да све пермутације ових н целих бројева подједнако вероватно. "
И претпостављам да имате на располагању случајан цео број генератор
који генерише цео у опсегу од 0 И да, пола опсег.
Да ли сви разумеју ово питање?
Ја вам дати низ од н целих бројева, а ја желим да га мешати.
У мом именику, написао сам неколико програма да покажу шта мислим.
Идем да дволичност низ од 20 елемената,
од -10 до +9,
и желим да излаз листу овако.
Дакле, ово је мој сортиран улаз низ, а ја желим да га промешати.
Ми ћемо то урадити поново.
Да ли сви разумеју питање? Ок.
Дакле, то је на вама.
Које су неке идеје? Можеш ли то учинити као н ^ 2, н лог н, н?
Отвори за предлоге.
Ок. Дакле, једна идеја, предложили Еми,
је прво израчуна случајни број, случајни цео број, у опсегу од 0 до 20 година.
Дакле, претпоставимо наш низ има дужину од 20 година.
У нашем дијаграму 20 елемената,
ово је наш улаз низ.
А сада, њен предлог је да направите нови низ,
тако да ће ово бити излаз низ.
И на основу сам вратио ранда -
па ако сам био, рецимо, 17,
копирајте 17. елемент у првој позицији.
Сада нам је потребно да избришете - морамо овде да пребаце све елементе
преко, тако да имамо празнину на крају и нема рупе у средини.
А сада ми поновите процес.
Сада бирамо нову случајан цео број између 0 и 19 година.
Имамо нову ја, и ми копирати овај елемент у овој позицији.
Онда смо схифт артикала више и понављамо поступак док не будемо имали нашу пуну нови низ.
Шта је време рада овог алгоритма?
Па, хајде да размотримо утицај овога.
Ми се пребацује сваки елемент.
Када смо уклонили ову ја смо се пребацује све елементе после тога са леве стране.
И то је О (н) трошкови
јер шта ако смо уклонили први елемент?
Дакле, за сваку уклањање, уклонимо -
свака уклањање сноси О (н) операција,
и пошто смо н уклањања, ово доводи до О (н ^ 2) збрци.
Ок. Тако добар почетак. Добар почетак.
>> Други предлог је да користите нешто познат као Кнутх збрци,
или Фишер-Иатес Схуффле.
И то је заправо линеарно време схуффле.
А идеја је веома слична.
Опет, имамо инпут низ,
али уместо да користите два низове за наш улаз / излазом,
користимо први део низа да пратите наше мешали дела,
и ми смо пратили, а онда оставити остатак нашег низа за унсхуффлед дела.
Дакле, ево шта ја мислим. Почињемо са - бирамо једну ја,
низа од 0 до 20 година.
Наш тренутни показивач указује на први индекс.
Бирамо неке и овде
и сада смо заменили.
Дакле, ако је ово 5 и то је било 4,
резултујући низ имати 5 Овде и 4 овде.
И сада примећујемо овде маркер.
Све са леве стране је мешали,
и све десно је унсхуффлед.
А сада можемо поновити процес.
Бирамо случајни индекс између 1 и 20 сада.
Дакле, претпостављам да је наша нова сам овде.
Сада смо заменили Ово сам са нашом тренутном нову позицију овде.
Дакле, ми не премештају и назад овако.
Дозволите ми да се код да би га више бетона.
Ми смо започели са нашим избором и -
почнемо са и једнак 0, бирамо случајно ј локације
у унсхуффлед део низа, ја се н-1.
Дакле, ако сам ја овде, одаберите случајни индекс између овде и остатак низа,
и ми свап.
То је све код неопходно да схуффле свој низа.
Има ли питања?
>> Па, један потребан питање је, зашто је то тако?
Зашто је свака пермутација подједнако вероватно?
И нећу ићи кроз доказ овога,
али многи проблеми у рачунарству се може доказати кроз индукције.
Колико сте упознати са индукцијом?
Ок. Кул.
Дакле, можете да докажете исправност овог алгоритма по једноставном индукцијом,
где ти је хипотеза индукција би, претпостављам да
мој схуффле враћа свака пермутација подједнако вероватно
до првих елемената и.
Сада, размислите и + 1.
А успут смо изабрали нашу ј индекс да замени,
ово доводи до - и онда разради детаље,
бар пун доказ зашто је овај алгоритам враћа
свака пермутација са подједнако вероватним вероватноће.
>> Добро, следећи проблем.
Дакле, "с обзиром низ целих бројева, постиве, нула, негативан,
написати функцију која израчунава максималну суму
било цонтинуеоус субарраи улазног низа. "
Пример овде је, у случају када су сви бројеви су позитивни,
онда тренутно најбољи избор је да се цео низ.
1, 2, 3, 4, једнако 10.
Када имате неке негативне тамо,
у овом случају само желимо прва два
јер избору -1 и / или -3 ће донети нашу суму доле.
Понекад можда ћемо морати да почне у средини низа.
Понекад желимо да изабере ништа уопште, то је најбоље да не узимају ништа.
А понекад је боље да пада,
јер ствар после ње је супер велика. Па било које идеје?
(Студент, неразумљив) >> Да.
Претпостављам да не -1 узети.
Тада сам изабере 1.000 и 20.000,
или сам само изаберите 3 милијарде.
Па, најбољи избор је да предузме све бројеве.
Ово -1, упркос томе што су негативне,
цела сума је боље него што сам није да се -1.
Дакле, један од савета које сам раније поменутих био да констатовати јасно види
и бруте форце решење на првом месту.
Шта је бруте форце решење овог проблема? Да?
[Јане] Па, ја мислим да је сирова снага раствор
би да саберете све могуће комбинације (неразумљиво).
[Иу] Ок. Дакле, Џејн Идеја је да се све могуће -
Ја сам парафразирам - да предузму све могуће континуирано субарраи,
израчунати своју суму, а онда се максимум од свих могућих континуираних субарраис.
Оно јединствено идентификује субарраи у мом улазном низу?
Као, шта две ствари ми је потребно? Да?
(Студент, неразумљив) >> реду.
Доња граница индекса и горњу границу индекса
јединствено одређује непрекидни субарраи.
[Студенткиња] Да ли смо процењујући да је низ јединствених бројева?
[Иу] Но Па њено питање је, да ли смо под претпоставком да наш низ -
Наша је низ све јединствене бројеве, а одговор је не.
>> Ако користимо наше голе силе решење, а затим и старт / енд индекса
јединствено одређује наше непрекидно субарраи.
Дакле, ако смо прелазили на све могуће старт уноса,
и за све крајње уносе> или = на почетак, и <н,
да израчуна суму, а онда узмемо максималну суму смо видели до сада.
Је ли то јасно?
Шта је велики О овог решења?
Тимевисе.
Није баш н ^ 2.
Имајте на уму да смо прелазили од 0 на Н,
тако да је то један за петљу.
Поново смо прелазили из готово почетка до краја, други за петљу.
И сада, у оквиру тога, морамо да сумирамо све ставке,
тако да је то још један за петљу. Дакле, имамо три угнежђену за петље, н ^ 3.
Ок. Ово иде као полазну тачку.
Наше решење није гора од н ^ 3.
Да ли сви разумеју голе силе решење?
>> Ок. Боље решење је коришћење идеју назива динамичко програмирање.
Ако узмете ЦС124, који је Алгоритми и подаци структуре,
ћете постати веома упознати са овом техником.
А идеја, покушајте да се изгради решења за мање проблеме на првом месту.
Оно што мислим да је ово тако, тренутно имамо да бринемо о две ствари: почетка и краја.
И то је досадно. Шта ако бисмо могли ослободити једног од тих параметара?
Једна од идеја је да се - ми смо дали наш првобитни проблем,
пронађете максималну суму било субарраи у опсегу [О, н-1].
И сада имамо нову субпроблем, где знамо, у нашој струја И индекса,
ми знамо да морамо закључити тамо. Наш субарраи мора да се заврши на садашњем индекса.
Дакле, преостали проблем је, где би требало да почнемо нашу субарраи?
Да ли ово смисла? Ок.
Тако сам кодирани ово, и хајде да погледамо шта то значи.
У цодирецтори, постоји програм који се зове субарраи,
и то траје неколико ставки,
и враћа максималну суму субарраи у мом мешали листи.
Дакле, у овом случају, наша максимална субарраи је 3.
И то је узет користећи само 2 и 1.
Хајде да пробамо поново. Такође је 3.
Али овај пут, имајте на уму како смо добили 3.
Ми узео - ми узми Тхе 3 себе
јер је окружен негатива на обе стране,
који ће донети Сум <3.
Хајде да раде на 10 ставки.
Овај пут то је 7, узимамо водећу 3 и 4.
Овај пут то је 8, а ми смо добили да је узимање 1, 4 и 3.
Тако да вам дам интуицију о томе како можемо да решимо тај проблем трансформише,
хајде да погледамо на овом субарраи.
Смо дали смо овај унос низ, а ми знамо да је одговор 8.
Ми узимамо 1, 4 и 3.
Али, хајде да погледамо како смо заправо добили тај одговор.
Погледајмо максималне субарраи који је окончан у свакој од ових индекса.
Шта је максимална субарраи која треба да се заврши на првом месту?
[Студентски] Зеро. >> Нула. Само не узимају -5.
Овде ће бити 0, као добро. Да?
(Студент, неразумљив)
[Иу] Ох, извини, то је -3.
Дакле, ово је 2, ово је -3.
Ок. Дакле -4, шта је максимална субарраи да оконча ту позицију
где је на -4? Нула.
Један? 1, 5, 8.
Сада, мора да се заврши на месту где је на -2.
Дакле 6, 5, 7, и последњи је 4.
Знајући да су моји уноси
за трансформисаног проблем где морам завршити у свакој од ових индекса,
онда мој коначни одговор је само, узмите ђерам преко,
и да максималан број.
Дакле, у овом случају то је 8.
То подразумева да максимална субарраи завршава на овом индексу,
и почео негде пре њега.
Да ли сви разумеју овај трансформише субарраи?
>> Ок. Па, хајде да откријемо понављање за ово.
Размотримо само неколико првих ставки.
Дакле, овде је 0, 0, 0, 1, 5, 8.
А онда је -2 овде, и то је сведен на 6 година.
Дакле, ако ја зовем улазак у позицији сам субпроблем (и)
Како могу да користим одговор на претходну субпроблем
да одговори на ово субпроблем?
Ако погледам, рецимо, овај унос.
Како могу да израчуна одговор 6 гледајући
Комбинација овог низа и одговоре на претходним субпроблемс у овом низу? Да?
[Студенткиња] Можете узети низ сума
у позицији десно пре тога, тако да је 8,
и онда додати тренутну субпроблем.
[Иу] Дакле њен предлог је да погледате ова два броја,
овај број и овај број.
Дакле, ово 8 односи на одговор за субпроблем (и - 1).
И да зовем А. унос низа
У циљу проналажења максималну субарраи која се завршава на позицији И,
Имам два избора: или да може да настави са субарраи
којим је окончан у претходној индекса, или почети нови низ.
Ако бих био да се настави субарраи који је започет у претходном индекса,
онда је максимална сума ја могу да остваре је одговор на претходни субпроблем
плус струја низ унос.
Али, ја имам избор почиње нови субарраи,
у ком случају је збир 0.
Дакле, одговор је мак од 0, субпроблем и - 1, плус струја низ унос.
Да ли то рецидив смисла?
Наш понављање, као што смо управо открили је субпроблем ја
једнак максимуму претходног субпроблем плус моје тренутне низа уласка,
што значи наставак претходног субарраи,
или 0, почети нову субарраи на моје тренутне индекса.
И када смо изградили ову табелу решења, онда је наш коначни одговор,
само урадите линеарну ђерам преко субпроблем низу
и да максималан број.
Ово је тачна примена онога што сам рекао.
Тако смо направили нови низ субпроблем, субпроблемс.
Први унос је 0 или прва ставка, а највише оних двоје.
А за остале субпроблемс
користимо тачно понављање смо управо открио.
Сада смо израчунати максимум нашег низа субпроблемс, и то је наш коначан одговор.
>> Па колико простора смо користе у овом алгоритму?
Уколико сте само узети ЦС50, онда можда нисте разговарали простор много.
Па, једна ствар је да сам позвао маллоц овде са величине н.
Шта то сугерише за тебе?
Овај алгоритам користи линеарну простор.
Можемо ли боље?
Да ли постоји нешто што сте приметили да је непотребно да се израчуна коначни одговор?
Ваљда боље питање је, какве информације
ми не треба да носе скроз до краја?
Сада, ако погледамо ове две линије,
ми само бринемо о претходном субпроблем,
а ми само стало до максимума смо икада видели до сада.
Да би се израчунала наш коначан одговор, ми не треба цео низ.
Треба само последњи број, последња два броја.
Последњи број за субпроблем низа, а последњи број за максимума.
Дакле, у ствари, можемо заједно споји ове петље
и иде од линеарног простора сталном простора.
Тренутни износ до сада, овде, замењује улогу субпроблем, наш субпроблем низа.
Дакле струја сума, до сада, је одговор на претходни субпроблем.
И то сума, за сада, заузима место нашег мак.
Ми смо израчунали максимум како идемо заједно.
И тако идемо од линеарног простора сталном простора,
а имамо и линеарно решење за наше субарраи проблема.
>> Оваква питања ћете добити током интервјуа.
Шта је време комплексност, шта је простор сложеност?
Можеш ли ти боље? Да ли постоје ствари које су непотребне да около?
Урадио сам ово да нагласим анализе које треба да предузму сами
као што радите кроз ове проблеме.
Увек се питате: "Могу ли боље?"
У ствари, можемо боље од овога?
Нешто трик питање. Ти не можеш, зато што је потребно да
барем прочитајте улаз проблема.
Дакле, чињеница да морате да барем прочитате улаз на проблем
значи да не можете да урадите боље од линеарног времена,
а ви не можете урадити боље од константног простора.
Дакле, ово је, у ствари, најбоље решење за овај проблем.
Питања? Ок.
>> Берза проблем:
"Имајући у виду низ од н целих бројева, позитивна, нула, или негативан,
који представљају цену залиха преко н дана,
написати функцију за израчунавање максималног профита можете направити
с обзиром да сте купују и продају акције тачно 1 у оквиру ових н дана. "
Суштински, желимо да купимо низак, продајемо високо.
И ми желимо да откријемо најбољи профит можемо направити.
Враћајући се мој савет, шта је одмах јасно, најједноставније решење, али је спор?
Да? (Студент, неразумљив) >> Да.
>> Дакле, само да, иако иду и погледате цену акција
у сваком тренутку, (неразумљиво).
[Иу] Ок, па је њена решење - њен предлог рачунарства
најниже и највише израчунавања не мора нужно да ради
јер највише може доћи до најниже.
Дакле, шта је сирова снага решење за овај проблем?
Које су две ствари које морам да јединствено одреди добит сам направи? Тачно.
Бруте форце решење је - ох, тако, Џорџов предлог је да ми је потребно само два дана
да јединствено одреди добит та два дана.
Тако смо израчунати сваки пар, као купују / продају,
израчунати профит, који би могао бити негативан или позитиван или једнак нули.
Израчунати максималну профит који ћемо учинити после итератинг над свим паровима дана.
То ће бити наш коначни одговор.
И то решење ће бити О (н ^ 2), јер је н изабрати два пара -
дана које можете да одаберете између крајњих дана.
Ок, тако да ја не идем преко бруте форце решење овде.
Ја ћу да вам кажем да постоји н лог н решење.
Шта алгоритам ти тренутно знамо да је н лог н?
То није трик питање.
>> Обједињавање сортирање. Обједињавање врста је н лог н
и, у ствари, један од начина решавања овог проблема је да се користи
обједињавање врста врста идеје назива, уопште, завади па владај.
А идеја је као што следи.
Желите да израчуна најбољи купити / продати пар у левој половини.
Пронађите најбољу зараду можете направити, само са првим н преко два дана.
Онда желите да оомпуте најбоље купити / продати пар на десној половини,
тако да се посљедњи н преко два дана.
И сада се поставља питање, како да споји ова решења поново заједно?
Да? (Студент, неразумљив)
>> Реду. Дакле, дозволите ми да нацртате слику.
Да? (Џорџ, неразумљив)
>> Тачно. Џорџ решење је потпуно тачно.
Дакле, његов предлог је, најпре израчуна најбољи куповати / продавати пар,
и да се јавља у левој половини, па назовимо то лево, лево.
Најбоље купити / продати пар који се јавља у десној половини.
Али, ако смо само у поређењу ова два броја, ми недостаје случај
где смо ми овде купују и продају негде у десној половини.
Ми купују у левој половини, продати у десној половини.
А најбољи начин да се израчуна најбољи купити / продати пар који обухвата обе половине
је да се израчуна минимално овде и овде израчуна максимум
и заузму своје разлике.
Дакле, ова два случаја, где купити / продати пар јавља само овде,
само овде, или на оба полувремена је дефинисана ова три броја.
Дакле, наш алгоритам да споји наша решења поново заједно,
желимо да израчуна најбољи куповати / продавати пар
где смо купити на левој половини и продају на десној половини.
А најбољи начин за то је да се израчуна најнижу цену у првом полувремену,
највиша цена у десној половини, и преузму свој разлику.
Резултујући три профит, ове три броја, можете узети максимум три,
и то је најбоља зарада можете направити преко ових првих и крај дана.
Овде су важне линије су у црвеном.
Ово је рекурзивни позив да израчуна одговор на левој половини.
Ово је рекурзивни позив да израчуна одговор у десној половини.
Ове две петље за израчунавање МИН и МАКС на левој и десној половини, респективно.
Сада сам израчунати профит који обухвата обе половине,
и коначни одговор је максимум ове три.
Ок.
>> Па, наравно, имамо алгоритам, али веће питање је,
шта је време сложеност ово?
А разлог зашто сам поменуо стапања врсту јесте да је овај облик поделе одговор
на два и онда спајање наших решења поново заједно
Управо је облик стапања врсте.
Зато ме пусти да идем кроз време.
Ако бисмо дефинисали функцију Т (н) да буде број корака
за н дана,
наше две рекурзивни позиви
су, свака ће коштати Т (н / 2),
а ту је и две од ових позива.
Сада треба да израчунамо минимум левој половини,
што могу да урадим у Н / 2 времена, плус максимума десној половини.
Дакле, ово је само н.
А онда, плус неки сталном раду.
И ово понављање једначина
је управо рецидив једначина за стапања врсте.
А ми сви знамо да је обједињавање врста је н лог н време.
Дакле, наш алгоритам је такође н лог н време.
Да ли ово итерација смисла?
Само кратак рекапитулација ово:
Т (н) је број корака за израчунавање максималног профита
током н дана.
Начин на који смо раздвојили наше позиве рецурсиве
је позивом наше решење на првих н / 2 дана,
тако да је то један позив,
и онда смо поново позвати на другој половини.
Дакле, то је два позива.
И онда ћемо наћи минимум на левој половини, што можемо урадити у линеарном времену,
наћи највише десној половини, што можемо урадити у линеарном времену.
Дакле, н / 2 + н / 2 је само н.
Онда имамо нешто константан рад, који је као радио аритметике.
Ово понављање једначина је управо рецидив једначина за стапања врсте.
Дакле, наш алгоритам схуффле је н лог н.
Па колико простора смо користите?
Идемо назад у коду.
>> Боље питање је, колико стека оквири ми икада имати у сваком тренутку?
Пошто смо користите рекурзија,
број фрејмова стека одређује нашу свемирску употребу.
Размотримо н = 8.
Апелујемо на дволичност 8,
које ће позвати дволичност на прва четири ставке,
које ће позвати схуффле на прве две ставке.
Дакле, наша стек - ово је наш стек.
А онда зовемо дволичност поново на 1,
и то је оно што је наш случај база, тако да смо одмах врате.
Да ли ћемо икада имати више од тога многи стека рамова?
Не, јер сваки пут радимо призивање,
рекурзивни призивање на дволичност,
делимо нашу величину на пола.
Дакле, максималан број фрејмова стека ми икада имати у сваком тренутку
је по налогу лог н стек оквире.
Сваки стек оквир има сталан простор,
а самим тим и укупан износ простора,
максимална количина простора који смо икада користили је О (лог н) простора
где је н број дана.
>> Сада, увек запитајте се: "Да ли можемо да урадимо боље?"
И посебно, можемо смањити то проблем смо већ решен?
Хинт: ми смо само разговарали два проблема пре овога, а то неће бити схуффле.
Можемо конвертује овај проблем берзе у максималном субарраи проблема.
Како можемо да урадимо ово?
Један од вас? Еми?
(Еми, неразумљив)
[Иу] Управо тако.
Дакле максималног субарраи проблема,
тражимо суме преко континуираног субарраи.
И Еми Предлог за проблем залиха,
разматра измене, односно о ушћа.
А слика је - то је цена једне акције,
али ако смо узели разлику између сваког узастопног дана -
па видимо да је максимална цена, максимална добит могли бисмо
је, ако ми овде купују и продају овде.
Али, хајде да погледамо континуирано - хајде да погледамо субарраи проблема.
Дакле, овде можемо направити - иде одавде до овде,
имамо позитивну промену, а онда иде одавде до овде имамо негативну промену.
Али онда, иде одавде до овде имамо огромну позитивну промену.
А то су промене које желимо да сумирамо да крајњи профит.
Онда имамо овде више негативних промена.
Кључ за смањење наше берзе проблем у нашој максималне субарраи проблема
је да размотри делти између дана.
Тако смо направили нови низ зове делти,
покрене први унос да буде 0,
и онда за сваки троугао (и), нека то буде разлика
мог улаза низ (и), арраи (и - 1).
Онда ћемо позвати нашу рутинску процедуру за максималну субарраи
пролази у низу једног Делтина.
И зато максимална субарраи је линеарно време,
и то смањење, овај процес стварања ове делта низ,
је линеарно време,
онда коначно решење за акције је О (н) раде, плус О (н) рад, још увек је О (н) рад.
Дакле, имамо линеарно време решење за наш проблем.
Да ли сви разумеју ову трансформацију?
>> У принципу, добра идеја да увек треба имати
се покуша да се смањи нови проблем који сте виде.
Ако изгледа познато старом проблему,
покушате да смањите га на стари проблем.
А да ли можете да користите све алате које сте користили на старом проблему
да реши нови проблем.
Тако да заврши, технички разговори су изазов.
Ови проблеми су вероватно неки од тежих проблема
које можете видети у интервјуу,
па ако не разумете све проблеме које сам покривена, то је у реду.
Ово су неке од изазова проблеме.
Пракса, пракса, пракса.
Дао сам доста проблема у уручења, тако да дефинитивно проверите оне оут.
И срећно на својим интервјуима. Сви моји извори су постављене на овом линку,
и један од мојих старијих пријатеља је понудио да уради лажне техничке разговоре,
па ако сте заинтересовани, е-маил ће Иао на тој емаил адресу.
Ако имате нека питања, можете ме питати.
Да ли ви имате конкретна питања у вези са техничким разговорима
или неки проблеми које смо видели до сада?
Ок. Па, срећно на својим интервјуима.
[ЦС50.ТВ]