1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [संगोष्ठी: तकनीकी साक्षात्कार]

2
00:00:02,640 --> 00:00:04,630
[केनी यू, हार्वर्ड विश्वविद्यालय]

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
मैं एक पूर्व सीएस में TF हूँ, और काश मैं यह था जब मैं एक underclassman था,

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 या एक गूगल डॉक्टर तो वे आप कोडिंग रहते देख सकते हैं

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
वे आप से पूछना पसंद करेंगे, जो समय और अंतरिक्ष जटिलता, बड़ा हे है?

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
वे करने के लिए सबसे अच्छा समाधान 1 खोजने की कोशिश करने का प्रयास है,

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
बड़ी हे समय जटिलता या अंतरिक्ष जटिलता,

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
तो सरल एल्गोरिथ्म के साथ आने के लिए डर 1 मत हो

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
N integers की एक सरणी को देखते हुए, एक समारोह में कहा कि सरणी shuffles लिखने

77
00:04:14,790 --> 00:04:20,209
जगह ऐसी है कि n integers के सभी permutations समान रूप से होने की संभावना है. "

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
मैं आप n integers की एक सरणी देते हैं, और मैं तुम्हें यह मिश्रण करने के लिए करना चाहते हैं.

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 से नौ के लिए,

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
कुछ विचारों को क्या कर रहे हैं? आप n ^ 2, n लॉग, n के रूप में यह कर सकते हैं?

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
1 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
और कहा कि एक हे लागत (एन)

113
00:07:21,600 --> 00:07:26,100
क्योंकि जो अगर हम 1 तत्व निकाल?

114
00:07:26,100 --> 00:07:29,670
तो प्रत्येक को हटाने के लिए, हम दूर -

115
00:07:29,670 --> 00:07:32,170
प्रत्येक को हटाने के एक हे (एन) आपरेशन incurs,

116
00:07:32,170 --> 00:07:41,520
और जब से हम removals n है, यह एक हे घसीटना (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
या फेरबदल फिशर Yates.

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
लेकिन हमारे इनपुट / आउटपुट के लिए दो arrays का उपयोग करने के बजाय,

124
00:08:08,580 --> 00:08:13,590
हम सरणी के पहले भाग का उपयोग हमारे shuffled भाग का ट्रैक रखने के लिए,

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
बाईं करने के लिए सब कुछ shuffled है,

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 के बराबर है, हम एक यादृच्छिक स्थान जम्मू लेने

144
00:09:58,370 --> 00:10:02,420
सरणी के unshuffled भाग में, मैं n-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
ठीक है. कूल.

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
और जिस तरह से हम हमारी अनुक्रमणिका जम्मू स्वैप करने के लिए चुनते हैं,

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 subarray की. "

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
(छात्र unintelligible) >> हाँ.

179
00:12:10,970 --> 00:12:13,560
मान लीजिए मैं -1 से नहीं लेते हैं.

180
00:12:13,560 --> 00:12:16,170
तो या तो मैं 1,000 और 20,000 चुनते हैं,

181
00:12:16,170 --> 00:12:18,630
या मैं सिर्फ तीन अरब का चयन करें.

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
और जानवर बल समाधान 1.

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
करने के लिए सभी संभव संयोजनों (unintelligible) जोड़ना होगा.

190
00:12:52,600 --> 00:12:58,250
[यू] ठीक है. तो जेन विचार करने के लिए हर संभव ले रहा है -

191
00:12:58,250 --> 00:13:01,470
मैं paraphrasing हूँ - हर संभव निरंतर subarray ले रहा है,

192
00:13:01,470 --> 00:13:07,840
अपनी राशि की गणना करने के लिए, और फिर सभी संभव निरंतर subarrays के अधिकतम ले.

193
00:13:07,840 --> 00:13:13,310
क्या विशिष्ट अपने इनपुट सरणी में एक subarray को दिखाता है?

194
00:13:13,310 --> 00:13:17,380
की तरह, दो बातें मैं क्या जरूरत है? हाँ?

195
00:13:17,380 --> 00:13:19,970
(छात्र unintelligible) >> ठीक है.

196
00:13:19,970 --> 00:13:22,130
एक कम सूचकांक और एक ऊपरी बाध्य सूचकांक पर बाध्य

197
00:13:22,130 --> 00:13:28,300
विशिष्ट एक सतत subarray निर्धारित करता है.

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
विशिष्ट हमारे निरंतर subarray निर्धारित करता है.

203
00:13:47,200 --> 00:13:51,680
तो अगर हम सभी संभव शुरू प्रविष्टियों के लिए पुनरावृति

204
00:13:51,680 --> 00:13:58,320
और अंत प्रविष्टियों के लिए> या = शुरू करने के लिए, करने के लिए और <n,

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
^ 2 काफी नहीं n.

210
00:14:18,860 --> 00:14:25,250
ध्यान दें कि हम 0 से n पुनरावृति

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
इतना है कि पाश के लिए एक और है. तो हम तीन loops के लिए नेस्टेड n ^ 3 है.

215
00:14:43,810 --> 00:14:46,560
ठीक है. यह एक प्रारंभिक बिंदु के रूप में चला जाता है.

216
00:14:46,560 --> 00:14:53,180
हमारी समाधान नहीं n ^ 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
और विचार करने के लिए छोटी समस्याओं के लिए समाधान 1 का निर्माण करने की कोशिश है.

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
हम हमारे मूल समस्या को देखते हुए, एक विचार करने के लिए है

225
00:15:32,650 --> 00:15:37,470
एक रेंज में किसी भी subarray की अधिकतम राशि [ओ, n-1] में पाते हैं.

226
00:15:37,470 --> 00:15:47,400
और अब हम हमारे वर्तमान सूचकांक में मैं एक नया subproblem है, जहां हम जानते है,

227
00:15:47,400 --> 00:15:52,520
हम जानते हैं कि हम वहाँ निष्कर्ष निकालना चाहिए. हमारी subarray वर्तमान सूचकांक में समाप्त होना चाहिए.

228
00:15:52,520 --> 00:15:57,640
तो शेष समस्या है, जहां हम हमारे subarray शुरू कर देना चाहिए?

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 में, वहाँ एक subarray कार्यक्रम बुलाया है,

232
00:16:16,230 --> 00:16:19,470
और यह आइटम्स की संख्या लेता है,

233
00:16:19,470 --> 00:16:25,550
और यह मेरे shuffled सूची में अधिक से अधिक subarray राशि देता है.

234
00:16:25,550 --> 00:16:29,920
तो इस मामले में, हमारे अधिक से अधिक subarray 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 है, और हम 4 1, 3 और लेने के द्वारा प्राप्त करने के लिए.

244
00:17:09,450 --> 00:17:16,310
तो आप कैसे पर एक अंतर्ज्ञान दे हम इस तब्दील समस्या को हल कर सकते हैं,

245
00:17:16,310 --> 00:17:18,890
चलो इस subarray पर एक नज़र ले.

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
चलो अधिकतम subarray कि इन सूचकांकों में से प्रत्येक में समाप्त हो गया पर देखो.

250
00:17:34,160 --> 00:17:40,780
अधिकतम subarray है कि पहले की स्थिति में समाप्त करने के लिए है क्या है?

251
00:17:40,780 --> 00:17:46,310
शून्य [छात्र]. शून्य. >> बस -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, कि स्थिति को समाप्त करने के लिए अधिक से अधिक subarray क्या है

257
00:18:08,690 --> 00:18:12,910
जहां पर -4 है? शून्य.

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
इसका मतलब है कि अधिक से अधिक subarray इस सूचकांक में समाप्त होता है,

267
00:19:00,010 --> 00:19:04,970
और इसके पहले कहीं से शुरू कर दिया.

268
00:19:04,970 --> 00:19:09,630
क्या हर कोई इस तब्दील subarray समझ में आया?

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) subproblem,

274
00:19:50,800 --> 00:19:54,910
मैं पिछले एक subproblem कैसे जवाब का उपयोग कर सकते हैं

275
00:19:54,910 --> 00:19:59,360
के लिए इस subproblem का जवाब?

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
इस सरणी और इस सरणी में पिछले subproblems जवाब का एक संयोजन है? हाँ?

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
और फिर आप वर्तमान subproblem जोड़ने के.

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 subproblem के लिए जवाब (1 i) को संदर्भित करता है.

285
00:20:50,130 --> 00:20:57,300
और मेरे इनपुट सरणी ए कॉल

286
00:20:57,300 --> 00:21:01,470
आदेश में खोजने के लिए एक अधिकतम subarray है कि मैं स्थिति पर समाप्त होता है,

287
00:21:01,470 --> 00:21:03,980
मैं दो विकल्प हैं: मैं या तो subarray जारी रख सकते हैं

288
00:21:03,980 --> 00:21:09,790
कि पिछले सूचकांक में समाप्त हो गया, या एक नई सरणी शुरू.

289
00:21:09,790 --> 00:21:14,190
अगर मैं subarray कि पिछले सूचकांक में शुरू जारी थे,

290
00:21:14,190 --> 00:21:19,260
तो मैं अधिकतम राशि प्राप्त कर सकते हैं पिछले subproblem का जवाब है

291
00:21:19,260 --> 00:21:24,120
साथ मौजूदा सरणी प्रविष्टि.

292
00:21:24,120 --> 00:21:27,550
लेकिन, मैं भी एक नया subarray शुरू की पसंद है,

293
00:21:27,550 --> 00:21:30,830
जो मामले में योग 0 है.

294
00:21:30,830 --> 00:21:42,860
1, प्लस वर्तमान सरणी प्रविष्टि तो जवाब 0 के अधिकतम, subproblem मैं है.

295
00:21:42,860 --> 00:21:46,150
इस पुनरावृत्ति मतलब होता है?

296
00:21:46,150 --> 00:21:50,840
हमारे पुनरावृत्ति, subproblem मैं, के रूप में हम अभी पता चला है

297
00:21:50,840 --> 00:21:54,740
पिछले subproblem की अधिकतम प्लस मेरे वर्तमान सरणी प्रविष्टि के लिए बराबर है,

298
00:21:54,740 --> 00:22:01,490
जिसका मतलब है कि पिछले subarray जारी,

299
00:22:01,490 --> 00:22:07,250
या 0, मेरे वर्तमान सूचकांक में एक नया subarray शुरू.

300
00:22:07,250 --> 00:22:10,060
और एक बार हम समाधान की इस तालिका को बनाया गया है, तो हमारे अंतिम जवाब

301
00:22:10,060 --> 00:22:13,950
सिर्फ subproblem सरणी पार एक रैखिक झाडू

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
तो हम एक नया subproblem सरणी, subproblems.

305
00:22:27,320 --> 00:22:32,330
पहली प्रविष्टि या तो 0 या 1 प्रविष्टि, उन दोनों के अधिकतम है.

306
00:22:32,330 --> 00:22:35,670
और subproblems के बाकी के लिए

307
00:22:35,670 --> 00:22:39,810
हम सही पुनरावृत्ति हम अभी पता चला है.

308
00:22:39,810 --> 00:22:49,960
अब हम हमारे subproblems सरणी के अधिकतम गणना और कि हमारी अंतिम जवाब है.

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
खैर, एक बात नोट करने के लिए है कि मैं malloc आकार n के साथ यहाँ बुलाया.

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
हम केवल पिछले subproblem के बारे में परवाह है,

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
Subproblem सरणी, अधिकतम के लिए और पिछले संख्या के लिए अंतिम संख्या.

324
00:24:02,630 --> 00:24:07,380
तो, वास्तव में, हम इन loops फ्यूज के साथ कर सकते हैं

325
00:24:07,380 --> 00:24:10,460
और रैखिक अंतरिक्ष से लगातार अंतरिक्ष के लिए जाना है.

326
00:24:10,460 --> 00:24:15,830
वर्तमान राशि इतनी दूर है, यहाँ, subproblem, हमारे subproblem सरणी की भूमिका को बदलता है.

327
00:24:15,830 --> 00:24:20,020
तो वर्तमान राशि, अब तक, पिछले subproblem जवाब है.

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
और हम भी हमारे subarray समस्या के लिए एक रेखीय समाधान है.

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
N integers, सकारात्मक, शून्य, या नकारात्मक की एक सरणी को देखते हुए,

348
00:25:38,350 --> 00:25:41,680
है कि n दिन पर एक शेयर की कीमत का प्रतिनिधित्व करते हैं,

349
00:25:41,680 --> 00:25:44,080
अधिकतम लाभ आप कर सकते हैं की गणना के लिए एक समारोह लिखने के लिए

350
00:25:44,080 --> 00:25:49,350
दिया है कि आप खरीदने के लिए और इन n दिनों के भीतर बिल्कुल 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
हाँ? (छात्र unintelligible) >> हां.

355
00:26:17,690 --> 00:26:21,470
>> तो आप सिर्फ हालांकि जाना होता है और शेयर की कीमतों को देखो

356
00:26:21,470 --> 00:26:30,550
समय में प्रत्येक बिंदु (unintelligible).

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
अधिकतम लाभ है कि हम दिन के सभी जोड़ों पर iterating के बाद कंप्यूट.

367
00:27:18,000 --> 00:27:20,330
यह हमारे अंतिम जवाब होगा.

368
00:27:20,330 --> 00:27:25,730
और हे (n ^ 2) है कि समाधान हो सकता है, क्योंकि वहाँ n दो जोड़े का चयन करें -

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
मैं आपको बताना है कि वहाँ एक n लॉग एन समाधान करने के लिए जा रहा हूँ.

372
00:27:37,420 --> 00:27:45,550
एल्गोरिथ्म क्या आप वर्तमान पता है कि n लॉग एन?

373
00:27:45,550 --> 00:27:50,730
यह एक चाल सवाल नहीं है.

374
00:27:50,730 --> 00:27:54,790
>> छंटाई संविलय. मर्ज प्रकार n लॉग एन है,

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
सबसे अच्छा लाभ आप कर सकते हैं, सिर्फ दो दिनों में 1 n के साथ.

380
00:28:16,480 --> 00:28:19,780
तो आप सबसे अच्छा खरीदने oompute / सही आधे पर जोड़ी बेचने चाहते हैं,

381
00:28:19,780 --> 00:28:23,930
पिछले दो दिनों में n.

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
हाँ? (जॉर्ज, unintelligible)

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
और सबसे अच्छी जोड़ी खरीदना / बेचना है कि spans दोनों हिस्सों की गणना करने के लिए सबसे अच्छा तरीका

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
Loops के लिए दो और बाएँ और दाएँ आधे पर अधिकतम मिनट क्रमशः गणना,.

409
00:30:50,720 --> 00:30:54,970
अब मैं लाभ है कि spans दोनों हिस्सों की गणना,

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
अगर हम एक समारोह टी (एन) को परिभाषित करने के लिए कदम की संख्या

419
00:31:41,340 --> 00:31:50,010
n दिनों के लिए,

420
00:31:50,010 --> 00:31:54,350
हमारे दो पुनरावर्ती कॉल

421
00:31:54,350 --> 00:32:00,460
कर रहे हैं हर टी (/ 2 n) खर्च करने जा रहा है,

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
जो मैं n / 2 समय, प्लस सही आधा की अधिकतम में कर सकते हैं.

425
00:32:17,050 --> 00:32:20,820
तो यह सिर्फ n है.

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
और हम सभी जानते हैं कि मर्ज तरह n लॉग n समय है.

430
00:32:39,170 --> 00:32:46,880
इसलिए, हमारे एल्गोरिथ्म भी लॉग n समय n है.

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
T (n) कदम की संख्या अधिकतम लाभ की गणना करने के लिए है

434
00:32:59,170 --> 00:33:02,750
n दिनों के पाठ्यक्रम पर.

435
00:33:02,750 --> 00:33:06,010
जिस तरह से हम अपने पुनरावर्ती कॉल विभाजित

436
00:33:06,010 --> 00:33:11,980
पहले n / 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
तो n / 2 + n / 2 n है.

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
इसलिए, हमारे घसीटना एल्गोरिथ्म भी n n लॉग.

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
चूंकि हम recursion का उपयोग कर रहे हैं,

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
लॉग एन ढेर फ्रेम के आदेश पर है.

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
अंतरिक्ष की अधिकतम राशि हम कभी इस्तेमाल हे अंतरिक्ष (लॉग एन)

467
00:35:49,240 --> 00:36:03,040
जहां n दिनों की संख्या है.

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
हम अधिक से अधिक subarray समस्या में यह शेयर बाजार की समस्या में परिवर्तित कर सकते हैं.

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
(एमी, unintelligible)

475
00:36:47,680 --> 00:36:53,860
[यू] बिल्कुल सही.

476
00:36:53,860 --> 00:36:59,940
अधिकतम subarray समस्या तो है,

477
00:36:59,940 --> 00:37:10,610
हम एक राशि के लिए एक सतत subarray पर देख रहे हैं.

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
लेकिन निरंतर पर देखो - चलो subarray समस्या पर देखो.

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
हमारे अधिकतम subarray समस्या में हमारे स्टॉक की समस्या को कम करने के लिए महत्वपूर्ण

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
1 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
तो फिर हम अपने एक अधिकतम subarray के लिए एक नियमित प्रक्रिया कॉल

497
00:38:55,530 --> 00:39:01,500
एक डेल्टा सरणी में गुजर रहा है.

498
00:39:01,500 --> 00:39:06,440
और क्योंकि अधिक से अधिक subarray रैखिक समय है,

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 (n) काम प्लस हे (एन) काम है, अभी भी हे (एन) काम है.

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]