[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]