توجه: نسخه با قابلیت کد برنامه بصورت متنی را در وبگاه https://dorostcode.com منتشر نمودم.
هدف و مراحل پاسخ به مسایل الگوریتمی در حین مصاحبه های برنامه نویسی در مقایسه با مسابقات برنامه نویسی (مثلا ACM) متفاوت است. درمسابقات برنامه نویسی تنها جواب آخر مهم است و نیاز نیست برای کسی راه حل خود را شرح دهیم. در مقایسه در مصاحبه های برنامه نویسی باید برای مصاحبه کننده همزمان که فکر می کنیم تعریف کنیم که چطور فکر می کنیم یا به اصطلاح فکرمان را داد بزنیم (Think out Loud). این کار به مصاحبه کننده نشان خواهد داد که ما چطور فکر می کنیم (thought process). مصاحبه کننده می خواهد بداند که آیا ما ذهن روشنی برای حل مسایل الگوریتمی داریم؟
طبیعی است که ذهن بسیار سریع تر از زبان فعالیت می کند و می خواهد ایده های مختلف را روی مساله امتحان کند تا راه بهینه را بیابد اما زبان از فکر عقب می افتد. اگر استراتژی درستی نداشته باشیم این ممکن است به مکث های نامناسب یا پرت و پلا گویی منجر شود که هر دو نشانه مهارت کم در ارتباط و حل مساله است. بنابر این باید یاد بگیریم که چگونه ذهن خود را در کانال درستی بصورت قطاری از ایده ها هدایت کنیم، چطور یک جریان گفتگوی نرم و مرحله به مرحله بسازیم، و کجای فکرمان را داد بزنیم.
بهترین راه برای ایجاد قطاری از ایده ها استفاده از استراتژی بهبود مرحله به مرحله است. در این روش پاسخگویی به صفر تا صد مساله، یعنی از فهم سوال، سپس بدیهی ترین (اما احتمالا کندتری) راه حل تا یافتن بهترین راه گام به گام به فکر و زبان می آوریم. در این پروسه احتمالا لازم باشد سوالی از مصاحبه کننده بپرسیم تا منظور وی از سوال را دقیق بفهمیم. همچنین احتمالا لازم شود که توضیحاتی بدهیم که از دید ما بدیهی است. باید این کار را انجام دهیم تا مصاحبه کننده بداند که ما چطور فکر می کنیم.
مراحل زیر استراتژی بهبود مرحله به مرحله را در قالب گامهایی توضیح می دهد:
فهم مساله: ابتدا مثالی از ورودی و خروجی بزنیم که نشان دهیم مساله را درست فهمیده ایم. همچنین این کمک می کند که نوع ورودی و فرمت آن را با مصاحبه کننده چک کنیم. این مرحله بسیار مهم است زیرا باید مطمین شویم که مساله اشتباهی را حل نمی کنیم.
راه حل جستجوی کامل: حل مساله را از کند ترین روش که جستجوی کامل (brute force) است آغاز می کنیم. راه حل را برای مصاحبه کننده تشریح می کنیم. سپس سرعت و میزان حافظه آن را (با استفاده از تخمین های Big O که در مبحث الگوریتم ها رایج است) ارزیابی می کنیم و شرح می دهیم. هدف از این کار این است که (۱) مساله را بهتر بشناسیم و بتوانیم تمام حالتهای آن را در نظر بگیریم و (۲) در صورتیکه نتوانستیم راه حل بهینه تر را در زمان مناسب (معمولا ۲۰ تا ۳۰ دقیقه) بیابیم به مصاحبه کننده نشان داده ایم که توانایی یافتن حداقل یک راه حل (اگرچه غیر بهینه) برای مساله را داریم. حتی اگر جواب بهینه را نیافتیم باید از مصاحبه کننده بخواهیم که به ما اجازه دهد تا راه حل غیر بهینه را پیاده سازی کنیم تا هنر پیاده سازی یک الگوریتم را نشان بدهیم.
آزمایش دستی با داده ورودی: با دادن ورودی های مناسب الگوریتم خود را امتحان می کنیم.
تصمیم در مورد پیاده سازی: اگر راه حل به اندازه کافی خوب است یا وقت پیدا کردن الگوریتم مناسب گذشته است به مرحله پیاده سازی بروید.
یافتن ایراد راه حل: در صورتی که الگوریتم درست است اما سرعت آن کم یا حافظه استفاده شده زیاد است باید اشکال آن را بزبان بیاوریم. مثلا اگر الگوریتمی که ارایه کرده ایم سرعت آن بصورت نمایی کند می شود باید بگوییم که این الگوریتم با یک میلیون داده ورودی بسیار کند و غیر عملی است. ممکن است الگوریتم حافظه زیادی استفاده کند. بیان ایراد راه حل به ما ضربه نمی زند بلکه کمک می کند که با هوش بنظر برسیم. علاوه بر این، باید فکر کنید که کجای الگوریتم شما باعث کندی الگوریتم است. مثلا ممکن است که الگوریتم پیشنهادی ما یک کار اضافی را تکرار کند. یافتن چنین ایرادی معمولا مقدمه ای برای ارایه راه حل بهتر است.
ارایه راه حل بهتر: با تامل در ایراد روش قبلی، امتحان کردن ساختمان های داده شناخته شده، یا الگوریتم های مرتبط سعی می کنیم که راه حل بهتری بیابیم. معیار برای ارزیابی الگوریتم ها سرعت و میزان حافظه مورد استفاده برنامه است. معمولا جواب نهایی یک راه حل چند جمله ای (polynomial) یا چیزی بهتر از آن است.
برو به مرحله ۳
پیاده سازی: راه حل خود را پیاده سازی می کنیم. در حین نوشتن خطوط برنامه باید فکرمان را داد بزنیم. شاید لازم باشد به یکی از خطوط قبلی برنامه برگردیم تا چیزی را اصلاح کنیم. این طبیعی است و ایرادی ندارد. نوشتن برنامه یک فرایند مرحله به مرحله است و کسی ما را بخاطر بهبود آن و بالا پایین رفتن در کد، اضافه کردن متغیر، تغییر نام متغیر، و غیره سرزنش نخواهد کرد.
مرور نهایی برنامه: قبل از آنکه اعلام کنیم برنامه را کامل کرده ایم یکبار دیگر منطق برنام را چک می کنیم تا مطمین شویم که آن را درست پیاده سازی کرده ایم. با این کار نشان می دهیم که دقت کافی برای اجتناب از اشکالات برنامه نویسی اجتناب ناپذیر را داریم. همیشه چیزی هستت که باید بهتر شود.
تست نهایی: بعد از نوشتن برنامه با داده های ورودی تستی برنامه خود را امتحان می کنیم تا مطمین شویم که خوب کار می کند. مراحل تست را برای مصاحبه کننده تشریح می کنیم.
نمودار زیر مراحل فوق را در قالب یک فوچارت نشان می دهد.
مراحل روش بهبود مرحله به مرحله برای پاسخ به سوالات مصاحبه های الگوریتمی
یک مثال کامل از اجرای این روش در یک مصاحبه برنامه نویسی را اینجا بخوانید.
