[Powered by Google Translate] [संगोष्ठी: तकनीकी साक्षात्कार] [केनी यू, हार्वर्ड विश्वविद्यालय] [यह CS50 है.] [CS50.TV] हाय सब, मैं केनी हूँ. मैं वर्तमान में एक जूनियर कंप्यूटर विज्ञान का अध्ययन कर रहा हूँ. मैं एक पूर्व सीएस में TF हूँ, और काश मैं यह था जब मैं एक underclassman था, और यही कारण है कि मैं इस संगोष्ठी दे रहा हूँ. तो मैं तुम्हें मजा उम्मीद है. इस संगोष्ठी में तकनीकी साक्षात्कार के बारे में है, और अपने सभी संसाधनों को इस लिंक पर पाया जा सकता है, यह सही यहाँ लिंक, संसाधनों के एक जोड़े. तो मैं समस्याओं की एक सूची बना दिया है, वास्तव में, काफी कुछ समस्याओं. इसके अलावा एक सामान्य संसाधन पृष्ठ जहाँ हम सुझाव प्राप्त कर सकते पर कैसे एक साक्षात्कार के लिए तैयार करने के लिए, आप एक वास्तविक साक्षात्कार के दौरान क्या करना चाहिए पर सुझाव, के रूप में के रूप में अच्छी तरह से कैसे दृष्टिकोण करने के लिए और भविष्य में संदर्भ के लिए समस्याओं और संसाधनों. यह सब ऑनलाइन. और बस इस संगोष्ठी, एक त्याग प्रस्तावना अपने साक्षात्कार की तैयारी इस तरह से नहीं होना चाहिए सीमित करने के लिए इस सूची में नहीं होना चाहिए. यह केवल एक गाइड के लिए होती है, और आप निश्चित रूप से सब कुछ मैं नमक की एक अनाज के साथ कहते हैं लेना चाहिए, लेकिन यह भी सब कुछ मैं करने के लिए आप अपने साक्षात्कार की तैयारी में मदद करने के लिए प्रयोग किया जाता का उपयोग करें. 

मैं गति अगले कुछ स्लाइड के माध्यम से जा रहा हूँ इसलिए हम वास्तविक मामले के अध्ययन के लिए मिल सकता है. एक सॉफ्टवेयर इंजीनियरिंग की स्थिति के लिए एक साक्षात्कार की संरचना, आमतौर पर यह 30 से 45 मिनट है, कई दौर, कंपनी पर निर्भर करता है. अक्सर आप एक सफेद बोर्ड पर कोडिंग हो जाएगा. तो इस तरह से है, लेकिन अक्सर एक छोटे पैमाने पर एक सफेद बोर्ड. यदि आप एक फोन साक्षात्कार कर रहे हैं, तो आप शायद का उपयोग किया जाएगा या तो collabedit या एक गूगल डॉक्टर तो वे आप कोडिंग रहते देख सकते हैं जब आप फोन पर साक्षात्कार किया जा रहा हो. एक साक्षात्कार ही आम तौर पर 2 या 3 समस्याओं अपने कंप्यूटर विज्ञान के ज्ञान का परीक्षण. और यह लगभग निश्चित रूप से कोडिंग शामिल होगी. प्रश्नों के प्रकार है कि आप देखेंगे आम तौर पर कर रहे हैं डेटा संरचनाओं और एल्गोरिदम. और समस्याओं के इन प्रकार के कर में, वे आप से पूछना पसंद करेंगे, जो समय और अंतरिक्ष जटिलता, बड़ा हे है? अक्सर वे भी उच्च स्तर के सवाल पूछना, हां, एक प्रणाली डिजाइन, आप कैसे अपने कोड रखना चाहते हैं? इंटरफेस, क्या कक्षाएं, मॉड्यूल क्या आप अपने सिस्टम में है क्या, और कैसे इन एक साथ बातचीत नहीं करते हैं? तो डाटा संरचनाओं और एल्गोरिदम के रूप में के रूप में अच्छी तरह से व्यवस्था है. 

इससे पहले कि हम हमारे मामले के अध्ययन में गोता लगाने के लिए कुछ सामान्य. मुझे लगता है कि सबसे महत्वपूर्ण नियम हमेशा से बाहर किया जाता है ज़ोर से सोच. साक्षात्कार के लिए अपने को दूर अपनी सोच की प्रक्रिया दिखाने का मौका माना जाता है. साक्षात्कार की बात है के लिए साक्षात्कारकर्ता गेज करने के लिए आपको लगता है कि कैसे और कैसे आप एक समस्या के माध्यम से जाना. सबसे बुरी बात आप कर सकते हैं पूरे साक्षात्कार के दौरान चुप है. वह सिर्फ अच्छा नहीं है. जब आप एक प्रश्न दिए जाते हैं, तो आप यह भी सुनिश्चित करें कि आप सवाल समझ बनाना चाहते हैं. तो सवाल फिर से वापस अपने खुद के शब्दों में और प्रयास के लिए काम करने के लिए पूरी तरह से कुछ सरल परीक्षण मामलों सुनिश्चित करें कि आप सवाल समझ बनाने. कुछ परीक्षण मामलों के माध्यम से कार्य करना भी आप कैसे इस समस्या को हल करने के लिए एक अंतर्ज्ञान दे देंगे. तुम भी कुछ पैटर्न की मदद करने के लिए आप समस्या को हल खोज सकते हैं. उनका बड़ा टिप को निराश नहीं मिलता है. निराश नहीं मिलता है. साक्षात्कार चुनौती दे रहे हैं, लेकिन सबसे बुरी बात आप कर सकते हैं, चुप जा रहा है के अलावा, जाहिरा तौर पर निराश हो. आप एक साक्षात्कारकर्ता कि छाप दे नहीं करना चाहती. एक बात है कि आप - तो, ​​कई लोगों को, जब वे एक साक्षात्कार में जाने, वे करने के लिए सबसे अच्छा समाधान 1 खोजने की कोशिश करने का प्रयास है, जब वास्तव में, वहां आमतौर पर एक चमक से स्पष्ट समाधान है. यह धीमी गति से किया जा सकता है, यह अक्षम हो सकता है, लेकिन हो सकता है आप सिर्फ यह राज्य चाहिए, बस इतना तुम एक से बेहतर काम करने के प्रारंभिक बिंदु है. इसके अलावा, बाहर समाधान की ओर इशारा करते हुए धीमी गति के मामले में, बड़ी हे समय जटिलता या अंतरिक्ष जटिलता, साक्षात्कारकर्ता को दिखाना है कि आप समझ जाएगा इन मुद्दों जब कोड लिखने. तो सरल एल्गोरिथ्म के साथ आने के लिए डर 1 मत हो और फिर वहाँ से बेहतर काम करते हैं. कोई प्रश्न इतनी दूर है? ठीक है. 

तो चलो हमारी पहली समस्या में गोता. N integers की एक सरणी को देखते हुए, एक समारोह में कहा कि सरणी shuffles लिखने जगह ऐसी है कि n integers के सभी permutations समान रूप से होने की संभावना है. " और लगता है आप एक यादृच्छिक पूर्णांक जनरेटर उपलब्ध है कि 0 से मैं एक रेंज में एक पूर्णांक उत्पन्न करता है, आधा रेंज. क्या हर कोई इस सवाल समझ में आया? मैं आप n integers की एक सरणी देते हैं, और मैं तुम्हें यह मिश्रण करने के लिए करना चाहते हैं. मेरे निर्देशिका में, मैं कुछ कार्यक्रमों को दिखाना है कि मैं क्या मतलब है लिखा था. मैं 20 तत्वों की एक सरणी फेरबदल करने के लिए जा रहा हूँ, -10 से नौ के लिए, और मैं आप इस तरह एक सूची का उत्पादन करने के लिए करना चाहते हैं. तो यह मेरे क्रमबद्ध इनपुट सरणी है, और मैं तुम्हें यह मिश्रण करने के लिए करना चाहते हैं. हम इसे फिर से करना होगा. क्या हर कोई प्रश्न समझ में आया? ठीक है. तो यह आप पर निर्भर है. कुछ विचारों को क्या कर रहे हैं? आप n ^ 2, n लॉग, n के रूप में यह कर सकते हैं? सुझाव के लिए खुला. ठीक है. तो एक विचार है, एमी ने सुझाव दिया है, 1 0 से 20 के लिए एक यादृच्छिक संख्या, यादृच्छिक पूर्णांक एक श्रेणी में गणना है. तो लगता है हमारे सरणी की लंबाई है 20. 20 तत्वों की हमारे चित्र में, यह हमारे इनपुट सरणी है. और अब, उसके सुझाव के लिए एक नई सरणी बनाने के लिए है, तो यह आउटपुट सरणी होगा. और मैं रैंड से लौट आए पर आधारित है - यदि ऐसा है तो मैं था, चलो कहते हैं, 17, पहले की स्थिति में 17 तत्व की प्रतिलिपि. अब हम नष्ट करने की जरूरत है - हम सभी तत्वों को यहाँ बदलाव की जरूरत इतना अधिक है कि हम अंत में एक अंतर है और बीच में कोई छेद है. और अब हम इस प्रक्रिया को दोहराने की है. अब हम 0 और 19 के बीच एक नई यादृच्छिक पूर्णांक उठाओ. हम एक नया मैं यहाँ है, और हम इस स्थिति में इस तत्व की नकल. तो फिर हम से अधिक आइटम बदलाव और हम इस प्रक्रिया को दोहराने जब तक हम अपनी पूरी नई सरणी है. इस एल्गोरिथ्म के चलाने के समय क्या है? ठीक है, चलो इस के प्रभाव पर विचार. हम हर तत्व जा रहे हैं. जब हम इस मैं निकालने के लिए, हम सभी तत्वों के बाद यह बाईं करने के लिए जा रहे हैं. और कहा कि एक हे लागत (एन) क्योंकि जो अगर हम 1 तत्व निकाल? तो प्रत्येक को हटाने के लिए, हम दूर - प्रत्येक को हटाने के एक हे (एन) आपरेशन incurs, और जब से हम removals n है, यह एक हे घसीटना (n ^ 2) की ओर जाता है. ठीक है. तो अच्छी शुरुआत है. अच्छी शुरुआत है. 

एक अन्य सुझाव नुथ फेरबदल के रूप में जाना जाता है कुछ का उपयोग करने के लिए है, या फेरबदल फिशर Yates. और यह वास्तव में एक रैखिक समय फेरबदल है. और विचार बहुत समान है. फिर, हम अपने इनपुट सरणी है, लेकिन हमारे इनपुट / आउटपुट के लिए दो arrays का उपयोग करने के बजाय, हम सरणी के पहले भाग का उपयोग हमारे shuffled भाग का ट्रैक रखने के लिए, और हम पर नज़र रखने के लिए, और फिर हम unshuffled हिस्से के लिए हमारे सरणी के बाकी छोड़. तो यहाँ मैं क्या मतलब है. हम साथ बंद शुरू - हम एक मैं चुन, 0 से 20 के लिए एक सरणी. हमारे वर्तमान सूचक पहले सूचकांक इशारा कर रहा है. हम कुछ मैं यहाँ का चयन और अब हम स्वैप. तो अगर यह 5 था और यह 4 था, जिसके परिणामस्वरूप सरणी यहाँ 5 और 4 यहाँ होगा. और अब हम एक मार्कर यहाँ ध्यान दें. बाईं करने के लिए सब कुछ shuffled है, और सही करने के लिए सब कुछ unshuffled है. और अब हम इस प्रक्रिया को दोहरा सकते हैं. हम अब 1 और 20 के बीच एक यादृच्छिक सूचकांक का चयन करें. तो हमारे नए लगता है कि मैं यहाँ है. अब हम हमारे वर्तमान नई स्थिति के साथ मैं यहाँ स्वैप. तो हम इस तरह से आगे और पीछे गमागमन. मुझे इसे और अधिक ठोस बनाने के लिए कोड लाने. हम मैं की हमारी पसंद के साथ शुरू करते हैं - हम शुरू के साथ मैं 0 के बराबर है, हम एक यादृच्छिक स्थान जम्मू लेने सरणी के unshuffled भाग में, मैं n-1. तो अगर मैं यहाँ हूँ, यहाँ और सरणी के बाकी के बीच एक यादृच्छिक सूचकांक चुनते हैं, और हम स्वैप. यह आपके सरणी फेरबदल करने के लिए आवश्यक सभी कोड है. कोई सवाल? 

खैर, एक सवाल की जरूरत है, यह सही है कि क्यों? क्यों हर क्रमचय समान रूप से होने की संभावना है? और मैं इस बात का सबूत के माध्यम से नहीं जाना होगा, लेकिन कंप्यूटर विज्ञान के क्षेत्र में कई समस्याओं प्रेरण के माध्यम से सिद्ध किया जा सकता है. आप में से कितने को शामिल करने के साथ परिचित हैं? ठीक है. कूल. तो आप सरल प्रेरण द्वारा इस एल्गोरिथ्म की शुद्धता साबित कर सकते हैं, जहां अपने प्रेरण परिकल्पना होगा, कि मान मेरे फेरबदल हर क्रमचय समान रूप से होने की संभावना देता है पहले मैं तत्वों. अब, मैं + 1 पर विचार करें. और जिस तरह से हम हमारी अनुक्रमणिका जम्मू स्वैप करने के लिए चुनते हैं, यह करने के लिए ले जाता है और फिर तुम बाहर विवरण काम, क्यों इस एल्गोरिथ्म रिटर्न के कम से कम एक पूर्ण प्रमाण समान रूप से होने की संभावना संभावना के साथ हर क्रमचय. 

सब ठीक है, अगले समस्या. तो "पूर्णांकों की सरणी, postive, शून्य, नकारात्मक दिया, लिखने के एक समारोह में कहा कि अधिकतम राशि की गणना इनपुट सरणी के किसी भी continueous subarray की. " यहाँ एक उदाहरण के मामले में जहां सभी नंबरों सकारात्मक हैं, तो वर्तमान में सबसे अच्छा विकल्प पूरे सरणी लेने के लिए है. 1, 2, 3, 4, 10 के बराबर है. , जब तुम वहाँ में कुछ नकारात्मक है इस मामले में हम सिर्फ पहली दो चाहते हैं क्योंकि -1 और / या -3 चयन हमारे राशि नीचे लाने जाएगा. कभी कभी हम सरणी के मध्य में शुरू हो सकता है. कभी कभी हम कुछ भी नहीं का चयन करना चाहते हैं, यह सबसे अच्छा है कुछ भी नहीं ले. और कभी कभी यह बेहतर है गिर लेने, क्योंकि के बाद यह बात सुपर बड़ा है. तो किसी भी विचारों? (छात्र unintelligible) >> हाँ. मान लीजिए मैं -1 से नहीं लेते हैं. तो या तो मैं 1,000 और 20,000 चुनते हैं, या मैं सिर्फ तीन अरब का चयन करें. खैर, सबसे अच्छा विकल्प सभी नंबरों को लेने के लिए है. यह -1, नकारात्मक होने के बावजूद, पूरी राशि बेहतर की तुलना में मैं -1 नहीं ले रहे थे. तो एक सुझाव है कि मैंने पहले उल्लेख के लिए स्पष्ट रूप से स्पष्ट राज्य और जानवर बल समाधान 1. इस समस्या में जानवर बल समाधान क्या है? हाँ? [जेन] खैर, मुझे लगता है कि जानवर बल समाधान करने के लिए सभी संभव संयोजनों (unintelligible) जोड़ना होगा. [यू] ठीक है. तो जेन विचार करने के लिए हर संभव ले रहा है - मैं paraphrasing हूँ - हर संभव निरंतर subarray ले रहा है, अपनी राशि की गणना करने के लिए, और फिर सभी संभव निरंतर subarrays के अधिकतम ले. क्या विशिष्ट अपने इनपुट सरणी में एक subarray को दिखाता है? की तरह, दो बातें मैं क्या जरूरत है? हाँ? (छात्र unintelligible) >> ठीक है. एक कम सूचकांक और एक ऊपरी बाध्य सूचकांक पर बाध्य विशिष्ट एक सतत subarray निर्धारित करता है. [स्त्री छात्र] हम का आकलन कर रहे हैं यह अद्वितीय संख्या की एक सरणी है? [यू] नहीं तो उसके सवाल है, हम कर रहे हैं हमारे सरणी संभालने - हमारे सरणी सभी अद्वितीय संख्या है, और इस सवाल का जवाब नहीं है. 

यदि हम अपने जानवर बल समाधान, तो इंडेक्स प्रारंभ / समाप्ति का उपयोग विशिष्ट हमारे निरंतर subarray निर्धारित करता है. तो अगर हम सभी संभव शुरू प्रविष्टियों के लिए पुनरावृति और अंत प्रविष्टियों के लिए> या = शुरू करने के लिए, करने के लिए और <n, आप राशि की गणना, और फिर हम अधिकतम राशि हम अब तक देखा है. यह स्पष्ट है? इस समाधान के बड़े हे क्या है? Timewise. ^ 2 काफी नहीं n. ध्यान दें कि हम 0 से n पुनरावृति इतना है कि एक पाश के लिए है. हम लगभग शुरुआत से अंत करने के लिए फिर से पुनरावृति पाश के लिए एक और. और अब, उसके भीतर, हम हर प्रविष्टि राशि है, इतना है कि पाश के लिए एक और है. तो हम तीन loops के लिए नेस्टेड n ^ 3 है. ठीक है. यह एक प्रारंभिक बिंदु के रूप में चला जाता है. हमारी समाधान नहीं n ^ 3 से भी बदतर है. क्या हर कोई जानवर बल समाधान समझ में आया? 

ठीक है. एक बेहतर समाधान एक गतिशील प्रोग्रामिंग नामक विचार का उपयोग कर रहा है. यदि आप CS124 लेते हैं, जो एल्गोरिदम और डाटा संरचनाओं है, आप इस तकनीक के साथ बहुत परिचित हो जाएगा. और विचार करने के लिए छोटी समस्याओं के लिए समाधान 1 का निर्माण करने की कोशिश है. प्रारंभ और अंत: मैं क्या मतलब यह है, हम वर्तमान में दो चीजों के बारे में चिंता करने की ज़रूरत है. और कि कष्टप्रद है. क्या होगा अगर हम उन मापदंडों के छुटकारा मिल सकता है? हम हमारे मूल समस्या को देखते हुए, एक विचार करने के लिए है एक रेंज में किसी भी subarray की अधिकतम राशि [ओ, n-1] में पाते हैं. और अब हम हमारे वर्तमान सूचकांक में मैं एक नया subproblem है, जहां हम जानते है, हम जानते हैं कि हम वहाँ निष्कर्ष निकालना चाहिए. हमारी subarray वर्तमान सूचकांक में समाप्त होना चाहिए. तो शेष समस्या है, जहां हम हमारे subarray शुरू कर देना चाहिए? क्या इसका मतलब है? ठीक है. तो मैं इस कोडित है, और हम इसका क्या मतलब है पर देखने के. Codirectory में, वहाँ एक subarray कार्यक्रम बुलाया है, और यह आइटम्स की संख्या लेता है, और यह मेरे shuffled सूची में अधिक से अधिक subarray राशि देता है. तो इस मामले में, हमारे अधिक से अधिक subarray 3 है. और कहा कि सिर्फ 2 और 1 का उपयोग करके लिया है. चलो इसे फिर से चलाने. यह भी 3. लेकिन इस समय ध्यान दें, कैसे हम 3 मिला. हम लगा - हम सिर्फ 3 ही ले क्योंकि यह नकारात्मक द्वारा दोनों पक्षों पर घिरा हुआ है, जो एक राशि <3 लाएगा. चलो 10 वस्तुओं पर चला. इस बार यह 7 है, हम अग्रणी 3 और 4 ले लो. इस बार यह 8 है, और हम 4 1, 3 और लेने के द्वारा प्राप्त करने के लिए. तो आप कैसे पर एक अंतर्ज्ञान दे हम इस तब्दील समस्या को हल कर सकते हैं, चलो इस subarray पर एक नज़र ले. हम इस इनपुट सरणी दिया रहे हैं, और हम जवाब पता 8 है. हम 1, 4, और 3 ले लो. लेकिन कैसे हम वास्तव में उस जवाब मिल गया है पर देखो. चलो अधिकतम subarray कि इन सूचकांकों में से प्रत्येक में समाप्त हो गया पर देखो. अधिकतम subarray है कि पहले की स्थिति में समाप्त करने के लिए है क्या है? शून्य [छात्र]. शून्य. >> बस -5 नहीं ले जाते. यहाँ यह 0 के रूप में अच्छी तरह से हो रहा है. हाँ? (छात्र दुर्बोध) [यू] ओह, माफ करना, यह एक -3 है. तो यह एक 2 है, यह एक -3 है. ठीक है. तो -4, कि स्थिति को समाप्त करने के लिए अधिक से अधिक subarray क्या है जहां पर -4 है? शून्य. एक? 1, 5, 8. अब, मैं स्थान है जहाँ पर -2 है पर समाप्त होना चाहिए. तो 6, 5, 7, और पिछले एक 4 है. यह जानते हुए कि ये मेरी प्रविष्टियां हैं बदल समस्या है जहाँ मैं इन सूचकांकों में से प्रत्येक में समाप्त होना चाहिए के लिए, तो मेरा अंतिम जवाब है, भर में एक झाड़ू ले, और अधिकतम संख्या ले. तो इस मामले में यह 8 है. इसका मतलब है कि अधिक से अधिक subarray इस सूचकांक में समाप्त होता है, और इसके पहले कहीं से शुरू कर दिया. क्या हर कोई इस तब्दील subarray समझ में आया? 

ठीक है. ठीक है, चलो इस के लिए पुनरावृत्ति आंकड़ा. चलो बस पहले कुछ प्रविष्टियों पर विचार. यहाँ तो यह 0, 0, 0, 1, 5, 8. और फिर वहाँ एक -2 यहाँ था, और कहा कि यह लाया 6 से नीचे. तो अगर मैं स्थिति में प्रवेश कहते हैं मैं (i) subproblem, मैं पिछले एक subproblem कैसे जवाब का उपयोग कर सकते हैं के लिए इस subproblem का जवाब? अगर मैं को देखो, चलो कहते हैं, इस प्रविष्टि. मैं देख कैसे 6 जवाब की गणना कर सकते हैं इस सरणी और इस सरणी में पिछले subproblems जवाब का एक संयोजन है? हाँ? आप रकम की सरणी ले [महिला छात्र] सही स्थिति में यह पहले, 8 इतना, और फिर आप वर्तमान subproblem जोड़ने के. [यू] तो उसे सुझाव के लिए इन दो नंबरों पर लग रहा है, यह संख्या और इस संख्या. तो यह 8 subproblem के लिए जवाब (1 i) को संदर्भित करता है. और मेरे इनपुट सरणी ए कॉल आदेश में खोजने के लिए एक अधिकतम subarray है कि मैं स्थिति पर समाप्त होता है, मैं दो विकल्प हैं: मैं या तो subarray जारी रख सकते हैं कि पिछले सूचकांक में समाप्त हो गया, या एक नई सरणी शुरू. अगर मैं subarray कि पिछले सूचकांक में शुरू जारी थे, तो मैं अधिकतम राशि प्राप्त कर सकते हैं पिछले subproblem का जवाब है साथ मौजूदा सरणी प्रविष्टि. लेकिन, मैं भी एक नया subarray शुरू की पसंद है, जो मामले में योग 0 है. 1, प्लस वर्तमान सरणी प्रविष्टि तो जवाब 0 के अधिकतम, subproblem मैं है. इस पुनरावृत्ति मतलब होता है? हमारे पुनरावृत्ति, subproblem मैं, के रूप में हम अभी पता चला है पिछले subproblem की अधिकतम प्लस मेरे वर्तमान सरणी प्रविष्टि के लिए बराबर है, जिसका मतलब है कि पिछले subarray जारी, या 0, मेरे वर्तमान सूचकांक में एक नया subarray शुरू. और एक बार हम समाधान की इस तालिका को बनाया गया है, तो हमारे अंतिम जवाब सिर्फ subproblem सरणी पार एक रैखिक झाडू और अधिकतम संख्या ले. यह मैं अभी क्या कहा की एक सटीक कार्यान्वयन है. तो हम एक नया subproblem सरणी, subproblems. पहली प्रविष्टि या तो 0 या 1 प्रविष्टि, उन दोनों के अधिकतम है. और subproblems के बाकी के लिए हम सही पुनरावृत्ति हम अभी पता चला है. अब हम हमारे subproblems सरणी के अधिकतम गणना और कि हमारी अंतिम जवाब है. 

तो कितना अंतरिक्ष हम इस एल्गोरिथ्म में प्रयोग कर रहे हैं? यदि आप केवल CS50 लिया है, तो आप अंतरिक्ष बहुत ज्यादा पर विचार विमर्श नहीं हो सकता है. खैर, एक बात नोट करने के लिए है कि मैं malloc आकार n के साथ यहाँ बुलाया. क्या है कि आप के लिए सुझाव है? इस एल्गोरिथ्म रैखिक अंतरिक्ष का उपयोग करता है. हम बेहतर कर सकते हैं? वहाँ कुछ भी है कि आप देखेंगे कि अंतिम जवाब की गणना करने के लिए अनावश्यक है? मुझे लगता है कि एक अच्छा सवाल है, क्या जानकारी है हम की जरूरत नहीं है के माध्यम से सभी तरह से समाप्त करने के लिए ले जाने के? अब, अगर हम इन दो पंक्तियों पर देखो, हम केवल पिछले subproblem के बारे में परवाह है, और हम केवल अधिकतम हम कभी अब तक देखा है के बारे में परवाह है. हमारे अंतिम जवाब की गणना करने के लिए, हम पूरे सरणी जरूरत नहीं है. हम केवल अंतिम संख्या, पिछले दो नंबर की जरूरत है. Subproblem सरणी, अधिकतम के लिए और पिछले संख्या के लिए अंतिम संख्या. तो, वास्तव में, हम इन loops फ्यूज के साथ कर सकते हैं और रैखिक अंतरिक्ष से लगातार अंतरिक्ष के लिए जाना है. वर्तमान राशि इतनी दूर है, यहाँ, subproblem, हमारे subproblem सरणी की भूमिका को बदलता है. तो वर्तमान राशि, अब तक, पिछले subproblem जवाब है. और उस राशि, अब तक हमारे अधिकतम की जगह लेता है. हम अधिकतम की गणना के रूप में हम साथ चलते हैं. और इसलिए हम रैखिक अंतरिक्ष से लगातार अंतरिक्ष के लिए जाना है, और हम भी हमारे subarray समस्या के लिए एक रेखीय समाधान है. 

सवालों के इन प्रकार आप एक साक्षात्कार के दौरान मिल जाएगा. समय जटिलता क्या है, अंतरिक्ष जटिलता क्या है? आप बेहतर कर सकते हैं? वहाँ चीज़ें है कि करने के लिए चारों ओर रखने के लिए अनावश्यक हैं? मैं इस किया विश्लेषण करती है कि आप अपने दम पर लेना चाहिए पर प्रकाश डाला के रूप में आप इन समस्याओं के माध्यम से काम कर रहे हैं. हमेशा अपने आप पूछ रहे हो, "मैं बेहतर कर सकते हैं?" वास्तव में, हम इस से बेहतर कर सकते हैं? एक चाल सवाल का क्रमबद्ध करें. आप कर सकते हैं, क्योंकि आप की जरूरत है नहीं कर सकते कम से कम इस समस्या के लिए इनपुट पढ़ा. तो तथ्य यह है कि आप की जरूरत कम से कम इस समस्या को इनपुट को पढ़ने इसका मतलब है कि आप रैखिक समय की तुलना में बेहतर नहीं कर सकता है, और आप लगातार अंतरिक्ष से बेहतर नहीं कर सकता. तो यह वास्तव में, इस समस्या का सबसे अच्छा समाधान है. प्रश्न? ठीक है. 

शेयर बाजार की समस्या: N integers, सकारात्मक, शून्य, या नकारात्मक की एक सरणी को देखते हुए, है कि n दिन पर एक शेयर की कीमत का प्रतिनिधित्व करते हैं, अधिकतम लाभ आप कर सकते हैं की गणना के लिए एक समारोह लिखने के लिए दिया है कि आप खरीदने के लिए और इन n दिनों के भीतर बिल्कुल 1 शेयर बेचते हैं. " मूलतः, हम करने के लिए कम खरीद, उच्च बेचते चाहते हैं. और हम सबसे अच्छा लाभ हम कर सकते हैं बाहर आंकड़ा करना चाहते हैं. मेरे टिप वापस जा रहे हैं, क्या तुरंत स्पष्ट, आसान जवाब है, लेकिन यह धीमी है? हाँ? (छात्र unintelligible) >> हां. >> तो आप सिर्फ हालांकि जाना होता है और शेयर की कीमतों को देखो समय में प्रत्येक बिंदु (unintelligible). [यू] ठीक है, तो उसका समाधान - कंप्यूटिंग के उसके सुझाव निम्नतम और उच्चतम कंप्यूटिंग जरूरी काम नहीं करता क्योंकि सबसे कम से पहले हो सकता है. तो जानवर बल पर इस समस्या का समाधान क्या है? दो चीजें हैं जो मैं करने के लिए विशिष्ट लाभ मैं बनाने के निर्धारित की जरूरत है क्या कर रहे हैं? सही है. जानवर बल समाधान है - ओह, तो, जॉर्ज सुझाव है कि हम केवल दो दिन की जरूरत है विशिष्ट उन दो दिनों के लाभ का निर्धारण करते हैं. इसलिए हम हर जोड़ी की गणना, खरीद / बिक्री की तरह, लाभ है, जो नकारात्मक या सकारात्मक या शून्य हो सकता है की गणना. अधिकतम लाभ है कि हम दिन के सभी जोड़ों पर iterating के बाद कंप्यूट. यह हमारे अंतिम जवाब होगा. और हे (n ^ 2) है कि समाधान हो सकता है, क्योंकि वहाँ n दो जोड़े का चयन करें - दिन है कि आप अंत दिनों के बीच चयन कर सकते हैं. ठीक है, तो मैं यहाँ जानवर बल समाधान पर जाना नहीं जा रहा हूँ. मैं आपको बताना है कि वहाँ एक n लॉग एन समाधान करने के लिए जा रहा हूँ. एल्गोरिथ्म क्या आप वर्तमान पता है कि n लॉग एन? यह एक चाल सवाल नहीं है. 

छंटाई संविलय. मर्ज प्रकार n लॉग एन है, और वास्तव में, इस समस्या के हल के लिए एक तरह से उपयोग करने के लिए है विचार का एक मर्ज तरह तरह कहा जाता है, सामान्य रूप में विभाजित है, और जीत. और विचार के रूप में इस प्रकार है. आप के लिए सबसे अच्छा खरीदने की गणना / बाईं छमाही में जोड़ी बेचने चाहते हैं. सबसे अच्छा लाभ आप कर सकते हैं, सिर्फ दो दिनों में 1 n के साथ. तो आप सबसे अच्छा खरीदने oompute / सही आधे पर जोड़ी बेचने चाहते हैं, पिछले दो दिनों में n. और अब सवाल यह है कि हम इन समाधान कैसे वापस एक साथ मर्ज? हाँ? (छात्र दुर्बोध) ठीक है. >> तो मुझे एक तस्वीर खींचना. हाँ? (जॉर्ज, unintelligible) वास्तव में. >> जॉर्ज समाधान बिल्कुल सही है. तो अपने सुझाव है, पहली बार सबसे अच्छी जोड़ी / खरीदने, बेचने की गणना और है कि बाईं छमाही में होता है, तो हम फोन है कि बाईं छोड़ दिया,. सबसे अच्छा खरीदने / जोड़ी है कि सही छमाही में होता बेचते हैं. लेकिन अगर हम केवल इन दो नंबरों की तुलना में, हम इस मामले को याद कर रहे हैं जहाँ हम यहाँ खरीदने के लिए और सही छमाही में कहीं से बेचते हैं. हम बाईं छमाही में खरीदते हैं, सही छमाही में बेचते हैं. और सबसे अच्छी जोड़ी खरीदना / बेचना है कि spans दोनों हिस्सों की गणना करने के लिए सबसे अच्छा तरीका न्यूनतम यहाँ की गणना और अधिकतम यहाँ की गणना और उनके अंतर रखना. दो मामलों में जहां / खरीदने, बेचने जोड़ी केवल यहाँ होता तो, केवल यहाँ, या दोनों हिस्सों पर इन तीन नंबर से परिभाषित किया गया है. हमारे एल्गोरिथ्म तो हमारे समाधान वापस एक साथ विलय, हम सबसे अच्छी जोड़ी / खरीदने, बेचने की गणना करना चाहते हैं जहां हम बाईं आधे पर खरीदने के लिए और सही आधा पर बेचते हैं. और सबसे अच्छा तरीका है कि पहली छमाही में सबसे कम कीमत की गणना है, सही छमाही में सबसे अधिक कीमत है, और उनके अंतर रखना. परिणामस्वरूप तीन लाभ, इन तीन नंबर, तीन की अधिकतम ले, और कहा कि सबसे अच्छा लाभ आप इन दिनों पहली और अंत में कर सकते हैं. यहाँ महत्वपूर्ण लाइनों लाल रंग में हैं. बाईं छमाही में जवाब की गणना करने के लिए यह एक पुनरावर्ती फोन है. यह सही आधा में जवाब की गणना के लिए एक पुनरावर्ती फोन है. Loops के लिए दो और बाएँ और दाएँ आधे पर अधिकतम मिनट क्रमशः गणना,. अब मैं लाभ है कि spans दोनों हिस्सों की गणना, और अंतिम जवाब इन तीनों का अधिकतम है. ठीक है. 

तो, यकीन है, हम एक एल्गोरिथ्म है, लेकिन बड़ा सवाल यह है, इस जटिलता के समय क्या है? और कारण है कि मैं मर्ज तरह का उल्लेख किया है कि इस फार्म का जवाब विभाजित दो में और फिर वापस हमारे समाधान एक साथ विलय बिल्कुल मर्ज तरह के फार्म है. तो मुझे अवधि के माध्यम से जाना. अगर हम एक समारोह टी (एन) को परिभाषित करने के लिए कदम की संख्या n दिनों के लिए, हमारे दो पुनरावर्ती कॉल कर रहे हैं हर टी (/ 2 n) खर्च करने जा रहा है, और वहाँ इन दो कॉल की है. अब मैं बाईं आधे के न्यूनतम की गणना करने की जरूरत है, जो मैं n / 2 समय, प्लस सही आधा की अधिकतम में कर सकते हैं. तो यह सिर्फ n है. और फिर कुछ लगातार काम प्लस. और इस पुनरावृत्ति समीकरण वास्तव में मर्ज प्रकार के लिए पुनरावृत्ति समीकरण है. और हम सभी जानते हैं कि मर्ज तरह n लॉग n समय है. इसलिए, हमारे एल्गोरिथ्म भी लॉग n समय n है. क्या इस यात्रा मतलब होता है? बस इस बात का एक संक्षिप्त पुनर्कथन: T (n) कदम की संख्या अधिकतम लाभ की गणना करने के लिए है n दिनों के पाठ्यक्रम पर. जिस तरह से हम अपने पुनरावर्ती कॉल विभाजित पहले n / 2 दिनों पर हमारे समाधान फोन करके है, इतना है कि एक फोन है, और फिर हम दूसरी छमाही पर फिर से फोन. तो यह है कि दो फोन है. और फिर हम एक न्यूनतम बाईं आधे पर मिल जाए, जो हम रैखिक समय में कर सकते हैं, अधिकतम सही आधा मिल जाए, जो हम रैखिक समय में कर सकते हैं. तो n / 2 + n / 2 n है. फिर हम कुछ लगातार काम जो अंकगणित की तरह कर रही है है. इस पुनरावृत्ति समीकरण बिल्कुल मर्ज प्रकार के लिए पुनरावृत्ति समीकरण है. इसलिए, हमारे घसीटना एल्गोरिथ्म भी n n लॉग. तो कितना अंतरिक्ष हम प्रयोग कर रहे हैं? चलो कोड के लिए वापस जाओ. 

एक अच्छा सवाल है, हम कितने ढेर फ्रेम है कभी किसी भी क्षण में है? चूंकि हम recursion का उपयोग कर रहे हैं, ढेर फ्रेम की संख्या हमारे अंतरिक्ष उपयोग निर्धारित करता है. चलो N = 8 विचार. हम 8 पर फेरबदल कहते हैं, है, जो पहले चार प्रविष्टियों पर फेरबदल कॉल जो पहले दो प्रविष्टियों पर फेरबदल कॉल जाएगा. इसलिए हमारे ढेर है - यह हमारे चुकी है. और फिर हम घसीटना फिर से फोन पर 1, और है कि हमारे आधार मामला क्या है, तो हम तुरंत वापस. क्या हम कभी यह कई ढेर फ्रेम की तुलना में अधिक है? नहीं, क्योंकि हर बार हम एक मंगलाचरण करना, मिश्रण करने के लिए एक पुनरावर्ती मंगलाचरण, हम आधे में हमारे आकार विभाजित करते हैं. ढेर फ्रेम की अधिकतम संख्या तो हम कभी भी किसी भी क्षण में है लॉग एन ढेर फ्रेम के आदेश पर है. प्रत्येक स्टैक फ्रेम लगातार स्थान है, और इसलिए अंतरिक्ष की कुल राशि, अंतरिक्ष की अधिकतम राशि हम कभी इस्तेमाल हे अंतरिक्ष (लॉग एन) जहां n दिनों की संख्या है. 

अब हमेशा खुद से पूछते हैं, "हम बेहतर कर सकते हैं?" और विशेष रूप में, हम एक समस्या है कि हम पहले से ही हल कर दिया है इस को कम कर सकते हैं? एक संकेत: हम इस से पहले केवल दो अन्य समस्याओं पर चर्चा की है, और यह करने के लिए फेरबदल होने वाला नहीं है. हम अधिक से अधिक subarray समस्या में यह शेयर बाजार की समस्या में परिवर्तित कर सकते हैं. हम यह कैसे कर सकते हैं? तुम में से एक? एमी? (एमी, unintelligible) [यू] बिल्कुल सही. अधिकतम subarray समस्या तो है, हम एक राशि के लिए एक सतत subarray पर देख रहे हैं. और शेयरों समस्या के लिए एमी सुझाव, परिवर्तन, या डेल्टा पर विचार करें. और इस का एक चित्र है - यह एक शेयर की कीमत है, लेकिन अगर हम एक लगातार दूसरे दिन के बीच का अंतर लिया - तो हम देखते हैं कि अधिक से अधिक लाभ अधिकतम मूल्य, हम कर सकता है अगर हम यहाँ खरीदने के लिए और यहाँ बेचने. लेकिन निरंतर पर देखो - चलो subarray समस्या पर देखो. तो यहाँ, हम कर सकते हैं - यहाँ से यहाँ के लिए जा रहा है, हम एक सकारात्मक बदलाव है, और फिर यहाँ से यहाँ के लिए जा रहा है हम एक नकारात्मक बदलाव है. लेकिन फिर, यहाँ से यहाँ के लिए जा रहा है हम एक बड़ा सकारात्मक बदलाव है. और इन परिवर्तनों कि हम राशि के लिए हमारे अंतिम लाभ प्राप्त करना चाहते हैं. फिर हम और अधिक नकारात्मक परिवर्तन यहाँ है. हमारे अधिकतम subarray समस्या में हमारे स्टॉक की समस्या को कम करने के लिए महत्वपूर्ण दिनों के बीच डेल्टा पर विचार करने के लिए है. तो हम एक नया डेल्टा बुलाया सरणी बनाने, 1 0 हो प्रविष्टि प्रारंभिकीकरण और फिर प्रत्येक डेल्टा के लिए (i), कि अंतर हो अपने इनपुट सरणी (i), और सरणी (मैं - 1). तो फिर हम अपने एक अधिकतम subarray के लिए एक नियमित प्रक्रिया कॉल एक डेल्टा सरणी में गुजर रहा है. और क्योंकि अधिक से अधिक subarray रैखिक समय है, और इस कमी, इस डेल्टा सरणी बनाने की इस प्रक्रिया, यह भी रैखिक समय है, तो शेयरों के लिए अंतिम समाधान O (n) काम प्लस हे (एन) काम है, अभी भी हे (एन) काम है. तो हम एक रेखीय समय हमारी समस्या का समाधान है. क्या हर कोई इस परिवर्तन को समझने? 

सामान्य में, एक अच्छा विचार है कि आप हमेशा होना चाहिए एक नई समस्या यह है कि आप देख रहे हैं कम करने की कोशिश है. अगर यह एक पुरानी समस्या के लिए परिचित लग रहा है, यह एक पुरानी समस्या को कम करने की कोशिश करें. और अगर आप सभी उपकरण का उपयोग कर सकते हैं कि आप पुरानी समस्या पर इस्तेमाल किया है नई समस्या को हल करने के लिए. तो को लपेटो, तकनीकी साक्षात्कार को चुनौती दे रहे हैं. इन समस्याओं को शायद कुछ अधिक कठिन समस्याओं है कि आप एक साक्षात्कार में देख सकते हैं, यदि ऐसा है तो आप सभी समस्याओं को समझ में नहीं आता कि मैं सिर्फ कवर, यह ठीक है. ये अधिक चुनौतीपूर्ण समस्याओं में से कुछ हैं. अभ्यास, अभ्यास, अभ्यास. मैं थिसिस में समस्याओं का एक बहुत कुछ दिया है, तो निश्चित रूप से उन बाहर की जाँच करें. और अपने साक्षात्कार पर अच्छी किस्मत. अपने सभी संसाधनों को इस लिंक पर पोस्ट कर रहे हैं, और मेरे वरिष्ठ दोस्तों के एक नकली तकनीकी साक्षात्कार करने के पेशकश की है, इसलिए यदि आप रुचि रखते हैं, उस ईमेल पते पर ईमेल याओ विल. यदि आप कुछ सवाल है, तो आप मुझसे पूछ सकते हैं. क्या तुम लोगों को विशिष्ट तकनीकी साक्षात्कार से संबंधित प्रश्न हैं या किसी भी समस्याओं को हम अब तक देखा है? ठीक है. खैर, अपने साक्षात्कार पर अच्छी किस्मत. [CS50.TV]