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

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

Деякі загальні поради Перш ніж ми заглибимося в наші тематичні дослідження. Я думаю, що найважливіше правило завжди думати вголос. Інтерв'ю повинно бути ваш шанс показати свій розумовий процес. Справа в інтерв'ю для інтерв'юера, щоб виміряти як ви думаєте, і як ви йдете через проблемі. Найгірше, що ви можете зробити, це мовчати протягом усього інтерв'ю. Ось тільки нічого хорошого. Коли ви отримуєте питання, ви також хочете, щоб переконатися, що ви зрозуміли запитання. Так що повторю питання ще в свої слова і спроба працювати ретельної кілька простих тестів переконайтеся, що ви зрозуміли запитання. Робота через кілька тестів також дасть вам інтуїція про те, як вирішити цю проблему. Ви навіть можете відкрити для себе кілька моделей, щоб допомогти вам вирішити цю проблему. Їх великі чайові, щоб не засмучуватися. Не турбуйтеся. Інтерв'ю є складними, але найгірше, що ви можете зробити, На додаток до того, мовчить, має бути явно розчаровані. Ви ж не хочете, щоб дати враження, що інтерв'юер. Одна річ, яку ви - так, багато людей, коли вони йдуть в інтерв'ю, вони намагаються, щоб спробувати знайти найкраще рішення першої, коли насправді, там зазвичай очевидні рішення. Це може бути повільним, воно може бути неефективним, але ви повинні просто констатувати це, просто так у вас є відправна точка, з якою можна працювати краще. Крім того, вказуючи на рішення повільно, з точки зору великий час O складності або простір складності, буде продемонструвати інтерв'юеру, що ви розумієте, ці питання при написанні коду. Так що не бійтеся придумати найпростіший алгоритм спочатку , А потім працювати краще звідти. Будь-які питання досі? Добре. 

Так що давайте зануритися в нашу першу задачу. "Враховуючи масив цілих чисел п, написати функцію, яка тасує масиву на місце так, що всі перестановки чисел п однаково ймовірні. " І припустимо, у вас є генератор випадкових цілих , Який генерує ціле число в діапазоні від 0 до я, половину діапазону. Чи всі розуміють це питання? Я даю вам масив цілих чисел п, і я хочу, щоб перемішати. У моєму каталозі, я написав кілька програм, щоб продемонструвати, що я маю на увазі. Я збираюся перемішати масив з 20 елементів, від -10 до +9, і я хочу, щоб ви вивести список, як це. Так що це мій відсортований масив вихідних даних, і я хочу, щоб ти перемішати. Ми зробимо це знову. Чи всі розуміють, в чому питання? Добре. Так що це залежить від вас. Які ідеї? Ви можете зробити це при п ^ 2, п § п, п? Відкритий для пропозицій. Добре. Так що ідея, запропонована Еммі, перший обчислити випадкове число, випадкове число, в діапазоні від 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 кращі покупки / продажу пари на правій половині, так що останні п протягом двох днів. А тепер питання в тому, як ми можемо об'єднати ці рішення разом? Так? (Студент, незрозумілі) >> Добре. Отже, дозвольте мені намалювати картинку. Так? (Джордж, незрозумілі) >> Саме так. Рішення Джорджа це абсолютно вірно. Так що його пропозиція є, в першу обчислити оптимальну покупку / продаж пари, і що відбувається в лівій половині, так що давайте називати це лівий, лівий. Краща покупка / продаж пара, яка відбувається в правій половині. Але якщо ми тільки в порівнянні цих двох чисел, ми пропустили випадок де купити тут і продати десь в правій половині. Ми купуємо в лівій половині, продажу в правій половині. І найкращий спосіб обчислити оптимальну купити / продати пару, яка охоплює обидві половинки є обчислення мінімального тут і вирахувати максимальну тут і взяти їх різницю. Таким чином, два випадки, коли купівлі / продажу пари відбувається тільки тут, Тільки тут, або на обох половинах визначається цими трьома числами. Таким чином, наш алгоритм об'єднати наші рішення разом, Ми хочемо обчислити оптимальну покупку / продаж пари де ми купуємо на лівій половині і продавати на правій половині. І кращий спосіб зробити це полягає в обчисленні найнижчою ціною в першій половині, найвища ціна в правій половині, і взяти їх різницю. Отримані три прибулих, ці три цифри, ви берете максимум три, і це найкраща прибуток ви можете зробити за ці перші і кінця днів. Тут важливі лінії червоного кольору. Це рекурсивний виклик для обчислення відповіді в лівій половині. Це рекурсивний виклик для обчислення відповіді в правій половині. Ці дві петлі для обчислення хв і макс на ліву і праву половини, відповідно. Тепер я обчислити прибуток, яка охоплює обидві половинки, і остаточну відповідь максимальна з цих трьох. Добре. 

Так що, впевнений, у нас є алгоритм, але більше питання в тому, що тимчасова складність цього? І причина, чому я згадав, сортування злиттям в тому, що ця форма розділити відповідь на два, а потім об'єднувати наші рішення разом Саме вид сортування злиттям. Отже, дозвольте мені пройти тривалості. Якщо ми визначили функцію T (N), що число кроків для п днів, наші рекурсивні виклики кожен буде коштувати т (п / 2), і є два з цих викликів. Тепер мені потрібно обчислити мінімум лівій половині, який я можу зробити в п / 2, плюс максимум в правій половині. Так що це просто п. А потім плюс деяка постійна робота. І це рекурентне рівняння Саме рекурентне рівняння для сортування злиттям. І всі ми знаємо, що сортування злиттям п § п часу. Таким чином, наш алгоритм також п § п часу. Чи означає це, ітерації сенс? Тільки коротке резюме цього: Т (п) є ряд кроків, щоб обчислити максимальний прибуток протягом доби з. Те, як ми розділилися наші рекурсивні виклики є викликом нашого рішення у перші дні п / 2, так що це один виклик, а потім ми знову закликаємо другої половини. Так от двома викликами. І тоді ми знаходимо мінімум на лівій половині, яку ми можемо зробити в лінійному часу, знайти максимум в правій половині, яку ми можемо зробити в лінійному часу. Таким чином, п / 2 + п / 2 знаходиться всього в с. Тоді у нас є постійна робота, яка, як робити арифметику. Це рекурентне рівняння в точності повторення рівняння для сортування злиттям. Таким чином, наш алгоритм перемішування також п п увійти. Так скільки місця ми використовуємо? Давайте повернемося до коду. 

Кращий питання, скільки кадрів стека ми коли-небудь в будь-який момент? Так як ми використовуємо рекурсію, число кадрів стека визначає наше використання простору. Розглянемо N = 8. Ми закликаємо перемішати 8, , Який буде викликати випадковому порядку на перших чотирьох записів, , Який буде викликати перемішування на перших двох записів. Таким чином, наш стек - це наш стек. І тоді ми називаємо перемішати ще раз на 1, і це те, що наша база випадок, тому ми негайно повернутися. Чи є у нас коли-небудь більше, ніж це кількість кадрів стека? Ні, тому що кожен раз, коли ми робимо виклик, рекурсивний виклик для перемішування, ми ділимо нашу розміром в половину. Таким чином, максимальна кількість кадрів стека ми коли-небудь в будь-який момент порядку журналу N кадрів стека. Кожен кадр стека має постійне місце, і, отже, загальний обсяг простору, максимальний обсяг простору, ми коли-небудь використовувати це O (журнал N) простору де п-кількість днів. 

Тепер, завжди запитуйте себе: "Чи можемо ми зробити краще?" І зокрема, ми можемо скоротити цю проблему ми вже вирішили? Підказка: ми тільки обговорювали два інших проблем до цього, і він не збирається бути перемішати. Ми можемо перетворити цю проблему фондового ринку в максимальній проблеми подмассіва. Як ми можемо це зробити? Один з вас? Еммі? (Emmy, незрозумілі) [Ю] Саме так. Таким чином, максимальна подмассіва проблеми, Ми шукаємо сума по безперервній подмассіва. І пропозиція Еммі завдання акції, Розглянемо зміни, або дельти. І картина ця є - це ціна акції, але якщо б ми взяли різницю між кожним день поспіль - Отже, ми бачимо, що максимальна ціна, максимальна прибуток ми могли б зробити , Якщо ми купуємо і продаємо тут тут. Але давайте подивимося на безперервне - давайте подивимося на подмассіва проблеми. Так от, ми можемо зробити - походить від сих до сих, у нас є позитивні зміни, а потім збирається звідси тут ми маємо негативне зміна. Але тоді, переходячи від сюди, щоб тут ми маємо величезну позитивну зміну. І ці зміни, які ми хочемо підвести підсумки, щоб отримати нашу кінцеву прибуток. Тоді у нас більше негативних змін тут. Ключ до зниження нашому складі проблемою в нашій максимальної проблеми подмассіва є розгляд дельти між днів. Таким чином, ми створюємо новий масив з ім'ям дельти, ініціалізація першого елемента рівним 0, а потім для кожної дельти (I), нехай це буде різниця моєї вхідний масив (I), і масив (я - 1). Тоді ми називаємо нашою рутинною процедурою для максимального подмассіва проходить в масиві дельти. І тому, що максимальна подмассіва є лінійним часом, і це скорочення, цей процес створення цієї дельти масиву, Також лінійного часу, то остаточне рішення запасів O (п) плюс робота O (п) роботи, як і раніше O (п) роботи. Тому у нас є лінійний час вирішення нашої проблеми. Чи всі розуміють це перетворення? 

Загалом, хороша ідея, що ви завжди повинні мати це спробувати зменшити нова проблема, що ви бачите. Якщо воно виглядає знайомо стара проблема, спробуйте зменшити його стара проблема. І якщо ви можете використовувати всі інструменти, які ви використовували на старі проблеми для вирішення нової проблеми. Таким чином, щоб підбивати підсумки, технічне інтерв'ю складним завданням. Ці проблеми, ймовірно, деякі з найбільш складних проблем що ви можете побачити в одному з інтерв'ю, так що якщо ви не розумієте, всі проблеми, які я тільки покриті, це нормально. Ось деякі з найбільш складних проблем. Практика, практика, практика. Я дала багато проблем в роздавальний матеріал, так виразно перевірити ці. І удачі на інтерв'ю. Всі мої ресурси, розміщені на цю посилання, і один з моїх старших друзів запропонував зробити макет технічне інтерв'ю, так що якщо ви зацікавилися, лист буде Яо, що адреса електронної пошти. Якщо у вас є питання, ви можете запитати мене. Як ви, хлопці, є конкретні питання, пов'язані з технічними інтерв'ю або будь-які проблеми, які ми бачили до сих пір? Добре. Ну, удачі на інтерв'ю. [CS50.TV]