[Powered by Google Translate] [ندوة: مقابلات الفني] [كيني يو، جامعة هارفارد] [هذا CS50.] [CS50.TV] مرحبا بالجميع، أنا كيني. وأنا حاليا دراسة علوم الكمبيوتر المبتدئين. أنا CS السابق TF، وكنت أتمنى لو كان هذا عندما كنت في اللامتخرج، وهذا هو السبب أنا أقدم هذه الندوة. لذلك آمل أن تستمتع به. هذه الندوة حوالي المقابلات الفنية، ويمكن العثور على كل ما عندي من الموارد في هذا الرابط، هذا الرابط هنا، وزوجين من الموارد. لذلك أنا قدمت قائمة من المشاكل، في الواقع، تماما عدد قليل من المشاكل. أيضا صفحة الموارد العامة حيث يمكننا العثور على نصائح حول كيفية الاستعداد للمقابلة، النصائح حول ما يجب عليك القيام به خلال مقابلة الفعلية، وكذلك كيفية التعامل مع المشاكل والموارد للرجوع إليها مستقبلا. كل شيء على الانترنت. وأستهل فقط لهذه الندوة، إخلاء، أود هذا لا - إعداد مقابلة الخاص لا ينبغي أن تقتصر على هذه القائمة. ويهدف هذا فقط لتكون دليلا، ويجب أن تأخذ بالتأكيد كل شيء أقول مع حبة الملح، ولكن أيضا استخدام كل ما كنت لمساعدتك في إعداد المقابلة. 

انا ذاهب الى السرعة من خلال الشرائح القليلة المقبلة حتى نتمكن من الوصول إلى دراسات الحالة الفعلية. هيكل حديث لبرنامج postion الهندسة، فمن عادة 30 إلى 45 دقيقة، جولات متعددة، اعتمادا على الشركة. في كثير من الأحيان عليك أن تكون على لوحة الترميز الأبيض. حتى لوحة بيضاء مثل هذا، ولكن في كثير من الأحيان على نطاق أصغر. إذا كنت تواجه مقابلة عبر الهاتف، سوف ربما كنت تستخدم إما collabedit أو محرر مستندات Google حتى يتمكنوا من أراك يعيش الترميز في حين أنهم يتعرضون مقابلتك عبر الهاتف. مقابلة نفسه هو عادة 2 أو 3 مشاكل اختبار معرفتك علوم الكمبيوتر. وسوف تشمل بالتأكيد تقريبا الترميز. أنواع الأسئلة التي سترى عادة ما تكون هياكل البيانات والخوارزميات. والقيام في هذه الأنواع من المشاكل، وسوف يطلب منك، مثل، ما هو الوقت وتعقيد الفضاء، يا كبير؟ كثيرا ما نتساءل لأسئلة ذات مستوى أعلى، لذلك، وتصميم النظام، كيف يمكنك وضع التعليمات البرمجية؟ ما اجهات، ما الطبقات، ما لديكم وحدات في النظام الخاص بك، وكيف يمكن لهذه تتفاعل معا؟ حتى هياكل البيانات والخوارزميات وكذلك نظم التصميم. 

بعض النصائح العامة قبل أن تغوص في دراسات لحالتنا. أعتقد أن أهم قاعدة يتم دائما يكون التفكير بصوت عال. من المفترض أن تكون المقابلة هي فرصتك لاظهار عملية التفكير الخاصة بك. وجهة المقابلة للمقابلة لقياس كيف تفكر وكيف تذهب من خلال مشكلة. أسوأ شيء يمكنك القيام به هو التزام الصمت طوال المقابلة كلها. هذا مجرد خيرا لا. عندما يتم إعطاء سؤال، وتريد أيضا للتأكد من أنك تفهم هذه المسألة. لذا فإن السؤال يتكرر مرة أخرى في الكلمات الخاصة بك ومحاولة للعمل عدد قليل من الحالات شامل اختبار بسيط للتأكد من أنك تفهم هذه المسألة. وسوف تعمل من خلال بعض حالات الاختبار ايضا ان اقدم لكم الحدس حول كيفية حل هذه المشكلة. قد تكتشف حتى أنماط قليلة لمساعدتك في حل هذه المشكلة. تلميح بهم كبيرة هو عدم الحصول على بالاحباط. لا بالإحباط. مقابلات تشكل تحديا، ولكن أسوأ شيء يمكنك القيام به، بالإضافة إلى كونه صامت، هو أن تشعر بالاحباط. كنت لا تريد أن تعطي هذا الانطباع إلى المقابلة. الشيء الوحيد الذي كنت - لذلك، كثير من الناس، عندما يذهبون إلى مقابلة، أنها محاولة لمحاولة العثور على أفضل الحل الأول، عندما حقا، وهناك عادة حل واضح وضوح الشمس. قد تكون بطيئة، قد يكون غير فعال، ولكن يجب القول فقط، فقط حتى يكون لديك نقطة انطلاق يمكن من خلالها العمل على نحو أفضل. أيضا، لافتا إلى أن الحل يكمن بطيئة، من حيث كبيرة تعقيد الوقت O أو تعقيد الفضاء، وسوف تثبت للمقابلة أن تفهم هذه القضايا عند كتابة التعليمات البرمجية. لذلك لا تخافوا من أجل التوصل إلى أبسط خوارزمية 1 وثم العمل على نحو أفضل من هناك. أي أسئلة حتى الآن؟ حسنا. 

لذلك دعونا الغوص في مشكلتنا الأولى. "ونظرا لمجموعة من الأعداد الصحيحة N، اكتب الدالة التي المراوغات الصفيف في مثل هذا المكان أن كل التباديل من أعداد صحيحة لا يحتمل على حد سواء. " وتحمل المتاحة لديك مولد عشوائي صحيح الذي يولد عددا صحيحا في نطاق من 0 إلى ط، مجموعة نصف. لا يفهم الجميع هذا السؤال؟ أنا أعطيك مجموعة من الأعداد الصحيحة ن، وأنا أريد منك أن خلط ذلك. في الدليل الخاص بي، كتبت عدد قليل من البرامج لإظهار ما أعنيه. انا ذاهب الى خلط مجموعة من 20 عنصرا، من -10 إلى +9، وأنا أريد منك أن إخراج مثل هذه القائمة. لذلك هذا هو بلدي مجموعة المدخلات فرزها، وأنا أريد منك أن خلط ذلك. سوف نفعل ذلك مرة أخرى. لا الجميع فهم السؤال؟ حسنا. لذلك متروك لكم. ما هي بعض الأفكار؟ يمكنك أن تفعل ذلك كما ن ^ 2، N سجل ن، ن؟ فتح لاقتراحات. حسنا. حتى فكرة واحدة، واقترح من قبل إيمي، هو أول حساب رقم عشوائي، عشوائية صحيح، في نطاق من 0 إلى 20. نفترض ذلك مجموعة لديها بطول 20. في الرسم التخطيطي لدينا من 20 عنصرا، هذا هو مجموعة لدينا المدخلات. والآن، اقتراحها هو خلق مجموعة جديدة، لذلك سوف تكون هذه هي صفيف الإخراج. واستنادا إلى عدت من قبل راند - حتى إذا كنت، دعنا نقول، 17، نسخ العنصر 17 في المركز الأول. الآن نحن بحاجة إلى حذف - نحن بحاجة إلى تحويل كل العناصر هنا أكثر من ذلك أن لدينا فجوة في نهاية الثقوب وليس في وسطها. والآن نكرر هذه العملية. نحن الآن اختيار عدد صحيح عشوائي بين 0 جديدة و 19. لدينا ط جديدا هنا، ونحن نسخ هذا العنصر في هذا الموقف. ثم ننتقل البنود مرارا ونكرر العملية حتى نحصل على مجموعة جديدة كاملة لدينا. ما هو وقت التشغيل من هذه الخوارزمية؟ حسنا، دعونا النظر في أثر ذلك. نحن تحويل كل عنصر. عندما نلغي هذا أنا، ونحن تحويل جميع العناصر بعد إلى اليسار. والتي هي (ن) O التكلفة لأن ما إذا كنا إزالة العنصر الأول؟ ذلك لإزالة كل، فإننا إزالة - كل إزالة يتحمل أحد (ن) O العملية، وبما أننا قد ن عمليات الإزالة، وهذا يؤدي إلى خلط ورق اللعب (ن ^ 2) O. حسنا. بداية جيدة لذلك. بداية طيبة. 

اقتراح آخر هو استخدام ما يعرف باسم خلط نث، خلط ورق اللعب أو فيشر ييتس. وانها في الواقع خلط ورق اللعب مرة الخطية. والفكرة هي مشابهة جدا. مرة أخرى، لدينا مجموعة لدينا المدخلات، ولكن بدلا من استخدام صفيفين لمساهمتنا / الإخراج، نستخدم الجزء الأول من الصفيف لتتبع جزء دينا تعديلا، ونحن تتبع، ومن ثم نترك بقية مجموعتنا للجزء unshuffled. حتى هنا هو ما أعنيه. نحن تبدأ مع - نختار من أنا، مجموعة 0 حتي 20. مؤشر حالتنا الراهنة يشير إلى الفهرس الأول. نختار هنا بعض ط والآن نحن مبادلة. إذا كان الأمر كذلك وكان هذا كان هذا 5 و 4، والصفيف الناتجة دينا 5 و 4 هنا هنا. والآن نلاحظ علامة هنا. وتعديلا كل شيء إلى اليسار، وunshuffled كل شيء إلى اليمين. والآن يمكننا تكرار هذه العملية. نختار مؤشر عشوائي بين 1 و 20 الآن. لنفترض لدينا حتى أنا جديدة هنا. الآن نحن مبادلة هذا أنا مع موقفنا الحالي الجديد هنا. لذلك علينا القيام مبادلة ذهابا وإيابا من هذا القبيل. اسمحوا لي أن طرح قانون لجعله أكثر واقعية. نبدأ مع خيارنا الأول - نبدأ مع ط يساوي 0، ونحن ي اختيار موقع عشوائي في الجزء unshuffled من الصفيف، وأنا إلى n-1. حتى إذا أنا هنا، واختيار عشوائي بين مؤشر هنا وبقية الصفيف، ونحن مبادلة. هذا هو كل التعليمات البرمجية الضرورية لخلط مجموعة الخاص بك. أي أسئلة؟ 

حسنا، السؤال هو احد في حاجة، لماذا هذا صحيح؟ لماذا كل التقليب المحتمل على قدم المساواة؟ وأنا لن تذهب من خلال دليل على ذلك، ولكن يمكن ثبت العديد من المشاكل في علوم الكمبيوتر من خلال تحريض. كم كنت معتادا على تحريض؟ حسنا. بارد. حتى تتمكن من إثبات صحة هذه الخوارزمية بواسطة الحث بسيطة، حيث لديك الفرضية تحريض سيكون، افترض أن خلط ورق اللعب بلدي بإرجاع كل التقليب من المحتمل أيضا حتى العناصر ط الأولى. الآن، والنظر في ط + 1. وبالمناسبة لدينا نختار ي مؤشر لمبادلة، هذا يؤدي إلى - ثم العمل على التفاصيل، على الأقل دليلا كاملا لماذا هذه الخوارزمية إرجاع كل التقليب مع احتمال المحتمل على قدم المساواة. 

حسنا، المشكلة القادمة. لذلك "نظرا لمجموعة من الأعداد الصحيحة، صالحهم بشكل ايجابي، صفر، سلبية، كتابة دالة تقوم بحساب مجموع الحد الأقصى أي subarray continueous للصفيف الإدخال. " مثال هنا هو، في الحالة التي يكون فيها كل الأرقام إيجابية، ثم حاليا أفضل خيار هو اتخاذ مجموعة كاملة. 1، 2، 3، 4، يساوي 10. عندما يكون لديك بعض السلبيات في هناك، في هذه الحالة نريد فقط الأولين لأن اختيار -1 و / أو تقديم مبلغ -3 لدينا باستمرار. في بعض الأحيان قد يكون لدينا أن تبدأ في منتصف الصفيف. في بعض الأحيان نريد أن تختار أي شيء على الإطلاق، بل من الأفضل أن لا تأخذ أي شيء. وأحيانا يكون من الأفضل أن تأخذ سقوط، لأن الشيء بعد أن السوبر كبيرة. لذلك أي أفكار؟ (الطالب، غير مفهومة) >> نعم. لنفترض أنني لا تأخذ -1. ثم إما أن أختار 1،000 و 20،000، أو اخترت فقط 3 مليارات دولار. كذلك، فإن أفضل خيار هو أن تأخذ جميع الأرقام. هذا -1، على الرغم من كونها سلبية، مجموع كله كان أفضل من أن لا تأخذ -1. لذلك كان واحدا من نصائح ذكرت سابقا أن أذكر ما هو واضح بشكل واضح والحل القوة الغاشمة الأول. ما هو الحل القوة الغاشمة في هذه المشكلة؟ نعم؟ [جين] حسنا، أعتقد أن الحل القوة الغاشمة سيكون لتضيف ما يصل جميع التوليفات الممكنة (غير مفهومة). [يو] حسنا. حتى فكرة جين هو اتخاذ كل ما يمكن - أنا إعادة الصياغة - هو اتخاذ كل subarray ممكن المستمر، حساب مبلغ الخمسين، ثم أخذ الحد الأقصى لجميع subarrays المستمر ممكن. ما يعرف بشكل فريد subarray في مجموعة المدخلات الخاصة بي؟ مثل، ما شيئين التي أحتاجها؟ نعم؟ (الطالب، غير مفهومة) الحق >>. A الأدنى على المؤشر ومؤشر الحد الأعلى يحدد بشكل فريد subarray المستمر. [طالب انثى] هل نحن تقدير انها مجموعة من الأرقام الفريدة؟ [يو] رقم حتى يتم سؤالها، هل نحن لدينا مجموعة افتراض - هو مجموعة لدينا كل الأرقام فريدة من نوعها، والجواب هو لا. 

إذا كان لنا أن استخدام القوة الغاشمة لدينا الحل، ثم مؤشرات بداية / نهاية يحدد بشكل فريد لدينا subarray المستمر. إذا كان الأمر كذلك فإننا تكرار لجميع مداخل بداية ممكنة، ونهاية لجميع مداخل> أو = لبدء، ون <، أنت حساب مجموع، ثم نأخذ مجموع الحد الأقصى رأيناه حتى الآن. هل هذا واضح؟ ما هو O كبير من هذا الحل؟ Timewise. لا ن جدا ^ 2. ملاحظة أننا تكرار من 0 إلى N، بحيث واحد للحلقة. ونحن مرة أخرى من تكرار بداية تقريبا إلى نهاية، وآخر للحلقة. والآن، في غضون ذلك، لدينا لتلخيص كل دخول، ذلك أن آخر حلقة لل. لذلك لدينا ثلاث حلقات متداخلة ل، N ^ 3. حسنا. هذا ينطبق كنقطة انطلاق. لدينا الحل هو أسوأ لا يتجاوز ن ^ 3. لا يفهم الجميع الحل القوة الغاشمة؟ 

حسنا. أفضل حل هو استخدام فكرة دعا البرمجة الديناميكية. إذا كنت تأخذ CS124، وهو الخوارزميات وهياكل البيانات، سوف تصبح مألوفة جدا مع هذه التقنية. والفكرة هي، في محاولة لبناء حلول لمشاكل أصغر الأولى. ما أعنيه بهذا هو، ليس لدينا حاليا ما يدعو للقلق أمرين: بداية ونهاية. وهذا مزعج. ماذا لو أننا يمكن أن تخلص من واحدة من تلك المعلمات؟ فكرة واحدة هي - we're نظرا مشكلتنا الأصلية، العثور على مبلغ الحد الأقصى من أي subarray في مجموعة [O، N-1]. والآن لدينا subproblem جديدة، حيث نعلم، في فهرسنا الحالي ط، نحن نعلم أننا يجب أن تختتم هناك. يجب subarray لدينا يغلق عند مستوى المؤشر الحالي. وبالتالي فإن المشكلة المتبقية هي، حيث يجب أن نبدأ subarray لدينا؟ هل هذا معقول؟ حسنا. حتى لقد ترميز I هذا الأمر، ودعونا نلقي نظرة على ما يعنيه هذا. في codirectory، وهناك برنامج يسمى subarray، ويستغرق عدد من العناصر، وتقوم بإرجاع المبلغ subarray القصوى في قائمتي تعديلا. حتى في هذه الحالة، لدينا subarray القصوى هي 3. وانها اتخذت هذا فقط باستخدام 2 و 1. دعونا تشغيله مرة أخرى. كما انها 3. ولكن هذه المرة، لاحظ كيف وصلنا إلى 3. اتخذنا - نحن نأخذ فقط ال 3 نفسها لأنه تحيط به السلبيات من الجانبين، والتي سوف تجلب مبلغا <3. دعونا تعمل على 10 تعليقات. هذه المرة 7، ونحن نأخذ ال 3 و 4 الرائدة. هذه المرة 8، والتي نحصل عليها من خلال اتخاذ 1 و 4 و 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. إذا كان الأمر كذلك أسميه الدخول في موقف ط subproblem (ط)، كيف يمكنني استخدام ردا على subproblem السابقة للإجابة على هذا subproblem؟ إذا كنت تبحث في، دعنا نقول، هذا الإدخال. كيف يمكنني حساب الجواب 6 من يبحث في مزيج من هذه المجموعة والمشاكل الثانوية إجابات لمجموعة السابقة في هذا؟ نعم؟ [طالب انثى] أن تأخذ مجموعة من المبالغ في المكان المناسب قبل أن، وبالتالي فإن 8، ثم قمت بإضافة subproblem الحالي. [يو] لذا اقتراحها هو أن ننظر إلى هذه الأرقام اثنين، وهذا العدد عدد هذه. ولذلك فإن هذا يشير إلى 8 الجواب لsubproblem (ط - 1). ودعونا ندعو A. بلدي مجموعة المدخلات من أجل العثور على subarray القصوى التي تنتهي في موقف ط، لدي خيارين: أستطيع أن تستمر إما subarray انتهت أنه في المؤشر السابق، أو اضافة مجموعة جديدة. إذا كان لي أن مواصلة subarray التي بدأت في المؤشر السابق، ثم مجموع الحد الأقصى أستطيع تحقيقه هو الجواب على subproblem السابقة بالإضافة إلى دخول مجموعة الحالية. ولكن، لا بد لي أيضا اختيار بدء subarray جديدة، في هذه الحالة مجموع 0. وبالتالي فإن الجواب هو أقصى 0، subproblem ط - 1، بالإضافة إلى دخول مجموعة الحالية. هل هذا تكرار معنى؟ تكرار لدينا، كما اكتشفنا للتو، هو أنا subproblem يساوي الحد الأقصى للsubproblem السابقة بالإضافة إلى مشاركتي مجموعة الحالية، وهو ما يعني مواصلة subarray السابقة، أو 0، بدء subarray جديدة في مؤشر بلدي الحالي. ومرة أقمنا هذا الجدول من الحلول، ثم ردنا النهائي، يفعل الخطية حملة عبر مجموعة subproblem واتخاذ أكبر عدد ممكن. هذا هو بالضبط ما تنفيذ قلت للتو. لذلك نحن إنشاء مجموعة جديدة subproblem، المشاكل الثانوية. الإدخال الأول هو إما 0 أو الإدخال الأول، والحد الأقصى من هذين. وبالنسبة لبقية المشاكل الثانوية لل نستخدم تكرار الدقيق اكتشفنا للتو. نحن الآن حساب الحد الأقصى لمجموعة المشاكل الثانوية لدينا، وهذا هو ردنا النهائي. 

حتى مقدار المساحة هل نستخدم في هذه الخوارزمية؟ إذا كنت قد اتخذت فقط CS50، فإنك قد لا يكون ناقش مساحة كبيرة جدا. حسنا، شيء واحد هو أن نلاحظ أن دعوت malloc هنا مع n الحجم. ماذا توحي لك؟ هذه الخوارزمية يستخدم الفضاء الخطي. يمكننا أن نفعل أفضل؟ هل هناك أي شيء لاحظت أن لا لزوم لها لحساب الجواب النهائي؟ أعتقد أفضل السؤال هو، ما هي المعلومات هل نحن لا حاجة إلى حمل على طول الطريق حتى النهاية؟ الآن، إذا نظرنا إلى هذين الخطين، نحن نهتم فقط عن subproblem السابقة، ونحن نهتم فقط عن الحد الأقصى رأيناه حتى الآن من أي وقت مضى. لحساب ردنا النهائي، ونحن لسنا بحاجة إلى مجموعة كاملة. نحن فقط في حاجة إلى عدد آخر، آخر رقمين. مشاركة رقم للمجموعة subproblem، وآخر رقم لأقصى حد. لذلك، في الواقع، يمكننا أن تلتحم هذه الحلقات معا وتذهب من الفضاء إلى الفضاء الخطي المستمر. مجموع الحالي حتى الآن، وهنا، يحل محل دور subproblem، لدينا مجموعة subproblem. مجموع الحالي بذلك، حتى الآن، هو الإجابة على subproblem السابقة. وهذا المبلغ حتى الآن، ويأخذ مكان ماكس لدينا. نحن حساب الحد الأقصى ونحن نمضي على طول. وهكذا نذهب من الفضاء إلى الفضاء الخطي المستمر، ونحن لدينا أيضا حلا لمشكلة الخطية subarray لدينا. 

هذه الأنواع من الأسئلة سوف تحصل خلال مقابلة. ما هو مدى تعقيد الوقت؛ ما هو تعقيد الفضاء؟ يمكنك أن تفعل أفضل؟ هناك أشياء غير ضرورية للحفاظ على حوالي؟ فعلت ذلك لتسليط الضوء على التحليلات التي يجب أن تأخذ بنفسك كما كنت تعمل من خلال هذه المشاكل. دائما أن تسأل نفسك، "هل يمكنني القيام أفضل؟" في الواقع، يمكن أن نفعل أفضل من هذا؟ نوع من السؤال خدعة. لا يمكنك، لأنك بحاجة إلى على الأقل قراءة المدخلات لهذه المشكلة. ذلك أن تحتاج إلى ما لا يقل عن قراءة المدخلات لهذه المشكلة يعني أنك لا تستطيع أن تفعل أفضل من الوقت الخطية، ويمكنك أن تفعل أفضل من الفضاء المستمر. لذلك هذا هو، في الواقع، فإن أفضل حل لهذه المشكلة. الأسئلة؟ حسنا. 

سوق الأسهم المشكلة: "ونظرا لمجموعة من الأعداد الصحيحة N، إيجابية، الصفر، أو سلبية، التي تمثل سعر السهم خلال الأيام N، كتابة دالة لحساب الربح الحد الأقصى الذي يمكن أن تجعل بالنظر إلى أن تقوم بشراء وبيع الأوراق المالية داخل بالضبط 1 ن هذه الأيام. " أساسا، ونحن نريد لشراء منخفضة، بيع عالية. ونحن نريد أن معرفة أفضل ربح يمكننا أن نجعل. العودة الى بلدي تلميح، ما هو واضح على الفور، أبسط الجواب، لكنه بطيء؟ نعم؟ (الطالب، غير مفهومة) >> نعم. لذا >> تذهب فقط على الرغم من وإلقاء نظرة على أسعار الأسهم في كل نقطة في الوقت المناسب، (غير مفهومة). [يو] حسنا، لذلك لها حل - اقتراحها من الحوسبة أقل وأعلى حساب لا يعمل بالضرورة لأنه قد تحدث قبل أعلى أدنى. فما هو الحل القوة الغاشمة لهذه المشكلة؟ ما هي شيئين أنني بحاجة لتحديد فريد الأرباح التي يمكنني تحقيقها؟ الحق. الحل هو القوة الغاشمة - يا، لذلك، هو اقتراح جورج نحتاج يومين فقط لتحديد فريد الربح من هذين اليومين. لذلك نحن حساب كل زوج، مثل شراء / بيع، حساب الربح، والتي يمكن أن تكون سلبية أو إيجابية أو صفر. حساب الربح الأقصى التي نتخذها بعد بالتكرار على جميع أزواج من الأيام. وسيكون ذلك ردنا النهائي. وسوف يكون هذا الحل O (N ^ 2)، لأنه لا يوجد اختيار اثنين من أزواج - الأيام التي يمكنك الاختيار من بين أيام نهاية. حسنا، لذلك أنا لن يذهب أكثر من القوة الغاشمة الحل هنا. انا ذاهب الى ان اقول لكم ان هناك ون ن حل السجل. ما الخوارزمية هل تعرف ما هو حاليا لا يوجد سجل ن؟ انها ليست مسألة خدعة. 

دمج النوع. دمج النوع هو ن ن سجل، وفي الواقع، طريقة واحدة لحل هذه المشكلة هو استخدام نوع من نوع الدمج فكرة ودعا، بشكل عام، فرق تسد. والفكرة هي كما يلي. تريد حساب أفضل شراء / بيع زوج في النصف الأيسر. العثور على أفضل الأرباح التي يمكن أن تجعل، فقط مع ن الاول على يومين. ثم كنت تريد أن oompute أفضل شراء / بيع زوج على النصف الأيمن، لذلك لا يوجد مشاركة على مدى يومين. والآن فإن السؤال هو، كيف يمكننا دمج هذه الحلول معا مرة أخرى؟ نعم؟ (الطالب، غير مفهومة) حسنا >>. لذلك اسمحوا لي رسم صورة. نعم؟ (جورج، غير مفهومة) بالضبط >>. الحل هو جورج صحيح تماما. ذلك هو اقتراحه، وحساب أول أفضل شراء / بيع زوج، والذي يحدث في النصف الأيسر، لذلك دعونا ندعو أن اليسار، اليسار. أفضل شراء / بيع زوج الذي يحدث في النصف الأيمن. ولكن إذا قارنا هذه الأرقام فقط اثنين، نفتقده حالة حيث نشتري هنا في مكان ما وبيع النصف الأيمن. نشتري في النصف الأيسر، وبيع في النصف الأيمن. وأفضل طريقة لحساب أفضل شراء / بيع زوج يمتد كل شطر هو الحد الأدنى لحساب هنا وحساب الحد الأقصى هنا وتأخذ الفرق الخاصة بهم. وبالتالي فإن القضيتين حيث الزوج البيع / الشراء يحدث هنا فقط، هنا فقط، أو على كل شطر تم تعريفه من قبل هذه الأرقام الثلاثة. حتى أنظمتنا لدمج حلولنا معا مرة أخرى، نحن نريد لحساب أفضل شراء / بيع زوج حيث نشتري على النصف الأيسر والنصف بيع على الحق. وأفضل طريقة للقيام بذلك هي لحساب أقل الأسعار في النصف الأول، أعلى سعر في النصف الأيمن، واتخاذ الفرق الخاصة بهم. 3 الناتجة الأرباح، وهذه الأرقام الثلاثة، وانت تأخذ الحد الأقصى من الثلاثة، وهذا هو أفضل الأرباح التي يمكن أن تجعل أكثر من هذه الأيام الأولى ونهاية. هنا خطوط المهم باللون الأحمر. هذه هي دعوة متكررة لحساب الإجابة في النصف الأيسر. هذه هي دعوة متكررة لحساب الجواب في النصف الأيمن. لهذين حلقات حساب الحد الأدنى والحد الأقصى للفي النصف الأيسر والأيمن على التوالي. أنا الآن حساب الربح الذي يمتد كل شطر، والجواب النهائي هو الحد الأقصى من هذه الثلاثة. حسنا. 

لذلك، بالتأكيد، لدينا خوارزمية، ولكن السؤال الأكبر هو، ما هو مدى تعقيد وقت هذا؟ والسبب ذكرتها دمج النوع هو أن هذا الشكل من أشكال تقسيم الإجابة الى قسمين ومن ثم دمج حلولنا معا مرة أخرى هو بالضبط شكل نوع الدمج. لذلك اسمحوا لي ان اذهب من خلال المدة. إذا حددنا ر ظيفة (ن) ليكون عدد من الخطوات لأيام ن، لدينا اثنين من المكالمات العودية وستكون تكلفة كل طن (ن / 2)، وهناك اثنان من هذه الدعوات. الان انا بحاجة لحساب الحد الأدنى من النصف الأيسر، الذي أستطيع أن أفعل في ن الوقت / 2، بالإضافة إلى الحد الأقصى من النصف الأيمن. ذلك هو ن هذا فقط. ثم بالإضافة إلى بعض العمل المستمر. وهذا تكرار المعادلة هو بالضبط المعادلة تكرار لنوع الدمج. ونحن نعلم جميعا أن دمج النوع هو ن ن سجل الزمن. ولذلك، أيضا هو ن ن خوارزمية لدينا سجل الزمن. هل هذا معنى التكرار؟ مجرد خلاصة موجزة عن هذا: T (ن) هو عدد من الخطوات لحساب الربح الأقصى على مدى أيام ن. الطريقة التي انفصل نداءاتنا العودية هي من خلال اللجوء لدينا الحل في الأيام ن / 2 أولا، ذلك أن مكالمة واحدة، ومن ثم فإننا ندعو مرة أخرى في النصف الثاني. ولهذا مكالمتين. ومن ثم نجد ما لا يقل عن النصف الأيسر، والذي يمكننا القيام به في الوقت الخطية، العثور على الحد الأقصى من النصف الأيمن، والذي يمكننا القيام به في الوقت الخطية. حتى ن / 2 + ن / 2 ن فقط. ثم لدينا بعض العمل المستمر، الذي هو مثل القيام الحساب. تكرار هذه المعادلة هو بالضبط المعادلة تكرار لنوع الدمج. وبالتالي، لدينا خوارزمية خلط ورق اللعب هو أيضا ن ن تسجيل الدخول. حتى مقدار المساحة هل نستخدم؟ دعونا نعود إلى رمز. 

A أفضل السؤال هو، كم عدد إطارات المكدس لدينا أي وقت مضى في أي لحظة؟ منذ نستخدمه العودية، عدد الإطارات مكدس يحدد استخدامنا الفضاء. دعونا النظر N = 8. ندعو المراوغه في 8، الذي سيدعو خلط ورق اللعب على مقالات الأربعة الأولى، والتي تدعو اجراء تعديل على مقالات الأولين. لذلك لدينا هو مكدس - وهذا هو مكدس لدينا. ومن ثم فإننا ندعو خلط ورق اللعب مرة أخرى في 1، وهذا ما قضيتنا الأساسية هي، لذلك علينا أن نعود فورا. هل لدينا من أي وقت مضى أكثر من هذا العديد من إطارات المكدس؟ لأن كل رقم مرة نفعل استدعاء، والاحتجاج عودي إلى خلط ورق اللعب، نقسم حجمنا في النصف. وبالتالي فإن الحد الأقصى لعدد إطارات المكدس لدينا أي وقت مضى في أي لحظة هو بناء على أمر من الأطر سجل ن المكدس. كل إطار المكدس لديه مساحة ثابتة، وبالتالي فإن المبلغ الإجمالي للفضاء، أكبر قدر ممكن من مساحة نستخدم أي وقت مضى هو O (سجل ن) الفضائية حيث n هو عدد الأيام. 

الآن، اطلب من نفسك دائما، "يمكننا أن نفعل أفضل؟" وعلى وجه الخصوص، يمكننا تقليل هذه لمشكلة لدينا حل بالفعل؟ A تلميح: ناقشنا اثنين فقط مشاكل أخرى قبل ذلك، وانها لن تكون المراوغه. يمكننا تحويل هذه المشكلة إلى سوق الأوراق المالية المشكلة subarray القصوى. كيف يمكننا أن نفعل هذا؟ واحد منكم؟ ايمى؟ (ايمى، غير مفهومة) [يو] بالضبط. وبالتالي فإن المشكلة subarray القصوى، نحن نبحث عن مبلغ أكثر من subarray المستمر. واقتراح ايمى لمشكلة الأرصدة، النظر في التغييرات، أو في مناطق الدلتا. وصورة هذا هو - وهذا هو سعر السهم، ولكن إذا أخذنا الفرق بين كل يوم على التوالي - لذلك نحن نرى أن الحد الأقصى للسعر، ونحن أقصى ربح يمكن أن هو إذا كنا هنا شراء وبيع هنا. ولكن دعونا ننظر إلى المستمر - دعونا ننظر إلى المشكلة subarray. حتى هنا، يمكننا أن نجعل - الانتقال من هنا إلى هنا، لدينا التغيير الإيجابي، ومن ثم الانتقال من هنا إلى هنا لدينا التغيير السلبي. ولكن بعد ذلك، والذهاب من هنا إلى هنا لدينا تغيير كبير إيجابية. وهذه هي التغييرات التي نريد أن نلخص للحصول على الربح النهائي. ثم لدينا أكثر سلبية التغييرات هنا. المفتاح لخفض المخزون مشكلتنا مشكلتنا في subarray القصوى هو النظر في دلتا بين أيام. لذلك نحن إنشاء مجموعة جديدة تسمى دلتا، تهيئة الإدخال الأول أن يكون 0، ومن ثم لكل الدلتا (ط)، واسمحوا أن يكون الفرق من بلدي مجموعة المدخلات (ط)، ومجموعة (I - 1). ثم نحن لدينا استدعاء الإجراء الروتيني لsubarray القصوى تمر في مجموعة من الدلتا. ولأن subarray القصوى الزمن الخطي، وهذا التخفيض، وهذا عملية إنشاء هذه المجموعة الدلتا، حان الوقت أيضا الخطية، ثم الحل النهائي للأسهم هو O (ن) العمل بالإضافة إلى O (ن) العمل، لا يزال O (ن) العمل. لذلك لدينا الوقت الخطية حل لمشكلتنا. لا يفهم الجميع هذا التحول؟ 

بشكل عام، فكرة جيدة أنه يجب أن يكون دائما هو محاولة للحد من مشكلة جديدة أن ترونه. إذا كان يبدو مألوفا لمشكلة قديمة، محاولة لتحويلها إلى مشكلة قديمة. وإذا كان يمكنك استخدام جميع الأدوات التي كنت قد استخدمت على مشكلة قديمة لحل مشكلة جديدة. ذلك أن تبرم، والمقابلات الفنية والتحدي. هذه المشاكل هي على الأرجح بعض المشاكل أكثر صعوبة قد تشاهد في مقابلة، لذلك إذا كنت لا تفهم جميع المشاكل التي غطيت فقط، انه بخير. هذه هي بعض من أكثر المشاكل الصعبة. الممارسة، الممارسة، الممارسة. أعطى الكثير من المشاكل في النشرة، وذلك بالتأكيد تحقق من تلك. ونتمنى لك التوفيق في المقابلات الخاصة بك. وتنشر كل ما عندي من الموارد في هذا الرابط، وعرضت واحدة من أصدقائي كبار في إجراء مقابلات وهمية التقنية، إذا كان الأمر كذلك كنت مهتما، البريد الإلكتروني هل ياو في ذلك عنوان البريد الإلكتروني. إذا كان لديك بعض الأسئلة، يمكنك أن تطلب لي. هل لديك أسئلة الرجال محددة تتعلق المقابلات الفنية أو أي مشاكل رأيناه حتى الآن؟ حسنا. حسنا، حظا سعيدا على مقابلات الخاص بك. [CS50.TV]