[Powered by Google Translate] [Семінар: Тэхнічныя Інтэрв'ю] [Kenny Ю., Гарвардскі універсітэт] [Гэта CS50.] [CS50.TV] Прывітанне ўсім, я Кені. У цяперашні час я малодшы, якія вывучаюць інфарматыку. Я былы CS TF, і я б хацеў гэтага, калі я быў студэнт першага або другога курсу, і менавіта таму я даю гэты семінар. Так што я спадзяюся, вам спадабаецца. Гэты семінар аб тэхнічных інтэрв'ю, і ўсе мае рэсурсы можна знайсці па гэтай спасылцы, спасылку прама тут, пару рэсурсаў. Таму я склаў спіс праблем, на самай справе, даволі шмат праблем. Акрамя таго, агульнае старонкі рэсурсаў, дзе можна знайсці парады пра тое, як падрыхтавацца да сумоўя, парады аб тым, што вы павінны зрабіць на працягу фактычнага інтэрв'ю, а таксама, як падыходзіць да праблем і рэсурсы для далейшага выкарыстання. Гэта ўсё он-лайн. І каб апярэдзіць гэты семінар, адмова, як гэта не варта - ваша падрыхтоўка да інтэрв'ю не павінны быць абмежаваныя ў гэты спіс. Гэта толькі азначае, што кіраўніцтва, і вы павінны абавязкова ўзяць усё, што я кажу з збожжам солі, але і выкарыстоўваць усе, што я выкарыстаў, каб дапамагчы вам у вашай падрыхтоўцы да інтэрв'ю. 

Я хачу, каб паскорыць працягу наступных некалькіх слайдах так што мы можам дабрацца да фактычнага даследаванняў. Структура інтэрв'ю постион распрацоўкі праграмнага забеспячэння, Звычайна яна складае ад 30 да 45 хвілін, некалькі раўндаў, у залежнасці ад кампаніі. Часта вы будзеце кадавання на белай дошцы. Такім чынам, белая дошка, як гэта, але часта і ў меншых маштабах. Калі ў вас інтэрв'ю па тэлефоне, вы будзеце, верагодна, выкарыстоўваць альбо collabedit або Google Doc каб яны маглі бачыць вы жывяце кадавання а вы ў час інтэрв'ю па тэлефоне. Інтэрв'ю сабе, як правіла, 2 ці 3 праблемы тэставанне кампутара навуковых ведаў. І гэта будзе амаль дакладна звязаны з кадаваньне. Тыпы пытанняў, якія вы ўбачыце, як правіла, структуры дадзеных і алгарытмы. І пры гэтым гэтыя віды праблем, яны будуць прасіць вас, быццам бы, колькі часу і прасторы складанасць, вялікія O? Часта яны таксама просяць больш высокім узроўні пытанні, Такім чынам, праектаванне сістэмы, Як бы вы выкласці код? Якія інтэрфейсы, якія класы, якія модулі ў вас ёсць у вашай сістэме, і як яны ўзаемадзейнічаюць адзін з адным? Такім чынам, структуры дадзеных і алгарытмы, а таксама праектаванне сістэм. 

Некаторыя агульныя парады Перш чым мы паглыбімся ў нашы тэматычныя даследаванні. Я думаю, што самае важнае правіла заўсёды думаць услых. Інтэрв'ю павінна быць ваш шанец паказаць свой разумовы працэс. Справа ў інтэрв'ю для інтэрв'юера, каб вымераць як вы думаеце, і як вы ідзяце праз праблеме. Горшае, што вы можаце зрабіць, гэта маўчаць на працягу ўсяго інтэрв'ю. Вось толькі нічога добрага. Калі вы атрымліваеце пытанне, вы таксама хочаце, каб пераканацца, што вы зразумелі пытанне. Так што паўтару пытанне яшчэ ў свае словы і спроба працаваць дбайнай некалькі простых тэстаў пераканайцеся, што вы зразумелі пытанне. Праца праз некалькі тэстаў таксама дасць вам інтуіцыя аб тым, як вырашыць гэтую праблему. Вы нават можаце адкрыць для сябе некалькі мадэляў, каб дапамагчы вам вырашыць гэтую праблему. Іх вялікія чаявыя, каб не хвалявацца. Не хвалюйцеся. Інтэрв'ю з'яўляюцца складанымі, але горшае, што вы можаце зрабіць, У дадатак да таго, маўчыць, павінна быць відавочна расчараваныя. Вы ж не хочаце, каб даць ўражанне, што інтэрв'юер. Адна рэч, якую вы - так, многія людзі, калі яны ідуць у інтэрв'ю, яны спрабуюць, каб паспрабаваць знайсці лепшае рашэнне першай, калі на самай справе, там звычайна відавочныя рашэнне. Гэта можа быць павольным, яно можа быць неэфектыўным, але вы павінны проста канстатаваць гэта, проста так у вас ёсць адпраўная кропка, з якой можна працаваць лепш. Акрамя таго, паказваючы на ​​рашэнне павольна, з пункту гледжання вялікі час O складанасці або прастору складанасці, будзе прадэманстраваць інтэрв'юеру, што вы разумееце, гэтыя пытанні пры напісанні кода. Так што не бойцеся прыдумаць найпросты алгарытм спачатку , А затым працаваць лепш адтуль. Любыя пытанні да гэтага часу? Добра. 

Так што давайце пагрузіцца ў нашу першую задачу. "Улічваючы масіў цэлых лікаў п, напісаць функцыю, якая тасуе масіва на месца так, што ўсе перастаноўкі лікаў п аднолькава верагодныя. " І выкажам здагадку, у вас маецца генератар выпадковых цэлых , Які генеруе цэлы лік у дыяпазоне ад 0 да я, палову дыяпазону. Ці ўсё разумеюць гэтае пытанне? Я даю вам масіў цэлых лікаў п, і я хачу, каб змяшаць. У маім каталогу, я напісаў некалькі праграм, каб прадэманстраваць, што я маю на ўвазе. Я збіраюся змяшаць масіў з 20 элементаў, ад -10 да 9, і я хачу, каб вы вывесці спіс, як гэта. Так што гэта мой адсартаваны масіў зыходных дадзеных, і я хачу, каб ты змяшаць. Мы зробім гэта зноў. Ці ўсё разумеюць, у чым пытанне? Добра. Так што гэта залежыць ад вас. Якія ідэі? Вы можаце зрабіць гэта пры п ^ 2, п § п, п? Адкрыты для прапаноў. Добра. Так што ідэя, прапанаваная Эмі, 1. вылічыць выпадковае лік, выпадковае лік, у дыяпазоне ад 0 да 20. Такім чынам, выкажам здагадку, наш масіў мае даўжыню 20. У нашай схеме 20 элементаў, гэта наш ўваходны масіў. І цяпер, яе прапанова з'яўляецца стварэнне новага масіва, так што гэта будзе выхадны масіў. І на аснове я вярнуўся на рандаў - так што калі б я быў, скажам, 17, скапіяваць 17 элементаў у першай пазіцыі. Цяпер нам трэба выдаліць - мы павінны перакласці ўсе элементы тут над тым, што ў нас ёсць прабел у канцы і без адтулін у сярэдзіне. І зараз мы паўтараем працэс. Цяпер мы выбіраем новае выпадковы лік паміж 0 і 19. У нас ёсць новая я тут, і мы капіяваны гэты элемент у гэтай пазіцыі. Затым мы пераходзім элементы зноў і паўтарыць працэс, пакуль у нас ёсць поўны новага масіва. Што такое час выканання гэтага алгарытму? Ну, давайце разгледзім наступствы гэтага. Мы пераходзім кожнага элемента. Калі мы выдаляем гэта я, мы пераходзім ўсе элементы пасля яго налева. І гэта O (п) кошт таму што, калі мы выдаляем першы элемент? Такім чынам, для кожнага выдалення, мы выдаляем - кожнае выдаленне нясе O (N) аперацый, і так як мы маем п абсорбцыі, гэта прыводзіць да O (N ^ 2) змяшаць. Добра. Так што добры пачатак. Добры пачатак. 

Іншая прапанова заключаецца ў выкарыстанні нешта, вядомае як пустую Кнута, або Fisher-Yates Shuffle. І гэта на самай справе лінейнага мяшання часу. А ідэя вельмі падобная. Зноў жа, у нас ёсць ўваходны масіў, але замест двух масіваў для нашых ўводу / вываду, мы выкарыстоўваем першую частку масіва сачыць за нашымі ператасаваць частка, і мы адсочваем, і тады мы пакінуць астатнюю частку нашага масіва для unshuffled частку. Такім чынам, вось што я маю на ўвазе. Мы пачынаем з - мы выбіраем я, масіў ад 0 да 20. Наш бягучы паказальнік паказвае на першы індэкс. Абярэм некаторы я тут і зараз мы перастаўляць. Так што, калі гэта было 5, і гэта было 4, выніковы масіў будзе мець 5 Тут і 4 тут. А зараз звярніце ўвагу маркерам тут. Усе злева тасуецца, і ўсё, што права unshuffled. І зараз мы можам паўтарыць працэс. Мы абярэм выпадковым індэксам ад 1 да 20 у цяперашні час. Такім чынам, хай наш новы я тут. Цяпер мы перастаўляць гэтым я з нашым бягучых новае палажэнне тут. Таму мы перапампоўкі наперад і назад, як гэта. Дазвольце мне падняць код, каб зрабіць яго больш канкрэтным. Пачнем з нашым выбарам я - Мы пачынаем з я роўная 0, мы выбіраем выпадковае размяшчэнне J У unshuffled частка масіва, я да п-1. Так што, калі я тут, абраць выпадковы індэкс паміж тут і астатняя частка масіва, і мы перастаўляць. Гэта ўвесь код, неабходны для мяшання масіва. Ёсць пытанні? 

Ну, адзін неабходны пытанне, чаму гэта правільна? Чаму ўсе перастаноўкі равновероятны? І я не буду доказ гэтага, але шматлікія праблемы ў галіне кампутарных навук можа быць даказана шляхам індукцыі. Як многія з вас ужо знаёмыя з індукцыяй? Добра. Cool. Такім чынам, вы можаце даказаць правільнасць гэтага алгарытму просты індукцыі, дзе ваша індукцыі бы, выкажам здагадку, што мой выпадковым парадку вяртае ўсе перастаноўкі равновероятны да першага элемента я. Зараз разгледзім + 1. І, дарэчы, мы выбіраем нашых індэксаў J, каб памяняць, гэта прыводзіць да - і тады вы прапрацаваць дэталі, па крайняй меры, поўнае доказ таго, чаму гэты алгарытм вяртаецца кожная перастаноўка з роўнай верагоднасцю верагоднасці. 

Добра, наступная праблема. Так што "гэты масіў цэлых лікаў, Postive, нулявы, адмоўны, напісаць функцыю, якая вылічае максімальную суму любой continueous подмассива ўваходны масіў ". Напрыклад вось, у выпадку, калі ўсе лікі станоўчыя, то ў цяперашні час лепшы выбар гэта ўзяць увесь масіў. 1, 2, 3, 4, роўна 10. Калі ў вас ёсць некаторыя негатывы там, У гэтым выпадку мы проста хочам першых двух таму што выбар -1 і / або -3 прынясе нашым сума ўніз. Часам мы, магчыма, прыйдзецца пачаць у сярэдзіне масіва. Часам мы хочам выбраць наогул нічога, то лепш не браць. І часам лепш прыняць восенню, таму што рэч пасля таго, як гэта супер вялікі. Такім чынам, любыя ідэі? (Студэнт, незразумелыя) >> Так. Няхай я не бяру -1. Тады альбо я выбіраю 1000 і 20000, ці я проста абраць 3 млрд. даляраў. Ну, лепшым выбарам будзе прымаць усе лічбы. Гэта -1, нягледзячы на ​​тое адмоўнае, Уся сума лепш, чым калі б я не прымаць -1. Такім чынам, адзін з саветаў я згадваў раней быў заявіць ясна відавочна, і грубай сіле рашэнне першай. Што такое грубай сілы ў вырашэнні гэтай праблемы? Да? [Джэйн] Ну, я думаю, што грубай сіле рашэнне можна было б дадаць ўсе магчымыя камбінацыі (неразборліва). [П] Добра. Такім чынам, ідэя Джэйн прыняць усе магчымыя - Я Перафразую - гэта прыняць усе магчымыя бесперапыннай подмассива, вылічыць яго суму, а затым ўзяць максімальнае з усіх магчымых бесперапынных подмассивов. Што адназначна ідэнтыфікуе подмассива ў маёй ўваходны масіў? Як і тое, што дзве рэчы мне патрэбныя? Да? (Студэнт, незразумелыя) >> праве. Ніжняя мяжа індэксаў і верхняя мяжа індэкса адназначна вызначае бесперапынную подмассива. [Студэнтка] Ці мы ацаніць гэта масіў унікальных нумароў? [П] Няма Таму яе пытанне, мы мяркуючы, наш масіў - Наша масіва ўсе унікальныя нумары, а адказу няма. 

Калі мы выкарыстоўваем нашу грубую сілу рашэнне, то пачатак / канец індэксаў адназначна вызначае нашы пастаянныя подмассива. Таму, калі мы перабору ўсіх магчымых запісаў пачатку, і для ўсіх канчатковых элементаў> ці =, каб пачаць, і <п, Вы можаце вылічыць суму, а затым ўзяць максімальную суму, што мы бачылі да гэтага часу. Гэта зразумела? Што такое вялікае Аб ад гэтага рашэння? Timewise. Не зусім N ^ 2. Звярніце ўвагу, што мы ітэрацыі ад 0 да п, так што адна цыклу. Мы зноў паўтараць практычна з пачатку і да канца, іншага цыклу. І зараз, у тым, што мы павінны падвесці вынікі кожнага ўваходу, так што гэта яшчэ адзін цыкл. Такім чынам, мы маем тры укладзеныя цыклы, п ^ 3. Добра. Гэта ідзе ў якасці адпраўной кропкі. Наша рашэнне не горш, чым п ^ 3. Ці ўсё разумеюць грубую сілу рашэнне? 

Добра. Лепшым рашэннем з'яўляецца выкарыстанне ідэі называюць дынамічным праграмаваннем. Калі ўзяць CS124, якая алгарытмы і структуры дадзеных, Вы станеце вельмі добра знаёмыя з гэтай тэхнікай. І ідэя, паспрабаваць стварыць рашэнні для меншых праблем у першую чаргу. Што я маю на ўвазе, мы ў цяперашні час не прыйдзецца турбавацца пра дзве рэчы: пачатак і канец. І гэта раздражняе. Што калі б мы маглі пазбавіцца ад аднаго з гэтых параметраў? Адна з ідэй складаецца - we're улічваючы нашу зыходную задачу, знайсці максімальную суму любых подмассива ў дыяпазоне [О, N-1]. І зараз у нас ёсць новы подзадачи, дзе мы ведаем, у нашай бягучай індэкс г, Мы ведаем, што мы павінны заключыць там. Нашы подмассива павінны заканчвацца на бягучы індэкс. Такім чынам, што засталася, праблема ў тым, дзе мы павінны пачаць наш подмассива? Ці мае гэта сэнс? Добра. Так што я закадаваны ад гэтага, і давайце паглядзім, што гэта азначае. У codirectory, ёсць праграма пад назвай подмассива, і ён прымае лік элементаў, і вяртае максімальную суму подмассива ў маім спісе змешваюцца. Такім чынам, у гэтым выпадку, наш максімальны подмассива роўны 3. І гэта прымаць толькі з дапамогай 2 і 1. Давайце запусцім яго зноў. Гэта таксама 3. Але на гэты раз, звярніце ўвагу, як мы атрымалі 3. Мы ўзялі - мы проста возьмем 3-сам таму што ён акружаны негатываў з абодвух бакоў, які прынясе суму <3. Давайце працаваць на 10 пунктаў. На гэты раз гэта 7, заняць лідзіруючыя 3 і 4. На гэты раз гэта 8, і мы атрымліваем, што, прымаючы 1, 4 і 3. Такім чынам, каб даць вам інтуіцыя аб тым, як мы можам вырашыць гэтую ператвараецца праблемы, Давайце зірнем на гэтую подмассива. Мы дадзена гэта ўваходны масіў, і мы ведаем адказ на гэтае пытанне 8. Мы бярэм 1, 4 і 3. Але давайце паглядзім на тое, як мы на самай справе ёсць, што адказаць. Давайце паглядзім на максімальнай подмассива, які скончыўся на кожны з гэтых паказчыкаў. Які максімальны подмассива, які павінен скончыцца на першай пазіцыі? [Студэнт] Zero. >> Zero. Толькі не прымайце -5. Вось гэта будзе мець значэнне 0, а таксама. Да? (Студэнт, незразумелыя) [П] Эх, шкада, што гэта -3. Такім чынам, гэта 2, гэта -3. Добра. Такім чынам, -4, што максімальная подмассива да канца, што становішча -4, Дзе знаходзіцца? Zero. Адзін? 1, 5, 8. Цяпер, я павінен заканчвацца ў тым месцы, дзе -2 знаходзіцца. Такім чынам, 6, 5, 7, а апошні роўны 4. Ведаючы, што гэтыя мае запісы для ператворанай задачы, дзе я павінен заканчвацца на кожны з гэтых паказчыкаў, Затым мой канчатковы адказ проста, узяць разгорткі па гарызанталі, і ўзяць максімальнае колькасць. Такім чынам, у дадзеным выпадку гэта 8. Гэта азначае, што максімальная подмассива заканчваецца ў гэтым індэксе, і пачаў дзесьці перад ім. Ці ўсё разумеюць гэта ператвараецца подмассива? 

Добра. Ну, давайце высвятляць паўтарэння гэтага. Давайце разгледзім толькі першыя некалькі запісаў. Дык вось гэта была 0, 0, 0, 1, 5, 8. А потым было -2 тут, і якія прывялі яго да 6. Так што, калі я называю ўступлення ў пасаду я подзадача (I), як я магу выкарыстоўваць адказе на папярэдні подзадачи Для адказу на гэтае подзадачи? Калі я гляджу на, скажам, гэты запіс. Як я магу вылічыць адказ 6, гледзячы на Спалучэнне гэтага масіва і адказаў на папярэднія подзадач ў гэтым масіве? Да? [Студэнтка] Ты масіве сум у становішча прама перад ёй, так што 8, а затым дадаць бягучую подзадачи. [П] Так ёй прапанову паглядзець на гэтыя два ліку, гэты лік, і гэта лік. Такім чынам, гэта 8 ставіцца да адказам на подзадачи (я - 1). І давайце называць майго уваходнага масіва A. Для таго каб знайсці максімальны подмассива, які заканчваецца ў пазіцыі I, У мяне ёсць два варыянты: я магу альбо працягнуць подмассива , Якая скончылася ў папярэдні індэкс, або пачаць новую масіва. Калі б я быў працягнуць подмассива, які пачаўся ў папярэдні індэкс, Затым максімальную суму я магу дасягнуць, гэта адказ на папярэдні подзадачи плюс бягучы элемент масіва. Але, у мяне ёсць выбар, пачынаючы новы подмассива, У гэтым выпадку сума роўная 0. Так што адказ макс 0, подзадача - 1, а таксама бягучы элемент масіва. Ці азначае гэта паўтор сэнсу? Нашы рэцыдыву, як мы толькі што выявілі, гэта я подзадача роўны максімуме папярэдняга подзадачи плюс мой бягучы элемент масіва, што азначае працяг папярэдняй подмассива, або 0, стварыць новую подмассива на мой бягучы індэкс. І як толькі мы стварылі гэтую табліцу рашэнняў, то наш канчатковы адказ, проста рабіць лінейныя разгорткі праз подзадачи масіва і ўзяць максімальнае колькасць. Гэта дакладная рэалізацыя таго, што я толькі што сказаў. Такім чынам, мы ствараем новы масіў подзадачи, подзадачи. Першая запіс альбо 0, альбо першы запіс, максімальнае з гэтых двух. А для астатніх подзадач мы выкарыстоўваем дакладнае паўтарэнне Мы толькі што выявілі. Цяпер вылічым максімальную нашага масіва подзадач, і гэта наш канчатковы адказ. 

Так колькі месца мы выкарыстоўваем у гэтым алгарытме? Калі вы толькі прымаць CS50, то вы не маглі б абмяркоўвацца прасторы вельмі шмат. Ну, адно варта адзначыць, што я назваў таНос тут з памерам п. Што гэта прапанаваць вам? Гэты алгарытм выкарыстоўвае лінейнае прастору. Ці можам мы зрабіць лепш? Ёсць што-небудзь, што вы заўважыце, што з'яўляецца неабходным для вылічэнні канчатковы адказ? Я думаю, лепш Пытанне ў тым, якая інфармацыя мы не павінны несці ўвесь шлях да канца? Цяпер, калі мы паглядзім на гэтыя дзве лініі, мы клапоцімся толькі пра папярэднюю подзадачи, і мы клапоцімся толькі пра максімальнай якія мы калі-небудзь бачылі да гэтага часу. Каб вылічыць наш канчатковы адказ, нам не трэба ўвесь масіў. Нам трэба толькі апошні нумар, дзве апошнія лічбы. Апошні нумар подзадачи масіва, а апошні нумар максімуму. Так, на самай справе, мы можам злучыць гэтыя завесы разам і перайсці ад лінейнага прасторы пастаяннай прасторы. Дадзенай сумы да гэтага часу, тут замяняе ролю подзадачи, нашы подзадачи масіва. Такім чынам, бягучая сума, да гэтага часу, з'яўляецца адказам на папярэдні подзадачи. І гэтая сума да гэтага часу займае месца нашага макс. Мы вылічым максімальную, як мы ідзем разам. І вось мы ідзём ад лінейнага прасторы пастаяннай прасторы, і мы таксама маем лінейнае рашэнне нашых подмассива праблемы. 

Гэтыя пытанні вы атрымаеце падчас інтэрв'ю. Якая часовая складанасць, што прастора складанасці? Ці можаце вы зрабіць лепш? Ёсць рэчы, якія не з'яўляюцца неабходнымі, каб трымаць вакол? Я зрабіў гэта, каб вылучыць аналізаў, якія вы павінны прыняць на свой уласны як вы працуеце праз гэтыя праблемы. Заўсёды можна спытаць сябе: "Ці магу я зрабіць лепш?" На самай справе, мы можам зрабіць лепш, чым гэта? Сартаваць пытанне з падвохам. Вы не можаце, таму што вы павінны па крайняй меры чытаць ўклад у праблему. Таму той факт, што вам трэба па крайняй меры чытаць ўклад у праблемы азначае, што вы не можаце зрабіць лепш, чым лінейнае час, і вы не можаце зрабіць лепш, чым пастаяннае месца. Так што гэта, на самой справе, лепшае рашэнне гэтай праблемы. Пытанні? Добра. 

Праблема Фондавы рынак: "Улічваючы масіў цэлых лікаў п, станоўчай, нулявы або адмоўнай, , Якія ўяўляюць сабой цану акцыі на працягу некалькіх дзён п, напісаць функцыю для вылічэння максімальнай прыбытку вы можаце зрабіць пры ўмове, што вы купляеце і прадаеце роўна 1 акцыя ў рамках гэтых п дзён ". Па сутнасці, мы хочам купіць танна, прадавай дорага. І мы хочам, каб высветліць, лепшы прыбытку мы можам зрабіць. Вяртаючыся да маёй наканечнікам, што адразу ясна, просты адказ, але гэта павольна? Да? (Студэнт, незразумелыя) >> Так. >> Так вы б проста пайсці, хоць і паглядзіце на цэны акцый у кожны момант часу, (неразборліва). [П] Добра, так што яе рашэнне - яе прапанову вылічальных самыя нізкія і самыя высокія вылічэнні не абавязкова працаваць таму што высокая можа адбыцца да самых нізкіх. Так што гэта грубая сіла рашэння гэтай праблемы? Якія дзве рэчы, якія мне трэба, каб адназначна вызначыць прыбытак я магу зрабіць? Права. Рашэнне грубай сілы - о, так, прапанова Джорджа гэта нам трэба толькі два дні для адназначнага вызначэння прыбытку гэтыя два дні. Такім чынам, мы вылічым кожнай пары, як купля / продаж, вылічыць прыбытак, якая можа быць станоўчым або адмоўным або нулявым. Вылічыць максімальны прыбытак, што мы робім пасля перабірае ўсе пары дзён. Гэта будзе наш канчатковы адказ. І гэтае рашэнне будзе O (N ^ 2), таму што існуе п выбраць дзве пары - дзён, якія вы можаце выбіраць паміж канца дня. Добра, так што я не збіраюся перайсці на грубай сіле рашэнне тут. Я збіраюся расказаць вам, што ёсць п § п рашэнне. Які алгарытм ў цяперашні час вы ведаеце, што гэта п § п? Гэта не пытанне з падвохам. 

Зліццё роду. Зліццё роду п § п, і на самай справе, адным з спосабаў вырашэння гэтай праблемы з'яўляецца выкарыстанне свайго роду зліццё роду ідэя называецца, у агульным, падзяляй і ўладар. А ідэя заключаецца ў наступным. Вы хочаце, каб вылічыць аптымальную куплі / продажу пары ў левай палове. Знайсці лепшы прыбытку вы можаце зрабіць, толькі з першай рускай працягу двух дзён. Затым вы хочаце oompute лепшыя куплі / продажу пары на правай палове, так што апошнія п працягу двух дзён. А зараз пытанне ў тым, як мы можам аб'яднаць гэтыя рашэнні разам? Да? (Студэнт, незразумелыя) >> Добра. Такім чынам, дазвольце мне намаляваць карцінку. Да? (Джордж, незразумелыя) >> Менавіта так. Рашэнне Джорджа гэта зусім дакладна. Так што яго прапанова з'яўляецца, у першую вылічыць аптымальную куплю / продаж пары, і што адбываецца ў левай палове, так што давайце называць гэта левы, левы. Лепшая купля / продаж пара, якая адбываецца ў правай палове. Але калі мы толькі па параўнанні гэтых двух лікаў, мы прапусцілі выпадак дзе купіць тут і прадаць дзесьці ў правай палове. Мы купляем у левай палове, продажу ў правай палове. І лепшы спосаб вылічыць аптымальную купіць / прадаць пару, якая ахоплівае абедзве палоўкі з'яўляецца вылічэнне мінімальнага тут і вылічыць максімальнае тут і ўзяць іх рознасць. Такім чынам, два выпадкі, калі куплі / продажу пары адбываецца толькі тут, Толькі тут, ці на абедзвюх палавінах вызначаецца гэтымі трыма лікамі. Такім чынам, наш алгарытм аб'яднаць нашы рашэнні разам, Мы хочам вылічыць аптымальную куплю / продаж пары дзе мы купляем на левай палове і прадаваць на правай палове. І лепшы спосаб зрабіць гэта складаецца ў вылічэнні самай нізкай цане ў першай палове, самая высокая цана ў правай палове, і ўзяць іх рознасць. Атрыманыя 3 прыбытак, гэтыя тры лічбы, вы бераце максімум тры, і гэта лепшая прыбытак вы можаце зрабіць за гэтыя першыя і канца дзён. Тут важныя лініі чырвонага колеру. Гэта рэкурсіўны выклік для вылічэнні адказу ў левай палове. Гэта рэкурсіўны выклік для вылічэнні адказу ў правай палове. Гэтыя дзве завесы для вылічэнні мін і макс на левую і правую паловы, адпаведна. Цяпер я вылічыць прыбытак, якая ахоплівае абедзве палоўкі, і канчатковы адказ максімальная з гэтых трох. Добра. 

Так што, упэўнены, у нас ёсць алгарытм, але больш за пытанне ў тым, што часовая складанасць гэтага? І прычына, чаму я згадаў, сартаванне зліццём у тым, што гэтая форма падзяліць адказ на два, а затым аб'ядноўваць нашы рашэнні разам Менавіта выгляд сартавання зліццём. Такім чынам, дазвольце мне прайсці працягласці. Калі мы вызначылі функцыю T (N), што колькасць крокаў для п дзён, нашы рэкурсіўнага выклікі кожны будзе каштаваць т (п / 2), і ёсць два з гэтых выклікаў. Цяпер мне трэба вылічыць мінімум левай палове, які я магу зрабіць у п / 2, плюс максімум у правай палове. Так што гэта проста п. А потым плюс некаторая пастаянная праца. І гэта рэкурэнтнага раўнанне Менавіта рэкурэнтнага раўнанне для сартавання зліццём. І ўсе мы ведаем, што сартаванне зліццём п § п часу. Такім чынам, наш алгарытм таксама п § п часу. Ці значыць гэта, ітэрацыі сэнс? Толькі кароткае рэзюмэ гэтага: Т (п) з'яўляецца шэраг крокаў, каб вылічыць максімальны прыбытак на працягу сутак з. Тое, як мы падзяліліся нашы рэкурсіўнага выклікі з'яўляецца выклікам нашага рашэння ў першыя дні п / 2, так што гэта адзін выклік, а потым мы зноў заклікаем другой паловы. Дык вось двума выклікамі. І тады мы знаходзім мінімум на левай палове, якую мы можам зрабіць у лінейным часу, знайсці максімум у правай палове, якую мы можам зрабіць у лінейным часу. Такім чынам, п / 2 + п / 2 знаходзіцца за ўсё ў с. Тады ў нас ёсць пастаянная праца, якая, як рабіць арыфметыку. Гэта рэкурэнтнага раўнанне ў дакладнасці паўтарэння раўнанні для сартавання зліццём. Такім чынам, наш алгарытм мяшання таксама п п ўвайсці. Так колькі месца мы выкарыстоўваем? Давайце вернемся да коду. 

Лепшы пытанне, колькі кадраў стэка мы калі-небудзь у любы момант? Так як мы выкарыстоўваем рэкурсіі, колькасць кадраў стэка вызначае наша выкарыстанне прасторы. Разгледзім N = 8. Мы заклікаем змяшаць 8, , Які будзе выклікаць выпадковым парадку на першых чатырох запісаў, , Які будзе выклікаць перамешванне на першых двух запісаў. Такім чынам, наш стэк - гэта наш стэк. І тады мы называем змяшаць яшчэ раз на 1, і гэта тое, што наша база выпадак, таму мы неадкладна вярнуцца. Ці ёсць у нас калі-небудзь больш, чым гэта колькасць кадраў стэка? Не, таму што кожны раз, калі мы робім выклік, рэкурсіўны выклік для мяшання, мы дзелім нашу памерам у палову. Такім чынам, максімальны лік кадраў стэка мы калі-небудзь у любы момант парадку часопіса N кадраў стэка. Кожны кадр стэка мае пастаяннае месца, і, такім чынам, агульны аб'ём прасторы, максімальны аб'ём прасторы, мы калі-небудзь выкарыстоўваць гэта O (часопіс N) прасторы дзе п-колькасць дзён. 

Цяпер, заўсёды пытайце сябе: "Ці можам мы зрабіць лепш?" І ў прыватнасці, мы можам скараціць гэтую праблему мы ўжо вырашылі? Падказка: мы толькі абмяркоўвалі два іншых праблем да гэтага, і ён не збіраецца быць змяшаць. Мы можам пераўтварыць гэтую праблему фондавага рынку ў максімальнай праблемы подмассива. Як мы можам гэта зрабіць? Адзін з вас? Эмі? (Emmy, незразумелыя) [П] Менавіта так. Такім чынам, максімальная подмассива праблемы, Мы шукаем сума па бесперапыннай подмассива. І прапанова Эмі задачы акцыі, Разгледзім змены, або дэльты. І карціна гэтая ёсць - гэта кошт акцыі, але калі б мы ўзялі розніцу паміж кожным дзень запар - Такім чынам, мы бачым, што максімальная цана, максімальная прыбытак мы маглі б зрабіць , Калі мы купляем і прадаем тут тут. Але давайце паглядзім на бесперапыннае - давайце паглядзім на подмассива праблемы. Дык вось, мы можам зрабіць - адбываецца ад гэтага да гэтага, у нас ёсць пазітыўныя змены, а затым збіраецца адсюль тут мы маем адмоўнае змена. Але тады, пераходзячы ад сюды, каб тут мы маем велізарнае станоўчае змяненне. І гэтыя змены, якія мы хочам падвесці вынікі, каб атрымаць нашу канчатковую прыбытак. Тады ў нас больш негатыўных зменаў тут. Ключ да зніжэння нашым складзе праблемай у нашай максімальнай праблемы подмассива з'яўляецца разгляд дэльты паміж дзён. Такім чынам, мы ствараем новы масіў з імем дэльты, ініцыялізацыя першага элемента роўным 0, а затым для кожнай дэльты (I), няхай гэта будзе розніца маёй ўваходны масіў (I), і масіў (я - 1). Тады мы называем нашай руціннай працэдурай для максімальнага подмассива якая праходзіць у масіве дэльты. І таму, што максімальная подмассива з'яўляецца лінейным часам, і гэта скарачэнне, гэты працэс стварэння гэтай дэльты масіва, Таксама лінейнага часу, то канчатковае рашэнне запасаў O (п) плюс праца O (п) работы, па-ранейшаму O (п) працы. Таму ў нас ёсць лінейнае час вырашэння нашай праблемы. Ці ўсё разумеюць гэта пераўтварэнне? 

Увогуле, добрая ідэя, што вы заўсёды павінны мець гэта паспрабаваць паменшыць новая праблема, што вы бачыце. Калі яно выглядае знаёма старая праблема, паспрабуйце паменшыць яго старая праблема. І калі вы можаце выкарыстоўваць усе інструменты, якія вы выкарыстоўвалі на старыя праблемы для вырашэння новай праблемы. Такім чынам, каб падводзіць вынікі, тэхнічнае інтэрв'ю складанай задачай. Гэтыя праблемы, верагодна, некаторыя з найбольш складаных праблем што вы можаце ўбачыць у адным з інтэрв'ю, так што калі вы не разумееце, усе праблемы, якія я толькі пакрытыя, гэта нармальна. Вось некаторыя з найбольш складаных праблем. Практыка, практыка, практыка. Я дала шмат праблем у раздатачны матэрыял, так вызначана праверыць гэтыя. І поспеху на інтэрв'ю. Усе мае рэсурсы, размешчаныя на гэтую спасылку, і адзін з маіх старэйшых сяброў прапанаваў зрабіць макет тэхнічнае інтэрв'ю, так што калі вы зацікавіліся, ліст будзе Яо, што адрас электроннай пошты. Калі ў вас ёсць пытанні, вы можаце спытаць мяне. Як вы, хлопцы, ёсць канкрэтныя пытанні, звязаныя з тэхнічнымі інтэрв'ю або любыя праблемы, якія мы бачылі да гэтага часу? Добра. Ну, поспеху на інтэрв'ю. [CS50.TV]