1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Семінар: Технічні Інтерв'ю]

2
00:00:02,640 --> 00:00:04,630
[Kenny Ю., Гарвардський університет]

3
00:00:04,630 --> 00:00:08,910
[Це CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Привіт всім, я Кенні. В даний час я молодший, що вивчають інформатику.

5
00:00:12,420 --> 00:00:17,310
Я колишній CS TF, і я б хотів цього, коли я був студент першого або другого курсу,

6
00:00:17,310 --> 00:00:19,380
і саме тому я даю цей семінар.

7
00:00:19,380 --> 00:00:21,370
Так що я сподіваюся, вам сподобається.

8
00:00:21,370 --> 00:00:23,470
Цей семінар про технічні інтерв'ю,

9
00:00:23,470 --> 00:00:26,650
і всі мої ресурси можна знайти за цим посиланням,

10
00:00:26,650 --> 00:00:32,350
посилання прямо тут, пару ресурсів.

11
00:00:32,350 --> 00:00:36,550
Тому я склав список проблем, насправді, досить багато проблем.

12
00:00:36,550 --> 00:00:40,800
Крім того, загальне сторінки ресурсів, де можна знайти поради

13
00:00:40,800 --> 00:00:42,870
про те, як підготуватися до співбесіди,

14
00:00:42,870 --> 00:00:46,470
поради про те, що ви повинні зробити протягом фактичного інтерв'ю,

15
00:00:46,470 --> 00:00:51,910
а також, як підходити до проблем і ресурси для подальшого використання.

16
00:00:51,910 --> 00:00:53,980
Це все он-лайн.

17
00:00:53,980 --> 00:00:58,290
І щоб випередити цей семінар, відмова,

18
00:00:58,290 --> 00:01:00,690
як це не слід - ваша підготовка до інтерв'ю

19
00:01:00,690 --> 00:01:02,800
не повинні бути обмежені в цей список.

20
00:01:02,800 --> 00:01:04,750
Це тільки означає, що керівництво,

21
00:01:04,750 --> 00:01:08,890
і ви повинні обов'язково взяти все, що я говорю з зерном солі,

22
00:01:08,890 --> 00:01:14,620
але і використовувати все, що я використав, щоб допомогти вам у вашій підготовці до інтерв'ю.

23
00:01:14,620 --> 00:01:16,400
>> Я хочу, щоб прискорити протягом наступних кількох слайдах

24
00:01:16,400 --> 00:01:18,650
так що ми можемо дістатися до фактичного досліджень.

25
00:01:18,650 --> 00:01:23,630
Структура інтерв'ю постіон розробки програмного забезпечення,

26
00:01:23,630 --> 00:01:26,320
Зазвичай вона становить від 30 до 45 хвилин,

27
00:01:26,320 --> 00:01:29,810
кілька раундів, в залежності від компанії.

28
00:01:29,810 --> 00:01:33,090
Часто ви будете кодування на білій дошці.

29
00:01:33,090 --> 00:01:35,960
Таким чином, біла дошка, як це, але часто і в менших масштабах.

30
00:01:35,960 --> 00:01:38,540
Якщо у вас інтерв'ю по телефону, ви будете, ймовірно, використовувати

31
00:01:38,540 --> 00:01:44,030
або collabedit або Google Doc щоб вони могли бачити ви живете кодування

32
00:01:44,030 --> 00:01:46,500
а ви під час інтерв'ю по телефону.

33
00:01:46,500 --> 00:01:48,490
Інтерв'ю собі, як правило, 2 або 3 проблеми

34
00:01:48,490 --> 00:01:50,620
тестування комп'ютера наукових знань.

35
00:01:50,620 --> 00:01:54,490
І це буде майже виразно зв'язані з кодуванням.

36
00:01:54,490 --> 00:01:59,540
Типи питань, які ви побачите, як правило, структури даних і алгоритми.

37
00:01:59,540 --> 00:02:02,210
І при цьому ці види проблем,

38
00:02:02,210 --> 00:02:07,830
вони будуть просити вас, начебто, скільки часу і просторі складність, великі O?

39
00:02:07,830 --> 00:02:09,800
Найчастіше вони також просять більш високому рівні питання,

40
00:02:09,800 --> 00:02:12,530
Таким чином, проектування системи,

41
00:02:12,530 --> 00:02:14,770
Як би ви викласти код?

42
00:02:14,770 --> 00:02:18,370
Які інтерфейси, які класи, які модулі у вас є у вашій системі,

43
00:02:18,370 --> 00:02:20,900
і як вони взаємодіють один з одним?

44
00:02:20,900 --> 00:02:26,130
Таким чином, структури даних і алгоритми, а також проектування систем.

45
00:02:26,130 --> 00:02:29,180
>> Деякі загальні поради Перш ніж ми заглибимося в наші тематичні дослідження.

46
00:02:29,180 --> 00:02:32,300
Я думаю, що найважливіше правило завжди думати вголос.

47
00:02:32,300 --> 00:02:36,980
Інтерв'ю повинно бути ваш шанс показати свій розумовий процес.

48
00:02:36,980 --> 00:02:39,820
Справа в інтерв'ю для інтерв'юера, щоб виміряти

49
00:02:39,820 --> 00:02:42,660
як ви думаєте, і як ви йдете через проблемі.

50
00:02:42,660 --> 00:02:45,210
Найгірше, що ви можете зробити, це мовчати протягом усього інтерв'ю.

51
00:02:45,210 --> 00:02:50,090
Ось тільки нічого хорошого.

52
00:02:50,090 --> 00:02:53,230
Коли ви отримуєте питання, ви також хочете, щоб переконатися, що ви зрозуміли запитання.

53
00:02:53,230 --> 00:02:55,350
Так що повторю питання ще в свої слова

54
00:02:55,350 --> 00:02:58,920
і спроба працювати ретельної кілька простих тестів

55
00:02:58,920 --> 00:03:01,530
переконайтеся, що ви зрозуміли запитання.

56
00:03:01,530 --> 00:03:05,510
Робота через кілька тестів також дасть вам інтуїція про те, як вирішити цю проблему.

57
00:03:05,510 --> 00:03:11,210
Ви навіть можете відкрити для себе кілька моделей, щоб допомогти вам вирішити цю проблему.

58
00:03:11,210 --> 00:03:14,500
Їх великі чайові, щоб не засмучуватися.

59
00:03:14,500 --> 00:03:17,060
Не турбуйтеся.

60
00:03:17,060 --> 00:03:19,060
Інтерв'ю є складними, але найгірше, що ви можете зробити,

61
00:03:19,060 --> 00:03:23,330
На додаток до того, мовчить, має бути явно розчаровані.

62
00:03:23,330 --> 00:03:27,410
Ви ж не хочете, щоб дати враження, що інтерв'юер.

63
00:03:27,410 --> 00:03:33,960
Одна річ, яку ви - так, багато людей, коли вони йдуть в інтерв'ю,

64
00:03:33,960 --> 00:03:37,150
вони намагаються, щоб спробувати знайти найкраще рішення першої,

65
00:03:37,150 --> 00:03:39,950
коли насправді, там зазвичай очевидні рішення.

66
00:03:39,950 --> 00:03:43,500
Це може бути повільним, воно може бути неефективним, але ви повинні просто констатувати це,

67
00:03:43,500 --> 00:03:46,210
просто так у вас є відправна точка, з якою можна працювати краще.

68
00:03:46,210 --> 00:03:48,270
Крім того, вказуючи на рішення повільно, з точки зору

69
00:03:48,270 --> 00:03:52,160
великий час O складності або простір складності,

70
00:03:52,160 --> 00:03:54,450
буде продемонструвати інтерв'юеру, що ви розумієте,

71
00:03:54,450 --> 00:03:57,510
ці питання при написанні коду.

72
00:03:57,510 --> 00:04:01,440
Так що не бійтеся придумати найпростіший алгоритм спочатку

73
00:04:01,440 --> 00:04:04,950
, А потім працювати краще звідти.

74
00:04:04,950 --> 00:04:09,810
Будь-які питання досі? Добре.

75
00:04:09,810 --> 00:04:11,650
>> Так що давайте зануритися в нашу першу задачу.

76
00:04:11,650 --> 00:04:14,790
"Враховуючи масив цілих чисел п, написати функцію, яка тасує масиву

77
00:04:14,790 --> 00:04:20,209
на місце так, що всі перестановки чисел п однаково ймовірні. "

78
00:04:20,209 --> 00:04:23,470
І припустимо, у вас є генератор випадкових цілих

79
00:04:23,470 --> 00:04:30,980
, Який генерує ціле число в діапазоні від 0 до я, половину діапазону.

80
00:04:30,980 --> 00:04:32,970
Чи всі розуміють це питання?

81
00:04:32,970 --> 00:04:39,660
Я даю вам масив цілих чисел п, і я хочу, щоб перемішати.

82
00:04:39,660 --> 00:04:46,050
У моєму каталозі, я написав кілька програм, щоб продемонструвати, що я маю на увазі.

83
00:04:46,050 --> 00:04:48,910
Я збираюся перемішати масив з 20 елементів,

84
00:04:48,910 --> 00:04:52,490
від -10 до +9,

85
00:04:52,490 --> 00:04:57,050
і я хочу, щоб ви вивести список, як це.

86
00:04:57,050 --> 00:05:02,890
Так що це мій відсортований масив вихідних даних, і я хочу, щоб ти перемішати.

87
00:05:02,890 --> 00:05:07,070
Ми зробимо це знову.

88
00:05:07,070 --> 00:05:13,780
Чи всі розуміють, в чому питання? Добре.

89
00:05:13,780 --> 00:05:16,730
Так що це залежить від вас.

90
00:05:16,730 --> 00:05:21,220
Які ідеї? Ви можете зробити це при п ^ 2, п § п, п?

91
00:05:21,220 --> 00:05:34,400
Відкритий для пропозицій.

92
00:05:34,400 --> 00:05:37,730
Добре. Так що ідея, запропонована Еммі,

93
00:05:37,730 --> 00:05:45,300
перший обчислити випадкове число, випадкове число, в діапазоні від 0 до 20.

94
00:05:45,300 --> 00:05:49,840
Таким чином, припустімо, наш масив має довжину 20.

95
00:05:49,840 --> 00:05:54,800
У нашій схемі 20 елементів,

96
00:05:54,800 --> 00:05:58,560
це наш вхідний масив.

97
00:05:58,560 --> 00:06:04,590
І тепер, її пропозиція є створення нового масиву,

98
00:06:04,590 --> 00:06:08,440
так що це буде вихідний масив.

99
00:06:08,440 --> 00:06:12,880
І на основі я повернувся на ранда -

100
00:06:12,880 --> 00:06:17,580
так що якщо б я був, скажімо, 17,

101
00:06:17,580 --> 00:06:25,640
скопіювати 17 елементів в першій позиції.

102
00:06:25,640 --> 00:06:30,300
Тепер нам потрібно видалити - ми повинні перекласти всі елементи тут

103
00:06:30,300 --> 00:06:36,920
над тим, що у нас є прогалина в кінці і без отворів в середині.

104
00:06:36,920 --> 00:06:39,860
І зараз ми повторюємо процес.

105
00:06:39,860 --> 00:06:46,360
Зараз ми вибираємо нове випадкове число між 0 і 19.

106
00:06:46,360 --> 00:06:52,510
У нас є нова я тут, і ми копіюємо цей елемент у цій позиції.

107
00:06:52,510 --> 00:07:00,960
Потім ми переходимо елементи знову і повторити процес, поки у нас є повний нового масиву.

108
00:07:00,960 --> 00:07:05,890
Що таке час виконання цього алгоритму?

109
00:07:05,890 --> 00:07:08,110
Ну, давайте розглянемо наслідки цього.

110
00:07:08,110 --> 00:07:10,380
Ми переходимо кожного елемента.

111
00:07:10,380 --> 00:07:16,800
Коли ми видаляємо це я, ми переходимо всі елементи після його вліво.

112
00:07:16,800 --> 00:07:21,600
І це O (п) вартість

113
00:07:21,600 --> 00:07:26,100
тому що, якщо ми видаляємо перший елемент?

114
00:07:26,100 --> 00:07:29,670
Таким чином, для кожного видалення, ми видаляємо -

115
00:07:29,670 --> 00:07:32,170
кожне видалення несе O (N) операцій,

116
00:07:32,170 --> 00:07:41,520
і так як ми маємо п абсорбції, це призводить до O (N ^ 2) перемішати.

117
00:07:41,520 --> 00:07:49,550
Добре. Так що хороший початок. Гарний початок.

118
00:07:49,550 --> 00:07:55,290
>> Інша пропозиція полягає у використанні щось, відоме як порожню Кнута,

119
00:07:55,290 --> 00:07:57,540
або Fisher-Yates Shuffle.

120
00:07:57,540 --> 00:07:59,630
І це насправді лінійного перемішування часу.

121
00:07:59,630 --> 00:08:02,200
А ідея дуже схожа.

122
00:08:02,200 --> 00:08:05,160
Знову ж таки, у нас є вхідний масив,

123
00:08:05,160 --> 00:08:08,580
але замість двох масивів для наших введення / виводу,

124
00:08:08,580 --> 00:08:13,590
ми використовуємо першу частину масиву стежити за нашими перетасував частина,

125
00:08:13,590 --> 00:08:18,400
і ми відстежуємо, і тоді ми залишити іншу частину нашого масиву для unshuffled частина.

126
00:08:18,400 --> 00:08:24,330
Отже, ось що я маю на увазі. Ми починаємо з - ми вибираємо я,

127
00:08:24,330 --> 00:08:30,910
масив від 0 до 20.

128
00:08:30,910 --> 00:08:36,150
Наш поточний покажчик вказує на перший індекс.

129
00:08:36,150 --> 00:08:39,590
Виберемо деякий я тут

130
00:08:39,590 --> 00:08:42,740
і тепер ми переставляємо.

131
00:08:42,740 --> 00:08:47,690
Так що, якщо це було 5, і це було 4,

132
00:08:47,690 --> 00:08:57,150
результуючий масив буде мати 5 Тут і 4 тут.

133
00:08:57,150 --> 00:09:00,390
А тепер зверніть увагу маркером тут.

134
00:09:00,390 --> 00:09:05,770
Всі зліва тасується,

135
00:09:05,770 --> 00:09:15,160
і все, що право unshuffled.

136
00:09:15,160 --> 00:09:17,260
І тепер ми можемо повторити процес.

137
00:09:17,260 --> 00:09:25,210
Ми виберемо випадковим індексом від 1 до 20 в даний час.

138
00:09:25,210 --> 00:09:30,650
Отже, хай наш новий я тут.

139
00:09:30,650 --> 00:09:39,370
Тепер ми переставляємо цьому я з нашим поточним нове положення тут.

140
00:09:39,370 --> 00:09:44,790
Тому ми перекачування вперед і назад, як це.

141
00:09:44,790 --> 00:09:51,630
Дозвольте мені підняти код, щоб зробити його більш конкретним.

142
00:09:51,630 --> 00:09:55,290
Почнемо з нашим вибором я -

143
00:09:55,290 --> 00:09:58,370
Ми починаємо з я дорівнює 0, ми вибираємо випадкове розташування J

144
00:09:58,370 --> 00:10:02,420
У unshuffled частина масиву, я до п-1.

145
00:10:02,420 --> 00:10:07,280
Так що, якщо я тут, вибрати випадковий індекс між тут і інша частина масиву,

146
00:10:07,280 --> 00:10:12,410
і ми переставляємо.

147
00:10:12,410 --> 00:10:17,550
Це весь код, необхідний для перемішування масиву.

148
00:10:17,550 --> 00:10:21,670
Є питання?

149
00:10:21,670 --> 00:10:25,530
>> Ну, один необхідний питання, чому це правильно?

150
00:10:25,530 --> 00:10:28,360
Чому всі перестановки різновірогідні?

151
00:10:28,360 --> 00:10:30,410
І я не буду доказ цього,

152
00:10:30,410 --> 00:10:35,970
але багато проблем в галузі комп'ютерних наук може бути доведено шляхом індукції.

153
00:10:35,970 --> 00:10:38,520
Як багато хто з вас вже знайомі з індукцією?

154
00:10:38,520 --> 00:10:40,590
Добре. Cool.

155
00:10:40,590 --> 00:10:43,610
Таким чином, ви можете довести правильність цього алгоритму простий індукції,

156
00:10:43,610 --> 00:10:49,540
де ваша індукції б, припустимо, що

157
00:10:49,540 --> 00:10:53,290
мій випадковому порядку повертає всі перестановки різновірогідні

158
00:10:53,290 --> 00:10:56,120
до першого елемента я.

159
00:10:56,120 --> 00:10:58,300
Тепер розглянемо + 1.

160
00:10:58,300 --> 00:11:02,550
І, до речі, ми вибираємо наших індексів J, щоб поміняти,

161
00:11:02,550 --> 00:11:05,230
це призводить до - і тоді ви пропрацювати деталі,

162
00:11:05,230 --> 00:11:07,390
принаймні, повний доказ того, чому цей алгоритм повертається

163
00:11:07,390 --> 00:11:12,800
кожна перестановка з рівною ймовірністю ймовірності.

164
00:11:12,800 --> 00:11:15,940
>> Гаразд, наступна проблема.

165
00:11:15,940 --> 00:11:19,170
Так що "даний масив цілих чисел, Postive, нульовий, негативний,

166
00:11:19,170 --> 00:11:21,290
написати функцію, яка обчислює максимальну суму

167
00:11:21,290 --> 00:11:24,720
будь continueous подмассіва вхідний масив ".

168
00:11:24,720 --> 00:11:28,370
Наприклад ось, у випадку, коли всі числа позитивні,

169
00:11:28,370 --> 00:11:31,320
то в даний час кращий вибір це взяти весь масив.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, дорівнює 10.

171
00:11:34,690 --> 00:11:36,780
Якщо у вас є деякі негативи там,

172
00:11:36,780 --> 00:11:38,690
У цьому випадку ми просто хочемо перших двох

173
00:11:38,690 --> 00:11:44,590
тому що вибір -1 і / або -3 принесе нашим сума вниз.

174
00:11:44,590 --> 00:11:48,120
Іноді ми, можливо, доведеться почати в середині масиву.

175
00:11:48,120 --> 00:11:53,500
Іноді ми хочемо вибрати взагалі нічого, то краще не брати.

176
00:11:53,500 --> 00:11:56,490
І іноді краще прийняти восени,

177
00:11:56,490 --> 00:12:07,510
тому що річ після того, як це супер великий. Таким чином, будь-які ідеї?

178
00:12:07,510 --> 00:12:10,970
(Студент, незрозумілі) >> Так.

179
00:12:10,970 --> 00:12:13,560
Нехай я не беру -1.

180
00:12:13,560 --> 00:12:16,170
Тоді або я вибираю 1000 і 20000,

181
00:12:16,170 --> 00:12:18,630
або я просто вибрати 3 млрд. доларів.

182
00:12:18,630 --> 00:12:20,760
Ну, кращим вибором буде приймати всі цифри.

183
00:12:20,760 --> 00:12:24,350
Це -1, незважаючи на те негативне,

184
00:12:24,350 --> 00:12:31,340
Вся сума краще, ніж якби я не приймати -1.

185
00:12:31,340 --> 00:12:36,460
Таким чином, одна з рад я згадував раніше був заявити ясно очевидно,

186
00:12:36,460 --> 00:12:40,540
і грубій силі рішення першої.

187
00:12:40,540 --> 00:12:44,340
Що таке грубої сили у вирішенні цієї проблеми? Так?

188
00:12:44,340 --> 00:12:46,890
[Джейн] Ну, я думаю, що грубій силі рішення

189
00:12:46,890 --> 00:12:52,600
можна було б додати всі можливі комбінації (нерозбірливо).

190
00:12:52,600 --> 00:12:58,250
[Ю] Добре. Таким чином, ідея Джейн прийняти всі можливі -

191
00:12:58,250 --> 00:13:01,470
Я перефразую - це прийняти всі можливі безперервної подмассіва,

192
00:13:01,470 --> 00:13:07,840
обчислити його суму, а потім взяти максимальне з усіх можливих безперервних подмассіва.

193
00:13:07,840 --> 00:13:13,310
Що однозначно ідентифікує подмассіва в моїй вхідний масив?

194
00:13:13,310 --> 00:13:17,380
Як і те, що дві речі мені потрібні? Так?

195
00:13:17,380 --> 00:13:19,970
(Студент, незрозумілі) >> праві.

196
00:13:19,970 --> 00:13:22,130
Нижня межа індексів і верхня межа індексу

197
00:13:22,130 --> 00:13:28,300
однозначно визначає безперервну подмассіва.

198
00:13:28,300 --> 00:13:31,400
[Студентка] Чи ми оцінити це масив унікальних номерів?

199
00:13:31,400 --> 00:13:34,280
[Ю] Немає Тому її питання, ми припускаючи, наш масив -

200
00:13:34,280 --> 00:13:39,000
Наша масиву всі унікальні номери, а відповіді немає.

201
00:13:39,000 --> 00:13:43,390
>> Якщо ми використовуємо нашу грубу силу рішення, то початок / кінець індексів

202
00:13:43,390 --> 00:13:47,200
однозначно визначає наші постійні подмассіва.

203
00:13:47,200 --> 00:13:51,680
Тому, якщо ми перебору всіх можливих записів початку,

204
00:13:51,680 --> 00:13:58,320
і для всіх кінцевих елементів> або =, щоб почати, і <п,

205
00:13:58,320 --> 00:14:05,570
Ви можете обчислити суму, а потім взяти максимальну суму, що ми бачили досі.

206
00:14:05,570 --> 00:14:07,880
Це зрозуміло?

207
00:14:07,880 --> 00:14:12,230
Що таке велике Про від цього рішення?

208
00:14:12,230 --> 00:14:16,660
Timewise.

209
00:14:16,660 --> 00:14:18,860
Не зовсім N ^ 2.

210
00:14:18,860 --> 00:14:25,250
Зверніть увагу, що ми ітерації від 0 до п,

211
00:14:25,250 --> 00:14:27,520
так що одна циклу.

212
00:14:27,520 --> 00:14:35,120
Ми знову повторювати практично з початку і до кінця, іншого циклу.

213
00:14:35,120 --> 00:14:37,640
І зараз, в тому, що ми повинні підвести підсумки кожного входу,

214
00:14:37,640 --> 00:14:43,810
так що це ще один цикл. Таким чином, ми маємо три вкладені цикли, п ^ 3.

215
00:14:43,810 --> 00:14:46,560
Добре. Це йде в якості відправної точки.

216
00:14:46,560 --> 00:14:53,180
Наше рішення не гірше, ніж п ^ 3.

217
00:14:53,180 --> 00:14:55,480
Чи всі розуміють грубу силу рішення?

218
00:14:55,480 --> 00:14:59,950
>> Добре. Кращим рішенням є використання ідеї називають динамічним програмуванням.

219
00:14:59,950 --> 00:15:03,040
Якщо взяти CS124, яка алгоритми й структури даних,

220
00:15:03,040 --> 00:15:05,680
Ви станете дуже добре знайомі з цією технікою.

221
00:15:05,680 --> 00:15:12,190
І ідея, спробувати створити рішення для менших проблем в першу чергу.

222
00:15:12,190 --> 00:15:17,990
Що я маю на увазі, ми в даний час не доведеться турбуватися про дві речі: початок і кінець.

223
00:15:17,990 --> 00:15:29,340
І це дратує. Що якщо б ми могли позбутися одного з цих параметрів?

224
00:15:29,340 --> 00:15:32,650
Одна з ідей полягає - we're враховуючи нашу вихідну завдання,

225
00:15:32,650 --> 00:15:37,470
знайти максимальну суму будь-яких подмассіва в діапазоні [О, N-1].

226
00:15:37,470 --> 00:15:47,400
І тепер у нас є новий підзадачі, де ми знаємо, в нашої поточної індекс г,

227
00:15:47,400 --> 00:15:52,520
Ми знаємо, що ми повинні укласти там. Наші подмассіва повинні закінчуватися на поточний індекс.

228
00:15:52,520 --> 00:15:57,640
Таким чином, залишилася проблема в тому, де ми повинні почати наш подмассіва?

229
00:15:57,640 --> 00:16:05,160
Чи має це сенс? Добре.

230
00:16:05,160 --> 00:16:12,030
Так що я закодований від цього, і давайте подивимося, що це означає.

231
00:16:12,030 --> 00:16:16,230
У codirectory, є програма під назвою подмассіва,

232
00:16:16,230 --> 00:16:19,470
і він приймає число елементів,

233
00:16:19,470 --> 00:16:25,550
і повертає максимальну суму подмассіва в моєму списку перемішуються.

234
00:16:25,550 --> 00:16:29,920
Таким чином, в цьому випадку, наш максимальний подмассіва дорівнює 3.

235
00:16:29,920 --> 00:16:34,850
І це приймати тільки за допомогою 2 і 1.

236
00:16:34,850 --> 00:16:38,050
Давайте запустимо його знову. Це також 3.

237
00:16:38,050 --> 00:16:40,950
Але на цей раз, зверніть увагу, як ми отримали 3.

238
00:16:40,950 --> 00:16:46,690
Ми взяли - ми просто візьмемо 3-сам

239
00:16:46,690 --> 00:16:49,980
тому що він оточений негативів з обох сторін,

240
00:16:49,980 --> 00:16:55,080
який принесе суму <3.

241
00:16:55,080 --> 00:16:57,820
Давайте працювати на 10 пунктів.

242
00:16:57,820 --> 00:17:03,200
На цей раз це 7, зайняти лідируючі 3 і 4.

243
00:17:03,200 --> 00:17:09,450
На цей раз це 8, і ми отримуємо, що, приймаючи 1, 4 і 3.

244
00:17:09,450 --> 00:17:16,310
Таким чином, щоб дати вам інтуїція про те, як ми можемо вирішити цю перетворюється проблеми,

245
00:17:16,310 --> 00:17:18,890
Давайте поглянемо на цю подмассіва.

246
00:17:18,890 --> 00:17:23,460
Ми дано це вхідний масив, і ми знаємо відповідь на це питання 8.

247
00:17:23,460 --> 00:17:26,359
Ми беремо 1, 4 і 3.

248
00:17:26,359 --> 00:17:29,090
Але давайте подивимося на те, як ми насправді є, що відповісти.

249
00:17:29,090 --> 00:17:34,160
Давайте подивимося на максимальній подмассіва, який закінчився на кожен з цих показників.

250
00:17:34,160 --> 00:17:40,780
Який максимальний подмассіва, який повинен закінчитися на першій позиції?

251
00:17:40,780 --> 00:17:46,310
[Студент] Zero. >> Zero. Тільки не приймайте -5.

252
00:17:46,310 --> 00:17:50,210
Ось це буде мати значення 0, а також. Так?

253
00:17:50,210 --> 00:17:56,470
(Студент, незрозумілі)

254
00:17:56,470 --> 00:17:58,960
[Ю] Ех, шкода, що це -3.

255
00:17:58,960 --> 00:18:03,220
Таким чином, це 2, це -3.

256
00:18:03,220 --> 00:18:08,690
Добре. Таким чином, -4, що максимальна подмассіва до кінця, що положення

257
00:18:08,690 --> 00:18:12,910
-4, Де знаходиться? Zero.

258
00:18:12,910 --> 00:18:22,570
Один? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
Тепер, я повинен закінчуватися в тому місці, де -2 знаходиться.

260
00:18:28,060 --> 00:18:39,330
Таким чином, 6, 5, 7, а останній дорівнює 4.

261
00:18:39,330 --> 00:18:43,480
Знаючи, що ці мої записи

262
00:18:43,480 --> 00:18:48,130
для перетвореної задачі, де я повинен закінчуватися на кожен з цих показників,

263
00:18:48,130 --> 00:18:51,410
Потім мій остаточну відповідь просто, взяти розгортки по горизонталі,

264
00:18:51,410 --> 00:18:53,580
і взяти максимальну кількість.

265
00:18:53,580 --> 00:18:55,620
Таким чином, в даному випадку це 8.

266
00:18:55,620 --> 00:19:00,010
Це означає, що максимальна подмассіва закінчується в цьому індексі,

267
00:19:00,010 --> 00:19:04,970
і почав десь перед ним.

268
00:19:04,970 --> 00:19:09,630
Чи всі розуміють це перетворюється подмассіва?

269
00:19:09,630 --> 00:19:22,160
>> Добре. Ну, давайте з'ясовувати повторення цього.

270
00:19:22,160 --> 00:19:27,990
Давайте розглянемо тільки перші кілька записів.

271
00:19:27,990 --> 00:19:35,930
Так ось це була 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
А потім було -2 тут, і які привели його до 6.

273
00:19:39,790 --> 00:19:50,800
Так що, якщо я називаю вступу на посаду я подзадача (I),

274
00:19:50,800 --> 00:19:54,910
як я можу використовувати відповіді на попереднє підзадачі

275
00:19:54,910 --> 00:19:59,360
Для відповіді на це підзадачі?

276
00:19:59,360 --> 00:20:04,550
Якщо я дивлюся на, скажімо, цей запис.

277
00:20:04,550 --> 00:20:09,190
Як я можу вирахувати відповідь 6, дивлячись на

278
00:20:09,190 --> 00:20:18,780
Поєднання цього масиву і відповідей на попередні підзадач в цьому масиві? Так?

279
00:20:18,780 --> 00:20:22,800
[Студентка] Ти масиві сум

280
00:20:22,800 --> 00:20:25,430
в положення прямо перед нею, так що 8,

281
00:20:25,430 --> 00:20:32,170
а потім додати поточну підзадачі.

282
00:20:32,170 --> 00:20:36,460
[Ю] Так їй пропозицію подивитися на ці два числа,

283
00:20:36,460 --> 00:20:40,090
це число, і це число.

284
00:20:40,090 --> 00:20:50,130
Таким чином, це 8 відноситься до відповіддю на підзадачі (я - 1).

285
00:20:50,130 --> 00:20:57,300
І давайте називати мого вхідного масиву A.

286
00:20:57,300 --> 00:21:01,470
Для того щоб знайти максимальний подмассіва, який закінчується в позиції I,

287
00:21:01,470 --> 00:21:03,980
У мене є два варіанти: я можу або продовжити подмассіва

288
00:21:03,980 --> 00:21:09,790
, Яка закінчилася в попередній індекс, або почати нову масиву.

289
00:21:09,790 --> 00:21:14,190
Якби я був продовжити подмассіва, який почався в попередній індекс,

290
00:21:14,190 --> 00:21:19,260
Потім максимальну суму я можу досягти, це відповідь на попередній підзадачі

291
00:21:19,260 --> 00:21:24,120
плюс поточний елемент масиву.

292
00:21:24,120 --> 00:21:27,550
Але, у мене є вибір, починаючи новий подмассіва,

293
00:21:27,550 --> 00:21:30,830
У цьому випадку сума дорівнює 0.

294
00:21:30,830 --> 00:21:42,860
Так що відповідь макс 0, подзадача - 1, а також поточний елемент масиву.

295
00:21:42,860 --> 00:21:46,150
Чи означає це повторення сенсу?

296
00:21:46,150 --> 00:21:50,840
Наші рецидиву, як ми тільки що виявили, це я подзадача

297
00:21:50,840 --> 00:21:54,740
дорівнює максимуму попереднього підзадачі плюс мій поточний елемент масиву,

298
00:21:54,740 --> 00:22:01,490
що означає продовження попередньої подмассіва,

299
00:22:01,490 --> 00:22:07,250
або 0, створити нову подмассіва на мій поточний індекс.

300
00:22:07,250 --> 00:22:10,060
І як тільки ми створили цю таблицю рішень, то наш остаточну відповідь,

301
00:22:10,060 --> 00:22:13,950
просто робити лінійні розгортки через підзадачі масиву

302
00:22:13,950 --> 00:22:19,890
і взяти максимальну кількість.

303
00:22:19,890 --> 00:22:23,330
Це точна реалізація того, що я тільки що сказав.

304
00:22:23,330 --> 00:22:27,320
Таким чином, ми створюємо новий масив підзадачі, підзадачі.

305
00:22:27,320 --> 00:22:32,330
Перший запис або 0, або перший запис, максимальне з цих двох.

306
00:22:32,330 --> 00:22:35,670
А для решти підзадач

307
00:22:35,670 --> 00:22:39,810
ми використовуємо точне повторення Ми тільки що виявили.

308
00:22:39,810 --> 00:22:49,960
Тепер обчислимо максимальну нашого масиву підзадач, і це наш остаточну відповідь.

309
00:22:49,960 --> 00:22:54,130
>> Так скільки місця ми використовуємо в цьому алгоритмі?

310
00:22:54,130 --> 00:23:01,470
Якщо ви тільки приймати CS50, то ви не могли б обговорюватися просторі дуже багато.

311
00:23:01,470 --> 00:23:07,750
Ну, одне слід зазначити, що я назвав Танос тут з розміром п.

312
00:23:07,750 --> 00:23:13,590
Що це запропонувати вам?

313
00:23:13,590 --> 00:23:17,450
Цей алгоритм використовує лінійний простір.

314
00:23:17,450 --> 00:23:21,030
Чи можемо ми зробити краще?

315
00:23:21,030 --> 00:23:30,780
Є що-небудь, що ви помітите, що є необхідною для обчислення остаточну відповідь?

316
00:23:30,780 --> 00:23:33,290
Я думаю, краще Питання в тому, яка інформація

317
00:23:33,290 --> 00:23:40,680
ми не повинні нести весь шлях до кінця?

318
00:23:40,680 --> 00:23:44,280
Тепер, якщо ми подивимося на ці дві лінії,

319
00:23:44,280 --> 00:23:47,720
ми дбаємо лише про попередню підзадачі,

320
00:23:47,720 --> 00:23:50,910
і ми дбаємо лише про максимальну які ми коли-небудь бачили досі.

321
00:23:50,910 --> 00:23:53,610
Щоб обчислити наш остаточну відповідь, нам не потрібно весь масив.

322
00:23:53,610 --> 00:23:57,450
Нам потрібно тільки останній номер, дві останні цифри.

323
00:23:57,450 --> 00:24:02,630
Останній номер підзадачі масиву, а останній номер максимуму.

324
00:24:02,630 --> 00:24:07,380
Так, справді, ми можемо поєднати ці петлі разом

325
00:24:07,380 --> 00:24:10,460
і перейти від лінійного простору постійної просторі.

326
00:24:10,460 --> 00:24:15,830
Даної суми до цих пір, тут заміняє роль підзадачі, наші підзадачі масиву.

327
00:24:15,830 --> 00:24:20,020
Таким чином, поточна сума, досі, є відповіддю на попередній підзадачі.

328
00:24:20,020 --> 00:24:23,450
І ця сума досі займає місце нашого макс.

329
00:24:23,450 --> 00:24:28,100
Ми обчислимо максимальну, як ми йдемо разом.

330
00:24:28,100 --> 00:24:30,890
І ось ми йдемо від лінійного простору постійної просторі,

331
00:24:30,890 --> 00:24:36,650
і ми також маємо лінійне рішення наших подмассіва проблеми.

332
00:24:36,650 --> 00:24:40,740
>> Ці питання ви отримаєте під час інтерв'ю.

333
00:24:40,740 --> 00:24:44,450
Яка часова складність, що простір складності?

334
00:24:44,450 --> 00:24:50,600
Чи можете ви зробити краще? Є речі, які не є необхідними, щоб тримати навколо?

335
00:24:50,600 --> 00:24:55,270
Я зробив це, щоб виділити аналізів, які ви повинні прийняти на свій власний

336
00:24:55,270 --> 00:24:57,400
як ви працюєте через ці проблеми.

337
00:24:57,400 --> 00:25:01,710
Завжди можна запитати себе: "Чи можу я зробити краще?"

338
00:25:01,710 --> 00:25:07,800
У самому справі, ми можемо зробити краще, ніж це?

339
00:25:07,800 --> 00:25:10,730
Сортувати питання з підступом. Ви не можете, тому що ви повинні

340
00:25:10,730 --> 00:25:13,590
принаймні читати внесок у проблему.

341
00:25:13,590 --> 00:25:15,570
Тому той факт, що вам потрібно принаймні читати внесок у проблеми

342
00:25:15,570 --> 00:25:19,580
означає, що ви не можете зробити краще, ніж лінійний час,

343
00:25:19,580 --> 00:25:22,870
і ви не можете зробити краще, ніж постійне місце.

344
00:25:22,870 --> 00:25:27,060
Так що це, насправді, краще рішення цієї проблеми.

345
00:25:27,060 --> 00:25:33,040
Питання? Добре.

346
00:25:33,040 --> 00:25:35,190
>> Проблема Фондовий ринок:

347
00:25:35,190 --> 00:25:38,350
"Враховуючи масив цілих чисел п, позитивною, нульовою або негативною,

348
00:25:38,350 --> 00:25:41,680
, Які являють собою ціну акції протягом декількох днів п,

349
00:25:41,680 --> 00:25:44,080
написати функцію для обчислення максимального прибутку ви можете зробити

350
00:25:44,080 --> 00:25:49,350
за умови, що ви купуєте і продаєте рівно 1 акція в рамках цих п днів ".

351
00:25:49,350 --> 00:25:51,690
По суті, ми хочемо купити дешево, продавай дорого.

352
00:25:51,690 --> 00:25:58,580
І ми хочемо, щоб з'ясувати, кращий прибутку ми можемо зробити.

353
00:25:58,580 --> 00:26:11,500
Повертаючись до моєї наконечником, що відразу ясно, проста відповідь, але це повільно?

354
00:26:11,500 --> 00:26:17,690
Так? (Студент, незрозумілі) >> Так.

355
00:26:17,690 --> 00:26:21,470
>> Так ви б просто піти, хоча і подивіться на ціни акцій

356
00:26:21,470 --> 00:26:30,550
в кожен момент часу, (нерозбірливо).

357
00:26:30,550 --> 00:26:33,990
[Ю] Добре, так що її рішення - її пропозицію обчислювальних

358
00:26:33,990 --> 00:26:37,380
найнижчі і найвищі обчислення не обов'язково працювати

359
00:26:37,380 --> 00:26:42,470
тому що висока може відбутися до найнижчих.

360
00:26:42,470 --> 00:26:47,340
Так що це груба сила вирішення цієї проблеми?

361
00:26:47,340 --> 00:26:53,150
Які дві речі, які мені потрібно, щоб однозначно визначити прибуток я можу зробити? Право.

362
00:26:53,150 --> 00:26:59,410
Рішення грубої сили - о, так, пропозицію Джорджа це нам потрібно тільки два дні

363
00:26:59,410 --> 00:27:02,880
для однозначного визначення прибутку ці два дні.

364
00:27:02,880 --> 00:27:06,660
Таким чином, ми обчислимо кожної пари, як покупка / продаж,

365
00:27:06,660 --> 00:27:12,850
обчислити прибуток, яка може бути позитивним чи негативним або нульовим.

366
00:27:12,850 --> 00:27:18,000
Обчислити максимальний прибуток, що ми робимо після перебирає всі пари днів.

367
00:27:18,000 --> 00:27:20,330
Це буде наш остаточну відповідь.

368
00:27:20,330 --> 00:27:25,730
І це рішення буде O (N ^ 2), тому що існує п вибрати дві пари -

369
00:27:25,730 --> 00:27:30,270
днів, які ви можете вибирати між кінця дня.

370
00:27:30,270 --> 00:27:32,580
Гаразд, так що я не збираюся перейти на грубій силі рішення тут.

371
00:27:32,580 --> 00:27:37,420
Я збираюся розповісти вам, що є п § п рішення.

372
00:27:37,420 --> 00:27:45,550
Який алгоритм в даний час ви знаєте, що це п § п?

373
00:27:45,550 --> 00:27:50,730
Це не питання з підступом.

374
00:27:50,730 --> 00:27:54,790
>> Злиття роду. Злиття роду п § п,

375
00:27:54,790 --> 00:27:57,760
і справді, одним із способів вирішення цієї проблеми є використання

376
00:27:57,760 --> 00:28:04,400
свого роду злиття роду ідея називається, в загальному, розділяй і володарюй.

377
00:28:04,400 --> 00:28:07,570
А ідея полягає в наступному.

378
00:28:07,570 --> 00:28:12,400
Ви хочете, щоб обчислити оптимальну купівлі / продажу пари в лівій половині.

379
00:28:12,400 --> 00:28:16,480
Знайти кращий прибутку ви можете зробити, тільки з першою російською протягом двох днів.

380
00:28:16,480 --> 00:28:19,780
Потім ви хочете oompute кращі покупки / продажу пари на правій половині,

381
00:28:19,780 --> 00:28:23,930
так що останні п протягом двох днів.

382
00:28:23,930 --> 00:28:32,400
А тепер питання в тому, як ми можемо об'єднати ці рішення разом?

383
00:28:32,400 --> 00:28:36,320
Так? (Студент, незрозумілі)

384
00:28:36,320 --> 00:28:49,890
>> Добре. Отже, дозвольте мені намалювати картинку.

385
00:28:49,890 --> 00:29:03,870
Так? (Джордж, незрозумілі)

386
00:29:03,870 --> 00:29:06,450
>> Саме так. Рішення Джорджа це абсолютно вірно.

387
00:29:06,450 --> 00:29:10,040
Так що його пропозиція є, в першу обчислити оптимальну покупку / продаж пари,

388
00:29:10,040 --> 00:29:16,050
і що відбувається в лівій половині, так що давайте називати це лівий, лівий.

389
00:29:16,050 --> 00:29:20,790
Краща покупка / продаж пара, яка відбувається в правій половині.

390
00:29:20,790 --> 00:29:25,180
Але якщо ми тільки в порівнянні цих двох чисел, ми пропустили випадок

391
00:29:25,180 --> 00:29:30,460
де купити тут і продати десь в правій половині.

392
00:29:30,460 --> 00:29:33,810
Ми купуємо в лівій половині, продажу в правій половині.

393
00:29:33,810 --> 00:29:38,490
І найкращий спосіб обчислити оптимальну купити / продати пару, яка охоплює обидві половинки

394
00:29:38,490 --> 00:29:43,480
є обчислення мінімального тут і вирахувати максимальну тут

395
00:29:43,480 --> 00:29:45,580
і взяти їх різницю.

396
00:29:45,580 --> 00:29:50,850
Таким чином, два випадки, коли купівлі / продажу пари відбувається тільки тут,

397
00:29:50,850 --> 00:30:01,910
Тільки тут, або на обох половинах визначається цими трьома числами.

398
00:30:01,910 --> 00:30:06,450
Таким чином, наш алгоритм об'єднати наші рішення разом,

399
00:30:06,450 --> 00:30:08,350
Ми хочемо обчислити оптимальну покупку / продаж пари

400
00:30:08,350 --> 00:30:13,120
де ми купуємо на лівій половині і продавати на правій половині.

401
00:30:13,120 --> 00:30:16,740
І кращий спосіб зробити це полягає в обчисленні найнижчою ціною в першій половині,

402
00:30:16,740 --> 00:30:20,360
найвища ціна в правій половині, і взяти їх різницю.

403
00:30:20,360 --> 00:30:25,390
Отримані три прибулих, ці три цифри, ви берете максимум три,

404
00:30:25,390 --> 00:30:32,720
і це найкраща прибуток ви можете зробити за ці перші і кінця днів.

405
00:30:32,720 --> 00:30:36,940
Тут важливі лінії червоного кольору.

406
00:30:36,940 --> 00:30:41,160
Це рекурсивний виклик для обчислення відповіді в лівій половині.

407
00:30:41,160 --> 00:30:44,760
Це рекурсивний виклик для обчислення відповіді в правій половині.

408
00:30:44,760 --> 00:30:50,720
Ці дві петлі для обчислення хв і макс на ліву і праву половини, відповідно.

409
00:30:50,720 --> 00:30:54,970
Тепер я обчислити прибуток, яка охоплює обидві половинки,

410
00:30:54,970 --> 00:31:00,530
і остаточну відповідь максимальна з цих трьох.

411
00:31:00,530 --> 00:31:04,120
Добре.

412
00:31:04,120 --> 00:31:06,420
>> Так що, впевнений, у нас є алгоритм, але більше питання в тому,

413
00:31:06,420 --> 00:31:08,290
що тимчасова складність цього?

414
00:31:08,290 --> 00:31:16,190
І причина, чому я згадав, сортування злиттям в тому, що ця форма розділити відповідь

415
00:31:16,190 --> 00:31:19,200
на два, а потім об'єднувати наші рішення разом

416
00:31:19,200 --> 00:31:23,580
Саме вид сортування злиттям.

417
00:31:23,580 --> 00:31:33,360
Отже, дозвольте мені пройти тривалості.

418
00:31:33,360 --> 00:31:41,340
Якщо ми визначили функцію T (N), що число кроків

419
00:31:41,340 --> 00:31:50,010
для п днів,

420
00:31:50,010 --> 00:31:54,350
наші рекурсивні виклики

421
00:31:54,350 --> 00:32:00,460
кожен буде коштувати т (п / 2),

422
00:32:00,460 --> 00:32:03,540
і є два з цих викликів.

423
00:32:03,540 --> 00:32:10,020
Тепер мені потрібно обчислити мінімум лівій половині,

424
00:32:10,020 --> 00:32:17,050
який я можу зробити в п / 2, плюс максимум в правій половині.

425
00:32:17,050 --> 00:32:20,820
Так що це просто п.

426
00:32:20,820 --> 00:32:25,050
А потім плюс деяка постійна робота.

427
00:32:25,050 --> 00:32:27,770
І це рекурентне рівняння

428
00:32:27,770 --> 00:32:35,560
Саме рекурентне рівняння для сортування злиттям.

429
00:32:35,560 --> 00:32:39,170
І всі ми знаємо, що сортування злиттям п § п часу.

430
00:32:39,170 --> 00:32:46,880
Таким чином, наш алгоритм також п § п часу.

431
00:32:46,880 --> 00:32:52,220
Чи означає це, ітерації сенс?

432
00:32:52,220 --> 00:32:55,780
Тільки коротке резюме цього:

433
00:32:55,780 --> 00:32:59,170
Т (п) є ряд кроків, щоб обчислити максимальний прибуток

434
00:32:59,170 --> 00:33:02,750
протягом доби з.

435
00:33:02,750 --> 00:33:06,010
Те, як ми розділилися наші рекурсивні виклики

436
00:33:06,010 --> 00:33:11,980
є викликом нашого рішення у перші дні п / 2,

437
00:33:11,980 --> 00:33:14,490
так що це один виклик,

438
00:33:14,490 --> 00:33:16,940
а потім ми знову закликаємо другої половини.

439
00:33:16,940 --> 00:33:20,440
Так от двома викликами.

440
00:33:20,440 --> 00:33:25,310
І тоді ми знаходимо мінімум на лівій половині, яку ми можемо зробити в лінійному часу,

441
00:33:25,310 --> 00:33:29,010
знайти максимум в правій половині, яку ми можемо зробити в лінійному часу.

442
00:33:29,010 --> 00:33:31,570
Таким чином, п / 2 + п / 2 знаходиться всього в с.

443
00:33:31,570 --> 00:33:36,020
Тоді у нас є постійна робота, яка, як робити арифметику.

444
00:33:36,020 --> 00:33:39,860
Це рекурентне рівняння в точності повторення рівняння для сортування злиттям.

445
00:33:39,860 --> 00:33:55,490
Таким чином, наш алгоритм перемішування також п п увійти.

446
00:33:55,490 --> 00:33:58,520
Так скільки місця ми використовуємо?

447
00:33:58,520 --> 00:34:04,910
Давайте повернемося до коду.

448
00:34:04,910 --> 00:34:09,420
>> Кращий питання, скільки кадрів стека ми коли-небудь в будь-який момент?

449
00:34:09,420 --> 00:34:11,449
Так як ми використовуємо рекурсію,

450
00:34:11,449 --> 00:34:23,530
число кадрів стека визначає наше використання простору.

451
00:34:23,530 --> 00:34:29,440
Розглянемо N = 8.

452
00:34:29,440 --> 00:34:36,889
Ми закликаємо перемішати 8,

453
00:34:36,889 --> 00:34:41,580
, Який буде викликати випадковому порядку на перших чотирьох записів,

454
00:34:41,580 --> 00:34:46,250
, Який буде викликати перемішування на перших двох записів.

455
00:34:46,250 --> 00:34:51,550
Таким чином, наш стек - це наш стек.

456
00:34:51,550 --> 00:34:54,980
І тоді ми називаємо перемішати ще раз на 1,

457
00:34:54,980 --> 00:34:58,070
і це те, що наша база випадок, тому ми негайно повернутися.

458
00:34:58,070 --> 00:35:04,700
Чи є у нас коли-небудь більше, ніж це кількість кадрів стека?

459
00:35:04,700 --> 00:35:08,880
Ні, тому що кожен раз, коли ми робимо виклик,

460
00:35:08,880 --> 00:35:10,770
рекурсивний виклик для перемішування,

461
00:35:10,770 --> 00:35:13,950
ми ділимо нашу розміром в половину.

462
00:35:13,950 --> 00:35:17,020
Таким чином, максимальна кількість кадрів стека ми коли-небудь в будь-який момент

463
00:35:17,020 --> 00:35:28,460
порядку журналу N кадрів стека.

464
00:35:28,460 --> 00:35:42,460
Кожен кадр стека має постійне місце,

465
00:35:42,460 --> 00:35:44,410
і, отже, загальний обсяг простору,

466
00:35:44,410 --> 00:35:49,240
максимальний обсяг простору, ми коли-небудь використовувати це O (журнал N) простору

467
00:35:49,240 --> 00:36:03,040
де п-кількість днів.

468
00:36:03,040 --> 00:36:07,230
>> Тепер, завжди запитуйте себе: "Чи можемо ми зробити краще?"

469
00:36:07,230 --> 00:36:12,390
І зокрема, ми можемо скоротити цю проблему ми вже вирішили?

470
00:36:12,390 --> 00:36:20,040
Підказка: ми тільки обговорювали два інших проблем до цього, і він не збирається бути перемішати.

471
00:36:20,040 --> 00:36:26,200
Ми можемо перетворити цю проблему фондового ринку в максимальній проблеми подмассіва.

472
00:36:26,200 --> 00:36:40,100
Як ми можемо це зробити?

473
00:36:40,100 --> 00:36:42,570
Один з вас? Еммі?

474
00:36:42,570 --> 00:36:47,680
(Emmy, незрозумілі)

475
00:36:47,680 --> 00:36:53,860
[Ю] Саме так.

476
00:36:53,860 --> 00:36:59,940
Таким чином, максимальна подмассіва проблеми,

477
00:36:59,940 --> 00:37:10,610
Ми шукаємо сума по безперервній подмассіва.

478
00:37:10,610 --> 00:37:16,230
І пропозиція Еммі завдання акції,

479
00:37:16,230 --> 00:37:30,720
Розглянемо зміни, або дельти.

480
00:37:30,720 --> 00:37:37,440
І картина ця є - це ціна акції,

481
00:37:37,440 --> 00:37:42,610
але якщо б ми взяли різницю між кожним день поспіль -

482
00:37:42,610 --> 00:37:45,200
Отже, ми бачимо, що максимальна ціна, максимальна прибуток ми могли б зробити

483
00:37:45,200 --> 00:37:50,070
, Якщо ми купуємо і продаємо тут тут.

484
00:37:50,070 --> 00:37:54,240
Але давайте подивимося на безперервне - давайте подивимося на подмассіва проблеми.

485
00:37:54,240 --> 00:38:02,510
Так от, ми можемо зробити - походить від сих до сих,

486
00:38:02,510 --> 00:38:08,410
у нас є позитивні зміни, а потім збирається звідси тут ми маємо негативне зміна.

487
00:38:08,410 --> 00:38:14,220
Але тоді, переходячи від сюди, щоб тут ми маємо величезну позитивну зміну.

488
00:38:14,220 --> 00:38:20,930
І ці зміни, які ми хочемо підвести підсумки, щоб отримати нашу кінцеву прибуток.

489
00:38:20,930 --> 00:38:25,160
Тоді у нас більше негативних змін тут.

490
00:38:25,160 --> 00:38:29,990
Ключ до зниження нашому складі проблемою в нашій максимальної проблеми подмассіва

491
00:38:29,990 --> 00:38:36,630
є розгляд дельти між днів.

492
00:38:36,630 --> 00:38:40,630
Таким чином, ми створюємо новий масив з ім'ям дельти,

493
00:38:40,630 --> 00:38:43,000
ініціалізація першого елемента рівним 0,

494
00:38:43,000 --> 00:38:46,380
а потім для кожної дельти (I), нехай це буде різниця

495
00:38:46,380 --> 00:38:52,830
моєї вхідний масив (I), і масив (я - 1).

496
00:38:52,830 --> 00:38:55,530
Тоді ми називаємо нашою рутинною процедурою для максимального подмассіва

497
00:38:55,530 --> 00:39:01,500
проходить в масиві дельти.

498
00:39:01,500 --> 00:39:06,440
І тому, що максимальна подмассіва є лінійним часом,

499
00:39:06,440 --> 00:39:09,370
і це скорочення, цей процес створення цієї дельти масиву,

500
00:39:09,370 --> 00:39:11,780
Також лінійного часу,

501
00:39:11,780 --> 00:39:19,060
то остаточне рішення запасів O (п) плюс робота O (п) роботи, як і раніше O (п) роботи.

502
00:39:19,060 --> 00:39:23,900
Тому у нас є лінійний час вирішення нашої проблеми.

503
00:39:23,900 --> 00:39:29,610
Чи всі розуміють це перетворення?

504
00:39:29,610 --> 00:39:32,140
>> Загалом, хороша ідея, що ви завжди повинні мати

505
00:39:32,140 --> 00:39:34,290
це спробувати зменшити нова проблема, що ви бачите.

506
00:39:34,290 --> 00:39:37,700
Якщо воно виглядає знайомо стара проблема,

507
00:39:37,700 --> 00:39:39,590
спробуйте зменшити його стара проблема.

508
00:39:39,590 --> 00:39:41,950
І якщо ви можете використовувати всі інструменти, які ви використовували на старі проблеми

509
00:39:41,950 --> 00:39:46,450
для вирішення нової проблеми.

510
00:39:46,450 --> 00:39:49,010
Таким чином, щоб підбивати підсумки, технічне інтерв'ю складним завданням.

511
00:39:49,010 --> 00:39:52,280
Ці проблеми, ймовірно, деякі з найбільш складних проблем

512
00:39:52,280 --> 00:39:54,700
що ви можете побачити в одному з інтерв'ю,

513
00:39:54,700 --> 00:39:57,690
так що якщо ви не розумієте, всі проблеми, які я тільки покриті, це нормально.

514
00:39:57,690 --> 00:40:01,080
Ось деякі з найбільш складних проблем.

515
00:40:01,080 --> 00:40:03,050
Практика, практика, практика.

516
00:40:03,050 --> 00:40:08,170
Я дала багато проблем в роздавальний матеріал, так виразно перевірити ці.

517
00:40:08,170 --> 00:40:11,690
І удачі на інтерв'ю. Всі мої ресурси, розміщені на цю посилання,

518
00:40:11,690 --> 00:40:15,220
і один з моїх старших друзів запропонував зробити макет технічне інтерв'ю,

519
00:40:15,220 --> 00:40:22,050
так що якщо ви зацікавилися, лист буде Яо, що адреса електронної пошти.

520
00:40:22,050 --> 00:40:26,070
Якщо у вас є питання, ви можете запитати мене.

521
00:40:26,070 --> 00:40:28,780
Як ви, хлопці, є конкретні питання, пов'язані з технічними інтерв'ю

522
00:40:28,780 --> 00:40:38,440
або будь-які проблеми, які ми бачили до сих пір?

523
00:40:38,440 --> 00:40:49,910
Добре. Ну, удачі на інтерв'ю.

524
00:40:49,910 --> 00:40:52,910
[CS50.TV]