[Powered by Google Translate] [سیمینار: تکنیکی انٹرویو] [KENNY یو، ہارورڈ یونیورسٹی] [یہ CS50 ہے.] [CS50.TV] ہیلو، سب، میں KENNY ہوں. میں نے اس وقت ایک جونیئر کا مطالعہ کمپیوٹر سائنس ہوں. میں ایک سابق CS TF ہوں، اور میں چاہتا ہوں کہ میں نے یہ تھا جب میں ایک underclassman تھا، اور یہی وجہ ہے کہ میں اس سیمینار کو دے رہا ہوں. تو مجھے امید ہے کہ آپ اس سے لطف اندوز ہوتے ہیں. اس سنگوشٹھی میں تکنیکی انٹرویو کے بارے میں ہے، اور اپنے تمام وسائل اس لنک پر پایا جا سکتا ہے، یہ ٹھیک ہے یہاں لنک کے وسائل کے ایک جوڑے کی ہے. لہذا میں مسائل کی ایک فہرست بنا دیا، اصل میں، بہت کچھ مسائل ہیں. بھی ایک عام وسائل صفحہ جہاں ہم تجاویز حاصل کر سکتے ہیں ہے کہ کس طرح ایک انٹرویو کے لئے تیار کرنے کے لئے، آپ کو ایک حقیقی انٹرویو کے دوران کیا کرنا چاہیے تجاویز، کے ساتھ ساتھ کس طرح مستقبل میں ریفرنس کے لئے مسائل اور وسائل سے رجوع کرنے کا. یہ تمام آن لائن. اور صرف اس سیمینار تردید preface، آپ کے انٹرویو کی تیاری - اس طرح نہیں کرنا چاہئے اس فہرست تک محدود نہیں کیا جانا چاہئے. یہ صرف ایک رہنما کا مقصد ہے، اور آپ سب کچھ میں نمک کی ایک اناج کے ساتھ کہتے ضرور لینا چاہئے، بلکہ سب کچھ میں آپ کے انٹرویو کی تیاری میں آپ کی مدد کرتے تھے کا استعمال کریں. 

میں اگلے چند سلائڈز کے ذریعے آپ کی رفتار تیز کرنے جا رہا ہوں تو ہم اصل کیس اسٹڈیز کے حاصل کرنے کے لئے کر سکتے ہیں. ایک انٹرویو کے سافٹ ویئر انجینئرنگ postion کے لئے ڈھانچہ، عام طور پر 30 سے ​​45 منٹ کا ہے، ایک سے زیادہ راؤنڈ کمپنی پر منحصر ہے. اکثر آپ کو ایک سفید بورڈ پر کوڈنگ گے. تو اس طرح، لیکن اکثر ایک چھوٹے پیمانے پر ایک سفید بورڈ. اگر آپ کو ایک فون انٹرویو کر رہے ہیں، تو شاید آپ کا استعمال کیا جائے گا یا تو collabedit یا ایک Google Doc تاکہ وہ دیکھ سکتا ہے آپ کو کوڈنگ لائیو جب تم جا رہا ہے فون پر انٹرویو. ایک انٹرویو ہی عام طور پر 2 یا 3 مسائل آپ کے کمپیوٹر سائنس کے علم کی جانچ. اور یہ کوڈنگ تقریبا یقینی طور پر شامل ہوں گے. سوالات کے اقسام ہیں کہ آپ دیکھیں گے عام طور پر ڈیٹا ڈھانچے اور الگورتھم ہیں. اور مسائل کی ان اقسام کو کرنے میں، وہ آپ سے پوچھتا ہوں، اچھا لگے گا، وقت اور خلائی پیچیدگی، بڑا O کیا ہے؟ ، اکثر وہ بھی سوال اعلی سطح کی طلب ایسا ہے، تو ایک ایسا نظام ڈیزائن، آپ کو کس طرح اپنے کوڈ ڈال دیں گے؟ کیا انٹرفیس، کیا کلاس، کیا ماڈیول آپ کو آپ کے سسٹم میں کیا ہے، اور کس طرح ایک دوسرے کے ساتھ بات چیت کرتے ہیں؟ تو ڈیٹا ڈھانچے اور الگورتھم کے ساتھ کے طور پر ڈیزائن نظام ہے. 

کچھ عام تجاویز اس سے پہلے کہ ہم ہمارے کیس اسٹڈیز میں کودو. مجھے لگتا ہے کہ سب سے اہم حکمرانی ہمیشہ زور سے سوچ. انٹرویو آپ اپنی سوچ کے عمل کو دکھانے کا موقع سمجھا جاتا ہے. انٹرویو کا کیا مطلب ہے انٹرویو کے لئے اندازہ لگانے کے آپ کو لگتا ہے کہ کس طرح اور کس طرح آپ کو کوئی مسئلہ کے ذریعے جانا. سب سے بری چیز ہے جو آپ کر سکتے ہیں پورے انٹرویو کے دوران خاموش ہو ہے. یہ اچھا نہیں ہے. جب آپ نے ایک سوال کے جواب میں دیا جاتا ہے، آپ کو بھی اس بات کا یقین کر لیں کہ آپ سوال سمجھتے ہیں بنانے کے لئے چاہتے ہیں. تو آپ کے اپنے الفاظ میں سوال واپس دوبارہ اور کوشش مکمل چند آسان ٹیسٹ کے مقدمات کو کام کرنے کی اس بات کا یقین کر لیں کہ آپ سوال سمجھتے ہیں بنانے کے لئے. چند ٹیسٹ کے مقدمات کے ذریعے کام کرنا تم نے کس طرح اس مسئلہ کو حل کرنے کے ایک انترجشتھان دے گا. آپ کو چند نمونوں کی مدد آپ کو مسئلے کو حل کرنے کے لئے بھی دریافت کر سکتے ہیں. ان کی بڑی ٹپ مایوس نہیں کرنے کی ہے. کیا مایوس نہ ہو. انٹرویو چیلنج ہیں، لیکن سب سے بری چیز ہے جو آپ کر سکتے ہیں، خاموش ہونے کے علاوہ میں، واضح طور پر مایوس ہے. آپ کو ایک انٹرویو میں اس تاثر نہیں دینا چاہتا. ایک بات یہ ہے کہ آپ - اس لئے، بہت سے لوگ، جب انہوں نے ایک انٹرویو میں جانا وہ سب سے بہترین حل سب سے پہلے تلاش کرنے کی کوشش کرنے کی کوشش، جب سچ میں، وہاں عام طور پر ہے ایک glaringly واضح حل ہے. یہ سست ہو سکتا ہے، غیر فعال ہو، لیکن آپ اسے صرف بیان کرنا چاہئے ہو سکتا ہے، بہت جس سے بہتر کام کرنے میں آپ کو ایک نقطہ اغاز ہے. اس کے علاوہ، حل کی طرف اشارہ کرتے ہوئے سست کے معاملے میں ہے، بڑا O وقت پیچیدگی یا خلا پیچیدگی، انٹرویو کہ آپ سمجھتے ہیں کا مظاہرہ کرے گی جب ان مسائل کوڈ لکھنے. تو آسان الگورتھم کے ساتھ آنے سے ڈرتے نہیں ہے سب سے پہلے اور پھر وہاں سے بہتر کام کرتے ہیں. کوئی بھی سوال اب تک؟ ٹھیک ہے. 

تو ہمارا پہلا مسئلہ میں کودو. انہوں نے کہا کہ ن integers کی ایک صف کو دیکھتے ہوئے، ایک تقریب ہے جو صف کی shuffles لکھنے ایسی ہے کہ ن integers کے تمام ترتیب برابر کا امکان ہے جگہ. " اور فرض کریں آپ کو دستیاب ایک بے ترتیب عددی جنریٹر ہے جو کہ 0 سے ایک رینج میں ایک عددی پیدا، نصف رینج ہے. کیا ہر کسی کو اس سوال سمجھ میں آیا؟ میں آپ ن integers کے ایک صف دے، اور میں آپ کو یہ شفل چاہتے ہیں. میری ڈائریکٹری میں، میں نے مظاہرہ ہو کہ میرا کیا مطلب میں کچھ پروگراموں کو لکھا تھا. میں 20 عناصر کے ایک صف کے شفل کے لئے جا رہا ہوں، -10 سے +9، اور میں آپ کے پاس اس طرح کی فہرست کی پیداوار کرنا چاہتے ہیں. تو یہ میری کے مطابق ان پٹ کی صف ہے، اور میں نے تم سے یہ شفل چاہتے ہیں. ہم نے اسے پھر سے کر دونگا. کیا اس کی سب سوال سمجھ میں آیا؟ ٹھیک ہے. تو یہ آپ پر منحصر ہے. کچھ خیالات کیا ہیں؟ یہ آپ ن ^ 2، ن لاگ ان کریں (ن)، (ن) کے طور پر کیا کر سکتے ہیں؟ تجاویز کے لئے کھلا. ٹھیک ہے. تو ایک خیال، ایمی کی طرف سے تجویز پیش کی ہے، سب سے پہلے 0 سے 20 تک ایک بے ترتیب تعداد میں، بے ترتیب عددی، ایک حد میں حساب. تو فرض ہمارے صف 20 کی لمبائی ہے. 20 عناصر کے ہمارے خاکہ میں یہ ہماری ان پٹ صف ہے. اور اب، اس تجویز کو ایک نئی صف بنانے کے لئے ہے، تو یہ پیداوار صف ہو جائے گا. میں رینڈ کی طرف سے واپس کی بنیاد پر - تو اگر میں تھا، کا کہنا ہے کہ، 17، 17th عنصر پہلی پوزیشن میں کاپی کریں. اب ہم کو خارج کرنے کی ضرورت - ہم تمام عناصر کو یہاں سے منتقل کرنے کی ضرورت ہے تو زائد ہے کہ ہم آخر میں ایک فرق اور درمیان میں کوئی سوراخ ہے. اور اب ہم عمل کو دہرائیں. اب ہم 0 اور 19 کے درمیان ایک نیا بے ترتیب عددی منتخب کریں. ہم نے ایک نئی میں یہاں ہے، اور ہم اس پوزیشن میں اس عنصر کو کاپی کرنے کے. پھر ہم سے زیادہ اشیاء کو منتقل کریں اور ہم عمل کو دہرائیں جب تک ہم اپنے مکمل نئی صف ہے. اس الگورتھم کی چلت وقت کیا ہے؟ ٹھیک ہے، اس کے اثرات پر غور کریں. ہم ہر عنصر کو جا رہے ہیں. جب ہم نے اس میں ہٹانے، ہم نے اس کے بعد تمام عناصر کو بائیں جا رہے ہیں. اور یہ O (ن) کی قیمت ہے اس لیے کہ اگر ہم نے پہلے عنصر کو ہٹا دیں؟ تو ہم ہر ہٹانے کا ہٹانے - ہر ہٹانے کی ایک O (ن) کے آپریشن کی موجب ہے، اور چونکہ ہم اخراج ن ہے، یہ O شفل (ن ^ 2) کی طرف جاتا ہے. ٹھیک ہے. اتنا اچھا آغاز. اچھی شروعات ہے. 

ایک اور تجویز Knuth شفل کے طور پر جانا جاتا کچھ استعمال کرنے کے لئے ہے، یا شفل فشر Yates. اور یہ اصل میں ایک لکیری وقت شفل ہے. اور خیال بہت ہی اسی طرح ہے. ایک بار پھر، ہم اپنے ان پٹ صف ہے، لیکن ہمارے ان پٹ / آؤٹ پٹ کے لئے دو arrays کا استعمال کرتے ہوئے کی بجائے، ہم صف کے پہلے حصہ کا استعمال کرتے ہیں ہمارے shuffled حصے کا ٹریک رکھنے کے لئے، اور ہم پر نگاہ رکھنے کے، اور پھر ہم unshuffled حصہ کے لئے باقی ہمارے صف چھوڑ. تو یہاں ہے کہ میرا کیا مطلب ہے. ہم اس کے ساتھ شروع کریں - ہم ایک میں کا انتخاب کرتے ہیں، 0 سے 20 تک ایک صف ہے. ہماری موجودہ پوائنٹر پہلے انڈیکس کی طرف اشارہ کرتے ہوئے ہے. ہم کچھ میں یہاں کا انتخاب کرتے ہیں اور اب ہم تبادلہ. تو اگر یہ 5 تھا اور یہ 4 تھی، نتیجے میں صف 5 یہاں اور 4 یہاں پڑے گا. اور اب ہم نے ایک مارکر یہاں نوٹ. سب کچھ بائیں shuffled ہے، اور حق کو سب کچھ unshuffled ہے. اور اب ہم عمل کو دوہرا سکتے ہیں. ہم 1 اور 20 کے درمیان ایک بے ترتیب انڈیکس کا انتخاب کرتے ہیں. تو ہمارے نئے لگتا ہے کہ میں یہاں ہے. اب ہم ہماری موجودہ نئی پوزیشن کے ساتھ اس میں یہاں تبادلہ. تو ہم اس طرح پیچھے گماگمن کرتے ہیں. مجھے زیادہ ٹھوس کوڈ لانے. ہم میں اپنی پسند کے ساتھ شروع کریں - ہم شروع میں 0 کے برابر ہے، ہم ایک بے ترتیب مقام J منتخب صف کے unshuffled حصہ میں، میں (ن) 1. اگر ایسا ہے تو میں یہاں ہوں، یہاں اور صف کے باقی حصوں کے درمیان ایک بے ترتیب انڈیکس کا انتخاب، ہم تبادلہ اور یہ سب آپ کا صف شفل کے لئے ضروری کوڈ آن ہے. کوئی سوال؟ 

ٹھیک ہے، ایک سوال کی ضرورت ہے، کیوں کیا یہ صحیح ہے؟ ہر permutation برابر امکان کیوں ہے؟ اور میں اس کا ثبوت کے ذریعے نہیں کرے گا، لیکن کمپیوٹر سائنس میں بہت سے مسائل کو شامل کے ذریعے ثابت کیا جا سکتا ہے. کس طرح تم میں سے بہت سے شامل سے واقف ہیں؟ ٹھیک ہے. ڈاؤن لوڈ، اتارنا. تو آپ کو سادہ شامل کرکے اس الگورتھم کی درست ثابت ہو سکتا ہے، آپ کے شامل پرختیارپنا کہاں ہو گا کہ فرض میرا شفل ہر permutation برابر کا امکان واپس پہلے میں عناصر. اب، میں 1 + غور کریں. اور جس طرح سے ہم ہماری انڈیکس J تبادلہ کرنے کا انتخاب کرتے ہیں کی طرف سے، اس کی طرف جاتا ہے - اور اس کے بعد آپ کو تفصیلات کام کیوں اس الگورتھم کو واپس کی کم از کم ایک مکمل ثبوت برابر کا امکان امکان کے ساتھ ہر permutation. 

ٹھیک ہے، اگلے مسئلہ ہے. تو "integers کی ایک صف، postive، صفر، منفی دیا، ایک تقریب ہے جو زیادہ سے زیادہ رقم کا حساب لگاتا ہے لکھیں ان پٹ کی صف میں سے کسی continueous subarray. " ایک یہاں مثال کے طور پر اس کیس میں ہے ہے جہاں تمام نمبرز مثبت ہیں، تو اس وقت سب سے اچھا انتخاب پوری صف کرنا ہے. 1، 2، 3، 4، 10 برابر ہے. جب آپ وہاں میں کچھ منفی ہیں، اس معاملے میں ہم صرف پہلے دو چاہتے ہیں کیونکہ -1 اور / یا -3 کا انتخاب ہماری رقم لانے کے نیچے جائے گا. کبھی کبھی ہم صف کے وسط میں شروع ہو سکتے ہیں. کبھی کبھی ہم نے بالکل کچھ بھی نہیں کا انتخاب کرنا چاہتے ہیں، یہ سب سے بہتر کچھ نہیں لے. اور کبھی کبھی یہ زوال لینے کے لئے بہتر ہے، کیونکہ اس کے بعد بات سپر بڑا ہے. کوئی خیال تو؟ (طالب علم unintelligible) >> جی ہاں. فرض کریں کہ میں -1 نہ لو. تو یا تو میں 1،000 اور 20،000 کا انتخاب کرتے ہیں، یا میں صرف 3 ارب منتخب کریں. ٹھیک ہے، سب سے اچھا انتخاب تمام نمبر لینا ہے. یہ -1،، منفی ہونے کے باوجود پوری رقم سے بہتر میں -1 نہیں لے ہے. تو تجاویز میں نے پہلے ذکر کی ایک واضح طور پر واضح بیان کرنا تھا اور جانور کو طاقت سب سے پہلے حل ہے. اس مسئلہ میں ایک جانور ہے طاقت حل کیا ہے؟ جی ہاں؟ [جین] ٹھیک ہے، میں جانور کو طاقت حل سوچتے ہیں تمام ممکنہ کے مجموعے (unintelligible) میں اضافہ ہو جائے گا. [یو] ٹھیک ہے. جین خیال ہر ممکن کرنا ہے - میں paraphrasing ہوں - ہر ممکن مسلسل subarray کرنا ہے، اس رقم کا حساب، اور پھر زیادہ سے زیادہ ہر ممکن مسلسل subarrays لو. کیا منفرد میرے ان پٹ صف میں ایک subarray کی شناخت؟ کی طرح، میں کیا دو چیزوں کی ضرورت ہے؟ جی ہاں؟ (طالب علم unintelligible) >> حق ہے. ایک کم فہرست اور ایک اوپری جانے انڈیکس پابند منفرد مسلسل subarray کا تعین کرتا ہے. [FEMALE طالب علم] کیا ہم اندازہ یہ منفرد کی تعداد کے ایک صف ہے؟ [یو] نمبر اس سوال کا تو ہے ہم نے اپنے صف سنبھالنے - ہمارے صف منفرد تعداد ہے، اور جواب نہیں ہے. 

اگر ہم اپنے جانور کو طاقت حل، پھر سوچکانکوں شروع / آخر کا استعمال منفرد ہماری مسلسل subarray کا تعین کرتا ہے. ، تو اگر ہم ہر ممکن آغاز سے لے کے لئے iterate اور آخر اندراجات کے لئے> یا = شروع، اور <ن، آپ رقم کی گنتی، اور پھر ہم زیادہ سے زیادہ رقم ہے ہم نے اب تک دیکھا ہے. واضح یہ ہے؟ اس حل کا بڑا O کیا ہے؟ Timewise. ^ 2 کافی نہیں ن. نوٹ کریں کہ ہم 0 سے (ن) کے iterate تاکہ لوپ کے لئے ایک ہے. ہم نے تقریبا شروع سے آخر تک دوبارہ، لوپ کے لئے ایک اور iterate. اور اب، اس کے اندر اندر ہم نے ہر تحریر پر ہونے والے تبصروں سے خلاصہ ہے، تاکہ لوپ کے لئے ایک ہے. تو ہم تین loops کے لئے اندر در اندر، 3 ن ^ ہے. ٹھیک ہے. یہ ایک نقطہ اغاز کے طور پر کی جاتی ہے. ہمارے حل ن ^ 3 سے بھی بدتر ہے. کیا ہر جانور کو طاقت حل سمجھ میں آیا؟ 

ٹھیک ہے. ایک بہتر حل متحرک پروگرامنگ نامی ایک خیال کا استعمال کرتے ہوئے کر رہا ہے. اگر آپ CS124 لیتے ہیں، جو والگورزم اور ڈیٹا ساخت ہے، آپ کو اس ٹیکنالوجی سے بہت واقف ہو جائے گا. اور خیال، چھوٹے مسائل کو حل سب سے پہلے تعمیر کرنے کی کوشش ہے. آغاز اور اختتام: کیا میرا مطلب ہے کی طرف سے ہے، ہم اس وقت دو چیزوں کے بارے میں فکر کرنے کی ہے. اور وہ پریشان ہے. کیا ہوگا اگر ہم ان پیرامیٹرز کی ایک سے چھٹکارا مل سکے؟ we're، دیا ہمارا اصل مسئلہ - ایک خیال ہے ایک حد میں کسی بھی subarray کی زیادہ سے زیادہ رقم [O، ن 1] کو تلاش کریں. اور اب ہم ہمارے موجودہ انڈیکس میں ایک نیا subproblem، ہیں جہاں ہم جانتے ہیں، ہم جانتے ہیں کہ ہم وہاں اختتام ضروری ہے. ہماری subarray موجودہ انڈیکس میں ختم ہونا چاہیے. تو باقی مسئلہ ہے، ہم ہماری subarray جہاں شروع کر دینا چاہئے؟ کیا اس کا کوئی مطلب ہے؟ ٹھیک ہے. تو میں اس کوڈت ہے، اور اس کا مطلب کیا ہوا نظر. codirectory میں کہا جاتا subarray پروگرام ہے، اور اشیاء کی تعداد لیتا ہے، اور یہ میری shuffled کی فہرست میں زیادہ سے زیادہ subarray رقم واپس. تو اس معاملے میں، ہماری زیادہ سے زیادہ subarray 3 ہے. اور یہ صرف 2 اور 1 کا استعمال کرتے ہوئے کی طرف سے اٹھائے گئے. اسے دوبارہ چلائیں. یہ بھی 3 ہے. لیکن اس وقت نوٹ کریں، کہ ہم کس طرح 3 ہے. ہم نے - ہم صرف 3 خود لے کیونکہ اس کے دونوں اطراف پر منفی طرف سے گھیر لیا ہے، جو کہ ایک رقم <3 لے آئے گا. 10 اشیاء پر چلانے دو اس بار 7 ہے، ہم معروف 3 اور 4 لے لو. اس بار 8 ہے، اور ہم 1، 4، اور 3 سے لے کر حاصل کریں. تو آپ کو کس طرح ایک انترجشتھان دیتے ہیں، اس تبدیل مسئلہ کو حل کر سکتے ہیں، ہم اس subarray پر ایک نظر لے. ہم اس ان پٹ صف دیا ہے، کر رہے ہیں اور ہم جانتے ہیں کہ جواب 8 ہے. ہم 1، 4، اور 3 لیتے ہیں. لیکن کس طرح ہم واقعی اس جواب مل گیا دیکھو. کی زیادہ سے زیادہ subarray ہے کہ ان سوچکانکوں میں سے ہر ایک میں ختم ہونے کو دیکھو. زیادہ سے زیادہ subarray ہے کہ پہلی پوزیشن پر ختم کرنے کے لئے ہے کیا ہے؟ [ZERO Student کی]. زیرو. >> بس -5 نہیں ہے. یہاں یہ 0 کے طور پر ہو رہا ہے. جی ہاں؟ (طالب علم unintelligible) [یو] اوہ، معاف کرنا، یہ ایک -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 جواب حساب کر سکتے ہیں اس صف اور اس صف میں گزشتہ subproblems کے جوابات کی ایک مجموعہ ہے؟ جی ہاں؟ [FEMALE طالب علم] آپ رقم کی صف رکھنا پوزیشن میں اس سے پہلے تو، 8، اور پھر آپ کو موجودہ subproblem شامل کریں. [یو] تو اس کی تجویز ان دو نمبروں کو دیکھنے کے لئے ہے، اس نمبر اور اس نمبر. تو 8 subproblem کا جواب (- 1 میں) سے مراد ہے. اور اپنے ان پٹ صف A. فون کے لئے ایک زیادہ سے زیادہ subarray کہ میں پوزیشن میں ختم ہو جاتی ہے کو تلاش کرنے کے لئے، میں دو راستے ہیں: میں subarray یا تو جاری رکھ سکتے ہیں جو گزشتہ انڈیکس میں ختم ہوا، یا ایک نئی صف شروع. اگر میں subarray کہ گزشتہ انڈیکس میں شروع جاری تھے، تو زیادہ سے زیادہ رقم میں حاصل کر سکتے ہیں گزشتہ subproblem کا جواب ہے علاوہ موجودہ صف اندراج. لیکن، میں نے بھی ایک نیا subarray شروع کرنے کا انتخاب ہے، جس صورت میں رقم 0 ہے. 1، کے علاوہ موجودہ صف انٹری - تو جواب 0 کی زیادہ سے زیادہ، subproblem میں ہے. کیا اس تکرار کا کوئی مطلب ہے؟ ہمارے تکرار، جیسا کہ ہم نے ابھی پتہ چلا ہے، subproblem میں گزشتہ subproblem کے زیادہ سے زیادہ کے علاوہ اپنے موجودہ صف اندراج کے برابر ہے، جس کا مطلب ہے کہ گزشتہ subarray جاری، یا 0، اپنے موجودہ فہرست میں ایک نیا subarray شروع. اور ایک بار ہم نے تعمیر کے حل کے اس میز ہے، تو ہماری آخری جواب صرف subproblem صف کے اس پار ایک لکیری جھاڑو کرنا اور زیادہ سے زیادہ تعداد کو لے لو. یہ جو میں نے ابھی کہا کے عین مطابق عمل درآمد ہے. تو ہم نے ایک نیا subproblem صف، subproblems تخلیق کرتے ہیں. پہلی انٹری یا تو 0 یا پہلی اندراج، ان دونوں کو زیادہ سے زیادہ ہے. اور subproblems کے باقی کے لئے ہم عین مطابق تکرار ہم صرف دریافت کا استعمال کرتے ہیں. اب ہم نے زیادہ سے زیادہ ہمارے subproblems صف کے حساب ہے، اور یہ کہ ہماری آخری جواب ہے. 

تو کتنا خلائی ہم اس الگورتھم میں استعمال کر رہے ہیں؟ اگر آپ کو صرف CS50 کر لیا ہے، تو آپ کی جگہ نہیں ہے ہو سکتا ہے بہت بات چیت کی. ٹھیک ہے، ایک بات نوٹ کی بات یہ ہے کہ میں نے فون کیا malloc سائز کی (ن) کے ساتھ یہاں ہے. کیا ہے جو آپ کو رائے ہے؟ یہ الگورتھم لکیری خلا کا استعمال کرتا ہے. ہم بہتر کر سکتا ہوں؟ ہے بھی ہے کہ آپ کو نوٹس ہے جو حتمی جواب حساب سے ضروری نہیں ہے؟ مجھے لگتا ہے کہ ایک بہتر سوال کیا ہے، کے بارے میں معلومات ہم آخر تک تمام طریقے سے انجام دینے کی ضرورت نہیں ہے؟ اب، اگر ہم ان دو لائنوں پر نظر آتے ہیں، ہم صرف گزشتہ subproblem کے بارے میں دیکھ بھال، اور ہم زیادہ سے زیادہ ہم نے اب تک دیکھا ہے کے بارے میں ہی خیال رکھتے ہیں. ہماری آخری جواب کا حساب کرنے کے لئے، ہم پوری صف کی ضرورت نہیں ہے. ہم صرف آخری نمبر، گزشتہ دو نمبروں کی ضرورت ہے. زیادہ سے زیادہ کے لئے subproblem صف، اور آخری نمبر کے لئے آخری نمبر. تو، حقیقت میں، ہم ان loops کے ساتھ گلانا کر سکتے ہیں اور لکیری خلا سے مسلسل جگہ جانا. موجودہ رقم اب تک، یہاں، ہمارے subproblem صف subproblem، کے کردار کی جگہ لے لیتا ہے. تو موجودہ رقم، اب تک، گزشتہ subproblem کا جواب ہے. اور وہ رقم، اب تک، ہماری زیادہ سے زیادہ کی جگہ لے لیتا ہے. ہم زیادہ سے زیادہ گنتی ہے جیسا کہ ہم ساتھ جاتے. اور اس طرح ہم لکیری خلا سے مسلسل جگہ جاتے ہیں، اور ہم بھی ایک لکیری ہمارے subarray مسئلہ کا حل ہے. 

یہ طرح کے سوالات کے آپ کو ایک انٹرویو کے دوران مل جائے گا. وقت پیچیدگی کیا ہے، خلائی پیچیدگی کیا ہے؟ آپ کو بہتر کر سکتا ہوں؟ چیزوں جو ارد گرد رکھنے کے لئے غیر ضروری ہیں؟ میں اس نے تجزیہ کرتا ہے کہ آپ اپنی ذمہ داری پر لینا چاہئے اجاگر کرنے کے کے طور پر آپ کو ان مسائل کے ذریعے کام کر رہے ہیں. ہمیشہ خود سے پوچھ، "میں بہتر کر سکتے ہیں؟" اصل میں، ہم اس سے بہتر کر سکتے ہیں؟ ایک چال کے سوال کی بنیاد پر ترتیب دیں. آپ، کیونکہ آپ کی ضرورت نہیں کر سکتے ہیں کم از کم مسئلہ ان پٹ کو پڑھیں. تو حقیقت یہ ہے کہ آپ کی ضرورت ہے کم از کم مسئلہ پر ان پٹ پڑھ کا مطلب ہے کہ آپ لکیری وقت سے بہتر نہیں کر سکتے، اور آپ کو مسلسل خلا سے بہتر نہیں کر سکتا. تو یہ ہے، اصل میں، اس مسئلہ کے لئے بہترین حل ہے. سوال؟ ٹھیک ہے. 

اسٹاک مارکیٹ کا مسئلہ: "کو ن integers، مثبت، صفر یا منفی ایک صف جو ن دنوں کے دوران اسٹاک کی قیمت کی نمائندگی کرتے ہیں، زیادہ سے زیادہ منافع ہے آپ کر سکتے ہیں حساب کرنے کے لئے ایک تقریب لکھنے دیا ہے کہ آپ اور فروخت ان (ن) دن کے اندر اندر بالکل 1 اسٹاک خریدتے ہیں. " بنیادی طور پر، ہم کم خریدنے کے لئے، اعلی فروخت کرنا چاہتے ہیں. اور ہم بہترین منافع ہے جو ہم کر سکتے ہیں کرنا چاہتے ہیں. میری ٹپ واپس جانا، کیا فوری طور پر واضح، آسان جواب ہے، لیکن یہ سست ہے ہے؟ جی ہاں؟ (طالب علم unintelligible) >> جی ہاں. >> تو آپ اگرچہ صرف اسٹاک کی قیمتوں کو دیکھو گے میں وقت میں ہر نقطہ (unintelligible). [یو] ٹھیک ہے، تو اس کا حل - کمپیوٹنگ کی اس تجویز سب سے کم اور سب سے زیادہ کمپیوٹنگ ضروری کام نہیں ہے کی وجہ سے سب سے زیادہ سب سے کم سے پہلے ہو سکتا ہے. تو جانور کو طاقت اس مسئلہ کا حل کیا ہے؟ دو چیزیں ہیں کہ میں منفرد منافع میں تعین کرنے کی ضرورت ہے؟ ٹھیک ہے. جانور کو طاقت کا حل ہے - اوہ، تو، جارج کی تجویز ہے کہ دو دن ہم صرف ضرورت ہے منفرد ان دو دنوں کے منافع کا تعین. تو ہم نے ہر جوڑے کو حساب، خرید / فروخت کی طرح، منافع حساب، جو کہ منفی یا مثبت یا صفر ہو سکتا ہے. زیادہ سے زیادہ منافع ہے کہ ہم دنوں کے تمام جوڑوں کو iterating کے بعد کمپیوٹ. یہ ہماری آخری جواب ہو جائے گا. اور اس کا حل O (ن ^ 2)، کیونکہ وہاں ن دو جوڑے کا انتخاب کریں گے - دن ہے کہ آپ کو آخر کے دنوں کے درمیان منتخب کر سکتے ہیں. ٹھیک ہے، تو میں جانور کو طاقت حل یہاں جانا نہیں کر رہا ہوں. میں آپ کو بتانے جا رہا ہوں کہ ایک ن لاگ ان ن حل ہے. کیا الگورتھم آپ فی الحال پتہ ہے جو ن لاگ ان ن ہے؟ یہ ایک چال کا سوال نہیں ہے. 

طرح ضم کریں. طرح ضم ن لاگ ان ن ہے، اور اصل میں، اس مسئلے کے حل میں سے ایک طریقہ استعمال کرنے کے لئے ہے خیال کی ضم طرح طرح کہا جاتا ہے، عام طور پر، اور فتح کی تقسیم. اور خیال ہے کے طور پر مندرجہ ذیل ہے. آپ کو سب سے بہتر خرید حساب / بائیں نصف میں جوڑی فروخت کرنا چاہتے ہیں. بہترین منافع آپ کو صرف دو دن کے دوران پہلی (ن) کے ساتھ، کر سکتے ہیں تلاش کریں. اس وقت آپ کو سب سے بہتر خرید oompute / صحیح نصف پر جوڑی فروخت کرنا چاہتے ہیں، دو دن کے دوران آخری ن. اور اب سوال یہ ہے کہ ہم کس طرح ان کے حل کے ساتھ میں واپس ضم؟ جی ہاں؟ (طالب علم unintelligible) ٹھیک ہے. >> تو مجھے ایک تصویر کو اپنی طرف متوجہ. جی ہاں؟ (جارج، unintelligible) بالکل ٹھیک ہے. >> جارج کی بالکل صحیح حل ہے. تو اس کی تجویز ہے، سب سے پہلے بہترین جوڑی خرید / فروخت کی گنتی، اور جو بائیں نصف میں ہوتا ہے، تو ہم کہتے ہیں بائیں چھوڑ دیا،. ڈاؤن لوڈ، اتارنا جوڑی جو درست نصف میں ہوتا ہے خرید / فروخت. لیکن اگر ہم صرف ان دو اعداد کے مقابلے میں، ہم کیس لاپتہ کر رہے ہیں ہم یہاں کہاں سے خرید اور صحیح نصف میں کہیں فروخت. ہم بائیں نصف میں خریدتے ہیں، صحیح نصف میں فروخت کرتے ہیں. اور بہترین جوڑی خرید / فروخت جس میں دونوں حصوں spans حساب کا بہترین طریقہ کم از کم یہاں حساب اور زیادہ سے زیادہ یہاں حساب اور ان کے فرق کو لے لو. دو معاملات میں جہاں جوڑے کی خرید / فروخت یہاں صرف اس وقت ہوتی ہے تو، یہاں صرف، یا دونوں حصوں کو ان تین نمبروں کی طرف سے وضاحت کی گئی ہے. ہماری الگورتھم تو ہمارے حل کو واپس کو ایک ساتھ ضم کرنا، ہم بہترین جوڑی خرید / فروخت کا حساب کرنے کے لئے کرنا چاہتے ہیں جہاں ہم بائیں نصف پر خرید اور صحیح نصف پر فروخت. اور ایسا کرنے کے لئے کا سب سے بہترین راستہ ہے جس سے پہلی ششماہی میں سب سے کم قیمت گنتی ہے، صحیح نصف میں زیادہ سے زیادہ قیمت ہے، اور ان کا فرق لے. نتیجے میں تین منافع، ان تین نمبر، آپ کے پاس زیادہ سے زیادہ تین سال کی ہے، اور یہ کہ سب سے بہترین منافع آپ کو ان کا پہلا اور آخر دنوں کے دوران کر سکتے ہیں ہے. یہاں اہم لائنوں سرخ رنگ میں ہیں. یہ ایک پنراورتی بائیں نصف میں جواب حساب کا فون ہے. یہ درست نصف میں ایک پنراورتی جواب حساب کا فون ہے. یہ دو loops کے لئے بائیں اور دائیں نصف پر کم از کم اور زیادہ سے زیادہ حساب، بالترتیب. اب میں منافع بخش ہے کہ دونوں حصوں spans حساب، اور آخری جواب ان تین میں سے زیادہ سے زیادہ ہے. ٹھیک ہے. 

تو، اس بات کا یقین، ہم ایک الگورتھم ہے، لیکن بڑا سوال یہ ہے، اس کے وقت پیچیدگی کیا ہے؟ اور وجہ میں ضم طرح ذکر کیا ہے کہ اس فارم کو جواب تقسیم دو حصوں میں اور پھر ہمارے حل کے ساتھ میں واپس ضم بالکل ضم طرح کے طور پر ہے. تو دو کے وزٹرز کا ریکارڈ رکھا جائے گا. میرے مدت کے ذریعے جانا. اگر ہم نے ایک تقریب ٹی (ن) کی وضاحت اقدامات کی تعداد (ن) کے دنوں کے لئے، ہمارے دو پنراورتی کالز ہر ٹی (ن / 2) کی لاگت اور وہاں ان کالوں کی دو ہے. اب میں بائیں نصف کے کم از کم کا حساب کرنے کی ضرورت ہے، جو میں نے N / 2 وقت کے علاوہ صحیح نصف کے زیادہ سے زیادہ میں کیا کر سکتے ہیں. تو یہ صرف ن ہے. اور پھر کسی مسلسل کام کے علاوہ. اور یہ تکرار مساوات بالکل ضم طرح کی تکرار مساوات ہے. اور ہم سب جانتے ہیں کہ انضمام کی طرح ن لاگ ان کریں (ن) کا وقت ہے. لہذا، ہماری الگورتھم بھی لاگ ان ن وقت (ن) ہے. کیا یہ iteration احساس ہے؟ اس کا بس ایک مختصر recap: T (ن) کے اقدامات کی تعداد زیادہ سے زیادہ منافع کے حساب ہے (ن) کے دن کے دوران. جس طرح سے ہم نے ہمارے پنراورتی کالز سپلٹ پہلے ن / 2 دن ہماری حل بلا ہے، تاکہ ایک فون ہے، اور پھر ہم دوسرے نصف حصے پر ایک بار پھر کہتے ہیں. تو وہ دو فون ہے. اور پھر ہم بائیں نصف پر کم از کم ملے، جو ہم لکیری وقت میں کر سکتے ہیں، صحیح نصف کے زیادہ سے زیادہ، جو ہم لکیری وقت میں کر سکتے ہیں کو تلاش کریں. تو ن / 2 این + / 2 ن ہے. پھر ہم کچھ مسلسل کام ہے، جو ریاضی کر رہی ہے ہے. یہ تکرار مساوات بالکل ضم طرح کی تکرار مساوات ہے. لہذا ہماری شفل الگورتھم بھی ہے ن ن لاگ ان کریں. تو کتنا خلائی ہم استعمال کر رہے ہیں؟ کوڈ واپس جانے دو. 

ایک بہتر سوال کس طرح بہت سے اسٹیک فریم ہے ہم کبھی بھی کسی بھی وقت ہے؟ چونکہ ہم نے تکرار کا استعمال کر رہے ہیں، اسٹیک کے فریموں کی تعداد ہمارے خلا استعمال کا تعین کرتا ہے. چلو ن 8 = غور ہیں. ہم نے 8 شفل فون، جو پہلے چار سے لے شفل کو فون کروں گا، جو پہلے دو سے لے کے ایک شفل فون کروں گا. تو ہمارے اسٹیک ہے - یہ ہمارا اسٹیک ہے. اور پھر ہم شفل 1 پھر کہتے ہیں، اور یہی ہماری بنیاد معاملہ ہے، تو ہم فوری طور پر واپس کر دیں. کیا ہم نے کبھی بھی یہ بہت سے اسٹیک فریم کے مقابلے میں زیادہ ہے؟ نہیں، کیونکہ ہر وقت ہے کہ ہم ایک فریاد کرتے ہیں پنراورتی شفل فریاد، ہم نے نصف میں ہماری حجم کو تقسیم. تو اسٹیک کے فریموں کی زیادہ سے زیادہ تعداد ہم نے کبھی بھی کسی بھی وقت ہے لاگ ان ن اسٹیک فریم کے حکم پر ہے. ہر اسٹیک فریم مستقل جگہ ہے، اور علاقے کا اس لئے کل رقم، جگہ کی زیادہ سے زیادہ رقم ہے جو ہم نے کبھی استعمال کریں O خلا (لاگ ان ن) ہے (ن) کے دنوں کی تعداد کہاں ہے. 

اب، ہمیشہ آپ سے سوال کریں، "بہتر ہے کہ ہم کر سکتے ہیں؟" اور خاص طور پر، ہم یہ ایک مسئلہ ہے ہم نے پہلے سے ہی حل کر لیا کم کر سکتے ہیں؟ ایک اشارہ: ہم صرف اس سے پہلے دو دیگر مسائل پر گفتگو کی، اور اس شفل نہیں. ہم زیادہ سے زیادہ subarray مسئلہ میں اس اسٹاک مارکیٹ کے مسائل کو تبدیل کر سکتے ہیں. ہم یہ کیسے کر سکتے ہیں؟ تم میں سے ایک ہے؟ ایمی؟ (ایمی، unintelligible) [یو] بالکل. زیادہ سے زیادہ subarray مسئلہ تو، ہم مسلسل subarray پر رقم کے لئے تلاش کر رہے ہیں. اور اسٹاک مسئلہ کے لئے ایمی تجویز تبدیلی، یا deltas پر غور کریں. اور اس کی ایک تصویر ہے - یہ اسٹاک کی قیمت ہے، لیکن اگر ہم ہر روز کے درمیان کا فرق لے لیا - تو ہم دیکھتے ہیں کہ زیادہ سے زیادہ قیمت کی زیادہ سے زیادہ منافع، ہم بنا سکتے ہیں اگر ہم یہاں سے خریدنے اور یہاں فروخت ہے. لیکن مسلسل میں دیکھو - subarray مسئلہ کو دیکھو. تو یہاں ہم کر سکتے ہیں - یہاں سے یہاں جانے، ہم نے ایک مثبت تبدیلی ہے، اور پھر یہاں سے یہاں جا ہم ایک منفی تبدیلی ہے. لیکن اس وقت، یہاں سے یہاں جا ہم نے ایک بہت بڑی مثبت تبدیلی ہے. اور ان تبدیلیوں کو کہ ہم نے ہماری آخری منافع حاصل کرنے کے لئے خلاصہ کرنا چاہتے ہیں ہیں. پھر ہم زیادہ منفی تبدیلیاں یہاں ہے. ہمارے زیادہ سے زیادہ subarray مسئلہ میں ہمارے اسٹاک مسئلہ کو کم کرنے کی کلید دن کے درمیان deltas پر غور کرنے کے لئے ہے ہے. تو ہم نامی ایک نیا deltas صف کو تشکیل دیتے ہیں، سب سے پہلے 0 کے لیے لاگ ان ابتدا، اور پھر ہر ڈیلٹا کے لئے (i) کے دو، یہ فرق ہونا میری ان پٹ صف (میں)، اور صف (میں - 1). اس وقت ہم نے اپنے ایک زیادہ سے زیادہ subarray کے لئے معمول کے عمل کی کال ایک ڈیلٹا کی صف میں گزرنے والے. اور اس وجہ سے زیادہ سے زیادہ subarray لکیری وقت ہے، اور یہ کمی، اس ڈیلٹا صف بنانے کے اس عمل، بھی لکیری وقت ہے، تو اسٹاک کے لئے حتمی حل O (ن) کے کام کے علاوہ O (ن) کا کام ہے، اب بھی O (ن) کا کام ہے. تو ہم ایک لکیری وقت ہمارا مسئلہ حل ہے. کیا سب اس تبدیلی کو سمجھنے میں؟ 

عام طور پر، ایک اچھا خیال ہے کہ آپ کو ہمیشہ ہونا چاہئے ایک نیا مسئلہ یہ ہے کہ آپ دیکھ رہے ہیں کو کم کرنے کی کوشش کریں. اگر یہ ایک پرانا مسئلہ سے واقف لگ رہی ہے، یہ ایک پرانا مسئلہ کو کم کرنے کی کوشش کریں. اور اگر آپ تمام اوزار ہے کہ آپ پرانے مسئلہ پر استعمال کیا جاتا ہے کا استعمال کر سکتے ہیں نئے مسئلے کو حل کرنے کے لئے. تو لپیٹ، تکنیکی انٹرویو کا چیلنج کر رہے ہیں. یہ مسائل شاید زیادہ مشکل مسائل میں سے کچھ یہ ہیں ہے کہ آپ کو ایک انٹرویو میں دیکھ سکتے ہیں، اگر ایسا ہے تو آپ تمام مسائل سمجھ میں نہیں آ رہا ہے کہ میں صرف احاطہ کرتا ہے، یہ ٹھیک ہے. یہ زیادہ مشکل مسائل میں سے کچھ ہیں. مشق، مشق، مشق کرتے ہیں. میں پرچہ میں مسائل کی ایک بہت کیا ہے، تو یقینی طور پر ان لوگوں کو باہر چیک کرنے کے لیے ہے. اور آپ کے انٹرویو پر اچھی قسمت ہے. میرے تمام وسائل کو اس لنک میں تعینات ہیں، اور اپنے ایران کے دوستوں میں سے ایک فرضی تکنیکی انٹرویو کرنے کی پیشکش کی ہے، اگر ایسا ہے تو آپ کو دلچسپی ہو، ای میل اس ای میل ایڈریس پر Yao ول. اگر آپ کے کچھ سوالات ہیں، تو تم مجھ سے پوچھ سکتے ہیں. کیا تم لوگ مخصوص تکنیکی انٹرویو سے متعلق سوالات ہیں یا کسی بھی مسائل ہم نے اب تک دیکھا ہے؟ ٹھیک ہے. ٹھیک ہے، آپ کے انٹرویو پر اچھی قسمت ہے. [CS50.TV]