[Powered by Google Translate] [Семинар на тема: Технически Интервюта] [Кени Ю, Харвардския университет] [Това е CS50. [CS50.TV] Здравейте всички, аз съм Кени. В момента съм младши учи компютърни науки. Аз съм бивш CS TF, и Бих искал да имам това, когато бях на underclassman, и затова давам този семинар. Така че се надявам да ви хареса. Този семинар е за техническите интервюта, и всичките ми ресурси могат да бъдат намерени в тази връзка, тази връзка тук, няколко на ресурсите. Така че направих списък с проблеми, всъщност, доста проблеми. Също така общо страница ресурси там, където можем да намерим съвети за това как да се подготвят за интервю, съвети за това какво трябва да правите по време на реалното интервю, , както и как да подходим към проблемите и ресурси за бъдещи справки. Това е онлайн. И само да предговор този семинар, за отказ от отговорност, като това не трябва - подготовката на интервю не трябва да се ограничава в този списък. Това има за цел единствено да бъде водач, и определено трябва да вземат всичко, което казвам със зърно на сол, но също така да използвате всичко, което да ви помогне в подготовката на интервю. Отивам да се ускори през следващите няколко слайда така че можем да стигнем до реални казуси. Структурата на интервю за софтуерно инженерство postion, обикновено е 30 до 45 минути, няколко кръга, в зависимост от компанията. Често ще се кодиране на бяла дъска. Така бяла дъска така, но често и в по-малък мащаб. Ако имате интервю по телефона, най-вероятно ще се използва collabedit или Google Doc така че те могат да се видим на живо кодиране докато сте интервюирани по телефона. Самото интервю обикновено е два или три проблема тестване на познанията си в областта на компютърните науки. И това почти със сигурност ще включва кодиране. Видове въпроси, които ще видите обикновено са структури от данни и алгоритми. И в правенето на тези видове проблеми, те ще ви попитам, харесвате, какво е времето и сложността пространство, Big O? Често те също задават въпроси от по-високо ниво, така, проектирането на системата, как ще изложи кода си? Какво интерфейси, какви класове, какви модули да имате във вашата система, и как те си взаимодействат заедно? Така структури от данни и алгоритми, както и проектиране на системи. Някои общи съвети, преди да се потопите в нашите казуси. Мисля, че най-важното правило е винаги да се мисли на глас. Интервюто е трябвало да бъде вашият шанс да покаже процеса на мислене. Точка на интервюто е интервюиращият да се прецени начина, по който мислят и как ти мине през проблем. Най-лошото нещо, което може да направите, е да мълчат през цялото интервю. Това е просто не е добър. Когато даден въпрос, вие искате да се уверете, че сте разбрали въпроса. Така че повтарям въпроса в собствените си думи и се опитват да работят през няколко прости тестове да се уверете, че сте разбрали въпроса. Работа чрез няколко случая на изпитване също ще ви даде интуиция за това как да се реши този проблем. Може дори да се открият няколко модели, за да ви помогне да разрешите проблема. Тяхната най-голяма съвет е да не се разочароват. Не се разочароват. Интервютата са предизвикателство, но най-лошото нещо, което можеш да направиш, в допълнение да мълчи, е да бъдат видимо разочарован. Вие не искате да се даде такова впечатление на интервюиращия. Едно нещо, което - така, много хора, когато те отиват в интервю, те се опитват да се опитаме да намерим най-доброто решение за първи път, когато наистина има обикновено е напълно ясно решение. Тя може да е бавно, то може да бъде неефективна, но просто трябва да го заявя, само за да имате отправна точка, от която да работи по-добре. Също така, като посочи, решението е бавен, по отношение на Big O време сложност или сложност пространство, ще покаже на интервюиращия, че сте разбрали тези въпроси при писане на код. Така че не се страхува да излезе с най-простият алгоритъм първа и след това да работят по-добре от там. Всякакви въпроси досега? Добре. Така че нека да се потопите в първата наш проблем. "Като се има предвид масив от числа н, напишете функция, която разбърква масива на мястото, че всички пермутации на числа н са еднакво вероятни. " Предполагам, че имате на разположение един генератор на случайни число , което генерира цяло число в диапазона от 0, 1/2 кръг. Всички ли разбирам този въпрос? Аз ви давам масив от цели числа н, и аз искам да го претупвам. В моята директория, аз написах няколко програми, за да демонстрират какво искам да кажа. Отивам да се набутвам масив от 20 елемента, от -10 до 9, и аз искам да изведете списък като този. Така че това е моят подредени Входният масив, и аз искам да го претупвам. Ще го направим отново. Всички ли разбирам въпроса? Добре. Така че това е до вас. Какви са някои идеи? Можеш ли да го направя като N ^ 2, N дневник N, N? Отворени за предложения. Добре. Така една идея, предложена от Еми, е първото изчисляване на случайно число, произволно цяло число в диапазона 0-20. Така че поема нашия масив е с дължина от 20. В нашата диаграма от 20 елемента, това е нашата Входният масив. И сега, нейното предложение е да се създаде нов масив, така че това ще бъде изхода на масива. И въз основа се върнах от Ранд - така че, ако бях аз, да речем, 17, копирате 17-ти елемент в първата позиция. Сега ние трябва да изтриете - ние трябва да смени всички елементи тук над, така че имаме разминаване в края и няма дупки в средата. И сега ние повторете процеса. Сега изберете ново случайно число между 0 и 19. Имаме нов правя тук, и ние копирате този елемент в тази позиция. След това смени позиции и повторете процеса, докато ние имаме пълно нов масив. Какво е времето на работа на този алгоритъм? Е, нека да разгледаме въздействието на тази. Ние се изместват всеки елемент. Когато премахнем това аз, ние се изместват всички елементи след това наляво. А това е O (N) разходи защото това, което ако премахнем първия елемент? Така че при всяко преместване, ние премахваме - всяко преместване поема O (н) експлоатация, и тъй като ние сме N премествания, това води до O (N ^ 2) разбъркано. Добре. Толкова добър старт. Добро начало. Друго предложение е да се използва нещо, известно като претупвам Кнут, или Fisher-Йейтс разбъркване. И това е всъщност линейна разбъркано време. И идеята е много подобна. Отново, ние имаме Входният масив, но вместо да използват два масива за нашия вход / изход, ние използваме първата част на масива, за да следите разбъркват нашата част, и ние следим, а след това оставете останалото на нашата масив за unshuffled част. Така че, ето какво искам да кажа. Започваме с - ние избираме I, масив 0-20. Сегашната ни показалеца сочи първият индекс. Ние избираме някои тук и сега ние разменят. Така че, ако това е 5 и това беше 4, масив ще има 5 тук и 4. И сега ние отбелязваме маркер тук. Всичко в ляво се разменят и всичко, на дясно е unshuffled. И сега можем да повторим този процес. Ние избираме случаен индекс между 1 и 20. Така че предполагам, нашата нова съм тук. Сега ние суап това аз с текущата ни нова позиция тук. Така че правим смяна назад и напред по този начин. Нека ми донесе код, за да стане по-конкретна. Започваме с избора ни на и - започват с равен на 0, изберете произволно място J в unshuffled част на масива, аз до N-1. Така че, ако аз съм тук, изберете случаен индекс между тук и останалата част от масива, и ние суап. Това е код, необходим, за да разбъркате си масив. Някакви въпроси? Е, едно е необходимо въпрос е, защо е това е правилно? Защо е всяка пермутация еднакво вероятни? И аз няма да мине през доказателство за това, но много проблеми в компютърната наука може да бъде доказано чрез индукция. Колко от вас са запознати с индукция? Добре. Cool. Така че може да докаже верността на този алгоритъм с обикновено индукция, къде хипотеза индукция би било да приемем, че разбъркано ми се връща всяка пермутация еднакво вероятни до първите елементи I. Сега, помислете + 1. И от начина, по който ние избираме нашия J индекс за размяна, това води до - и след това да работите в детайли, най-малко един пълен доказателство за това защо този алгоритъм се връща всяка пермутация с еднаква вероятност вероятност. Добре, следващия проблем. Така "масив от цели числа, postive, нула, отрицателен, напишете функция, която изчислява максималната сума на всяка continueous subarray на входния масив. Пример тук е, че в случаите, когато всички числа са положителни, след това в момента е най-добрият избор е да се вземе целия масив. 1, 2, 3, 4, е равно на 10. Когато имате на някои негативи там, в този случай ние просто искаме първите две защото избора -1 и / или -3 ще донесе сумата. Понякога може да се наложи да започне в средата на масива. Понякога искаме да изберете нищо, то е най-добре да не вземат нищо. И понякога е по-добре да се вземат есента, , защото нещо, което след това е супер голям. Така че всякакви идеи? (Студент, неразбираем) >> Да. Да предположим, че аз не приемам -1. След това или да избера 1000 и 20000, или просто изберете от 3 милиарда. Е, най-добрият избор е да се вземат всички числа. Това -1, въпреки че е отрицателен, цялата сума е по-добре, отколкото аз да не предприемат -1. Така че един от съветите, които споменах по-рано е да се посочи ясно очевидно и груба сила решение на първо място. Какво е решение на грубата сила в този проблем? Да? [Джейн] Е, мисля, че грубата сила решение да се добавят всички възможни комбинации (неразбираемо). [Ю] Добре. Така че идеята на Джейн е да се вземат всички възможни Съм перифразиране - е да се вземат всички възможни непрекъснато subarray, изчисли си сума, а след това да се възползват максимално от всички възможни непрекъснати подмасива. Какво уникално идентифицира subarray в моя Входният масив? Например, две неща са ми нужни? Да? (Студент, неразбираем) >> Точно така. Долната граница на индекса и горна граница индекс еднозначно определя непрекъснато subarray. [Жена студент] Дали това е набор от уникални номера оцени? [Ю] Не Така че си въпрос, ние прие нашето масив - е нашият масив всички уникални номера, и отговорът е не. Ако се използва груба сила решение, а след това начало / край индекси еднозначно определя нашите непрекъснато subarray. Така че, ако за всички възможни записи стартиращи превъртите и за всички крайни записвания> или = да започне и > Zero. Само не приемайте -5. Тук ще бъде 0, както и. Да? (Студент, неразбираемо) [Ю] О, съжалявам, това е -3. Така че това е 2, това е -3. Добре. Така -4, каква е максималната subarray до края на тази позиция където -4 е? Zero. One? 1, 5, 8. Сега, аз трябва да се сложи край на мястото, където -2 е. Така 6, 5, 7, и последният е 4. Знаейки, че това са моите записи трансформира проблем, когато аз трябва да приключат на всеки един от тези показатели, след последната ми отговор е просто да из целия и да вземат максималния им брой. Така че в този случай това е 8. Това означава,, че максималният subarray завършва в този индекс, и започна някъде пред него. Всички ли разбирам този променен subarray? Добре. Ами, нека да разбера повтаряне за това. Нека разгледаме само първите няколко вписвания. Така че тук е 0, 0, 0, 1, 5, 8. И тогава там е -2 тук, и че го свалиха до 6. Така че, ако аз наричам влизане в позиция subproblem (I), как мога да използвам отговор на предишна subproblem да отговори на тази subproblem? Ако гледам, нека кажем, този пост. Как мога да се изчисли отговор 6, като погледнете в комбинация от този масив и отговори на предишни subproblems в този масив? Да? [Жена студент] масива на суми в състояние преди, така че 8 и след това да добавите настоящата subproblem. [Ю] Така че нейното предложение е да се погледне на тези две числа, този номер и този номер. Така че това 8 се отнася до отговора за subproblem (I - 1). И нека го наречем моя масив вход А. За да се намери максимален subarray, който завършва и позиция, Имам две възможности: Мога да продължи subarray , която приключи в предишния индекс, или започнете нов масив. Ако аз трябваше да продължи subarray, която започна в предишния индекс, тогава максималната сума, може да се постигне, е отговорът на предишния subproblem плюс масив влизане. Но, аз също имам избор за стартиране на нов subarray като в този случай сумата е 0. Така че отговорът е макс на 0, subproblem и - 1, плюс текущия елемент от масива. Ли това повторение има ли смисъл? Нашата рецидив, тъй като ние току-що открих, е subproblem и е равна на максимум предходната subproblem плюс текущата ми елемент от масива, което означава, продължи предишната subarray, или 0, започнете нова subarray в сегашния си индекс. И след като сме изградили тази таблица на решения, тогава нашият окончателен отговор, просто правя линейна размах през subproblem масив и да вземат максималния им брой. Това е точното прилагане на това, което току-що казах. Така че ние създаваме нов масив subproblem, subproblems. Първият запис е 0 или на първото влизане, максималното от тези две. А за останалата част от subproblems ние използваме точно повторение, ние току-що открих. Сега ние се изчисли максимум на нашата subproblems масив, и това е нашият окончателен отговор. Така че колко пространство се използва в този алгоритъм? Ако сте само CS50, тогава може и да не са обсъждали пространство много. Е, едно нещо, което трябва да се отбележи, е, че се обадих на изчистване тук с размер N. Какво значи това ви предложа? Този алгоритъм използва линейно пространство. Можем ли да направим по-добре? Има ли нещо, което забележите, че не е необходимо да се изчисли окончателен отговор? Предполагам, че по-добрият въпрос е, каква информация не трябва да носят през целия път до края? Сега, ако се вгледаме в тези две линии, ние само се грижи за предишния subproblem, и ние само се грижи за максималното, което сме виждали досега. За да се изчисли окончателен отговор, ние не се нуждаем от целия масив. Нужно е само по последната цифра, последните две цифри. На последния номер за subproblem масив, и последното число за максималната. Така че, всъщност, ние можем да се слеят тези вериги и си отиват от линейно пространство до постоянно пространство. Текущ сумата досега, тук, замества ролята на subproblem, нашата subproblem масив. Така че сегашната сума, доколкото е отговорът на предишния subproblem. И тази сума, досега, заема мястото на нашата макс. Изчисляваме максимално, като отидем заедно. И така преминаваме от линейно пространство на постоянно място, и ние също трябва линейна решение на проблема ни subarray. Тези въпроси ще получите по време на интервю. Какво е времето сложност; какво е пространството сложност? Можеш ли да направиш по-добре? Има ли неща, които не са необходими, за да се запази около? Аз направих това, за да се подчертае анализи, които трябва да вземете по своему като работим чрез тези проблеми. Винаги си задавайте въпроса: "Мога ли да направя по-добре?" В действителност, можем да направим по-добро от това? Сортиране на подвеждащ въпрос. Не можеш, защото трябва да се поне прочетете входа на проблема. Така че самият факт, че трябва да най-малко четат входа на проблема означава, че не можеш да направиш по-добре, отколкото линейно време, и не можеш да направиш по-добре в сравнение с постоянния пространство. Така че това е, всъщност, най-доброто решение на този проблем. Въпроси? Добре. Проблем на фондовия пазар: "Като се има предвид масив от цели числа N, положителни, нулеви или отрицателни, , които представляват цената на фондовата н ден, напиши функция за изчисляване на максимална печалба, можете да направите като се има предвид, че купуват и продават точно един състав в рамките на тези н ден. " По същество, ние искаме да купуват ниско, продават големи. И ние искаме да измислят най-добрата печалба, можем да направим. Връщайки се към върха ми, това, което е непосредствено ясно, простият отговор, но това е бавен? Да? (Студент, неразбираем) >> Да. >> Така че просто ще отида все пак и погледнете цените на акциите във всяка точка във времето (неразбираемо). [Ю] Добре, така че нейният решение - предложение на изчислителната техника най-ниската и изчисляване на най-високата не е задължително да работи тъй като най-високото може да се случи преди най-ниската. Така че това, което е груба сила решение на този проблем? Какви са двете неща, които трябва да може еднозначно да се определи печалбата правя? Точно така. Груба сила е решение - О, значи, предложение Джордж е само нужда от два дни за да може еднозначно да се определи печалбата на тези два дни. Така че ние се изчислява всеки чифт, като купува / продава изчисли печалбата, която може да бъде отрицателен или положителен или нулев. Изчислете максимална печалба, че ние правим след итерации над всички двойки на ден. Това ще бъде нашият окончателен отговор. И това решение ще бъде O (N ^ 2), защото има N изберете два чифта - на ден, които можете да избирате сред крайните ден. Добре, така че аз не отивам тук да премине груба сила решение. Аз ще ви кажа, че има N дневник N решение. Какво алгоритъм момента знаем, че е н дневник н? Това не е подвеждащ въпрос. Обединяване вид. Обединяване вид е н н дневник, и в действителност, един от начините за решаване на този проблем е да се използва един вид сливане на идея, наречена, като цяло, разделяй и владей. И идеята е, както следва. Искаш ли да се изчисли най-добрите купува / продава двойка в лявата половина. Намерете най-добрите печалбата, която могат да направят, само с първия N в рамките на два дни. След искате да oompute най-добрите купува / продава чифт върху дясната половина, Така последната N в рамките на два дни. И сега въпросът е, как да се слеят тези решения отново заедно? Да? (Студент, неразбираемо) >> Добре. Така че нека да нарисува картина. Да? (Джордж, неразбираем) >> Точно така. Джордж решение е точно така. Така че предложението му е първото изчисляване на най-добрата двойка купува / продава и че се появява в лявата половина, така че нека го наречем, че ляво, ляво. Най-добър купува / продава двойка, която се появява в дясната половина. Но ако ние само спрямо тези две числа, ни липсва по делото където ние купуваме тук и продават някъде в дясната половина. Ние купуваме в лявата половина продават в дясната половина. И най-добрият начин да се изчисли най-добрите купува / продава чифт, който обхваща двете полувремена е да се пресметнат минимум тук и изчисляване на максималната тук и да им разлика. Така двете случаите, когато двойката купува / продава се случва само тук, само тук, или на двете полувремена се определя от тези три числа. Така че нашият алгоритъм, за да се слеят нашите решения, искаме да се изчисли най-добрата двойка купува / продава където ние купуваме в лявата половина и продават в дясната половина. И най-добрият начин да направите това е да се изчисли най-ниската цена в първата половина, най-високата цена в дясната половина, и да си вземат разликата. В резултат на три печалби, тези три числа, се възползват максимално от трите, и това е най-добрата печалба може да се направи през тези първи и в края ден. Ето най-важните линии са в червено. Това е рекурсивно повикване, за да се изчисли отговор в лявата половина. Това е рекурсивно повикване, за да се изчисли отговор в дясната половина. Тези две за вериги изчисли мин и макс на лявата и дясната половина. Сега се изчисли печалбата, която обхваща двете полувремена, и окончателен отговор е максималната от тези три. Добре. Така че, разбира се, ние имаме един алгоритъм, но големият въпрос е, какво е времето сложността на този въпрос? И причината, поради която споменах сливане вид е, че тази форма на разделяме отговор на две и след това обединяване на нашите решения заедно е точно формата на сливане вид. Така че нека да мине през продължителността. Ако ние определено функция т (н) да бъде броя на стъпките N за ден, нашите две рекурсивни повиквания всеки ще струва тон (N / 2), и има два от тези разговори. Сега трябва да се изчисли минимум на лявата половина, , което мога да направя в N / 2 време, плюс максимум на дясната половина. Така че това е просто N. И тогава, плюс някои постоянна работа. И това повторение уравнение е точно повторение уравнението за сливане вид. И ние всички знаем, че се сливат вид е н дневник н време. Затова нашият алгоритъм е N дневник н. Ли тази итерация има ли смисъл? Само една кратка рекапитулация на това: T (N) е броя на стъпките за изчисляване на максимална печалба в течение N на ден. Начинът, по който се разделят нашите рекурсивни повиквания е като се обадите на нашето решение на първия ден N / 2, така че това е един разговор, и след това ние наричаме отново на второто полувреме. Така че това е двете повиквания. И тогава ние откриваме минимум в лявата половина, което можем да направим в линейното време, намерите максимум на дясната половина, което можем да направим в линейното време. Така N / 2 + N / 2 е просто н. Тогава ние имаме някаква постоянна работа, което е като смятане. Този рецидив уравнение е точно повторение уравнението за сливане вид. Следователно, разбъркано алгоритъм е N влезете н. Така че, колко място ще използвате? Нека се върнем на кода. По-добрият въпрос е, колко стека рамки ние някога в даден момент? Тъй като ние сме използване на рекурсия, броя на стека рамки определя използването на нашето пространство. Нека разгледаме N = 8. Ние наричаме разбъркването 8, , които ще се обадя на разбъркването първите четири записа, , които ще се обадя на разбъркването първите два записа. Така че нашата стак е - това е нашата стека. И тогава ние наричаме набутвам отново на 1, и това е, което нашата база случай е, за да се върнем веднага. Ли някога повече от това много рамки стека? Не, защото всеки път, когато правим позоваването рекурсивно извикване, за да претупвам, ние разделяме нашия размер на половина. Така максималният брой на стека рамки някога във всеки един момент е по нареждане на Дневник н стека рамки. Всеки стек рамка има постоянна пространство, и следователно общата сума на пространството, максималния размер на пространството, което някога използвате е O (дневник н) пространство където N е броя на дните. Сега, винаги се запитате, "Можем ли да направя по-добре?" И по-специално, можем да се намали този проблем, вече сме решени? Жокер: само обсъди две други проблеми преди това, и това няма да се набутвам. Ние можем да конвертирате този проблем фондов пазар в максималната проблем subarray. Как можем да направим това? Един от вас? Еми? (Еми, неразбираем) [Ю] Точно така. Така максималната проблем subarray търсим сума непрекъснато subarray. И предложение на "Еми" за проблема с запаси, разгледа промени, или делта. И картина на това е - това е цената на запаси, но ако вземем разликата между всеки пореден ден - така че ние виждаме, че максималната цена, максимална печалба можем да направим е, ако ние купуваме тук и продават тук. Но нека да разгледаме в непрекъснат нека погледнем в subarray проблем. Така че тук, можем да направим - от тук до тук, имаме положителна промяна, и след това става от тук до тук имаме отрицателна промяна. Но след това, от тук до тук имаме огромна положителна промяна. И това са промените, които искаме да обобщим, за да получите нашата крайна печалба. Тогава ние имаме по-негативни промени тук. Ключът към намаляване на нашия състав проблем в максимална subarray проблем е да се разгледа делтите между дни. Така че ние създаваме нов масив наречен делти, инициализиране на първото влизане, за да бъде 0, и след това за всяка делта (I), нека това да бъде разликата Входният масив (I), и масив (I - 1). Тогава ние наричаме нашия рутинна процедура за максимално subarray преминаващи в масив на делтата. И тъй като максимално subarray е линейното време, и това намаление, този процес на създаването на тази делта масив, е линейно време, след окончателното решение за запаси е O (N) работа плюс O (N) работа, все още е O (N) работа. Така че ние имаме линейно решение на нашия проблем. Всички ли разбирам тази трансформация? Като цяло, добра идея, която винаги трябва да има се опитат да намалят нов проблем, който вие виждате. Ако изглежда познат на един стар проблем, опитайте се да го намали до един стар проблем. И ако може да използваме всички инструменти, които сте използвали по стар проблем за решаване на нов проблем. Така че, за да се приключи, технически интервюта оспорват. Тези проблеми вероятно са някои от най-трудните проблеми , които можете да видите в интервю, така че, ако вие не разбирате всички проблеми, които аз просто обхванати, всичко е наред. Това са някои от най-трудните проблеми. Практика, практика, практика. Дадох много проблеми в помагалото, така че определено проверите тези. И късмет на вашите интервюта. Всичките ми средства са публикувани в тази връзка, и един от моите старши приятели предложи да се направи макет технически интервюта, така че ако ви интересува, електронна поща, ще Яо този имейл адрес. Ако имате някакви въпроси, можете да ме питате. Вие, момчета, имате ли конкретни въпроси, свързани с технически интервюта или някакви проблеми, които сме виждали досега? Добре. Е, на добър час на вашите интервюта. [CS50.TV]