بخش ۲:چگونه به سوال برنامه نویسی در یک مصاحبه پاسخ دهیم؟

هدف و مراحل پاسخ به مسایل الگوریتمی در حین مصاحبه های برنامه نویسی در مقایسه با مسابقات برنامه نویسی (مثلا ACM) متفاوت است. درمسابقات برنامه نویسی تنها جواب آخر مهم است و نیاز نیست برای کسی راه حل خود را شرح دهیم. در مقایسه در مصاحبه های برنامه نویسی باید برای مصاحبه کننده همزمان که فکر می کنیم تعریف کنیم که چطور فکر می کنیم یا به اصطلاح فکرمان را داد بزنیم (Think out Load). این کار به مصاحبه کننده نشان خواهد داد که ما چطور فکر می کنیم (thought process). مصاحبه کننده می خواهد بداند که آیا ما ذهن روشنی برای حل مسایل الگوریتمی داریم؟

طبیعی است که ذهن بسیار سریع تر از زبان فعالیت می کند و می خواهد ایده های مختلف را روی مساله امتحان کند تا راه بهینه را بیابد اما زبان از فکر عقب می افتد. اگر استراتژی درستی نداشته باشیم این ممکن است به مکث های نامناسب یا پرت و پلا گویی منجر شود که هر دو نشانه مهارت کم در ارتباط و حل مساله است. بنابر این باید یاد بگیریم که چگونه ذهن خود را در کانال درستی بصورت قطاری از ایده ها هدایت کنیم، چطور یک جریان گفتگوی نرم و مرحله به مرحله بسازیم، و کجای فکرمان را داد بزنیم.

بهترین راه برای ایجاد قطاری از ایده ها استفاده از استراتژی بهبود مرحله به مرحله است. در این روش پاسخگویی به صفر تا صد مساله، یعنی از فهم سوال، سپس بدیهی ترین (اما احتمالا کندتری) راه حل تا یافتن بهترین راه گام به گام به فکر و زبان می آوریم. در این پروسه احتمالا لازم باشد سوالی از مصاحبه کننده بپرسیم تا منظور وی از سوال را دقیق بفهمیم. همچنین احتمالا لازم شود که توضیحاتی بدهیم که از دید ما بدیهی است. باید این کار را انجام دهیم تا مصاحبه کننده بداند که ما چطور فکر می کنیم.

مراحل زیر استراتژی بهبود مرحله به مرحله را در قالب گامهایی توضیح می دهد:

  1. فهم مساله: ابتدا مثالی از ورودی و خروجی بزنیم که نشان دهیم مساله را درست فهمیده ایم. همچنین این کمک می کند که نوع ورودی و فرمت آن را با مصاحبه کننده چک کنیم. این مرحله بسیار مهم است زیرا باید مطمین شویم که مساله اشتباهی را حل نمی کنیم.
  2. راه حل جستجوی کامل: حل مساله را از کند ترین روش که جستجوی کامل (brute force) است آغاز می کنیم. راه حل را برای مصاحبه کننده تشریح می کنیم. سپس سرعت و میزان حافظه آن را (با استفاده از تخمین های Big O که در مبحث الگوریتم ها رایج است) ارزیابی می کنیم و شرح می دهیم. هدف از این کار این است که (۱) مساله را بهتر بشناسیم و بتوانیم تمام حالتهای آن را در نظر بگیریم و (۲) در صورتیکه نتوانستیم راه حل بهینه تر را در زمان مناسب (معمولا ۲۰ تا ۳۰ دقیقه) بیابیم به مصاحبه کننده نشان داده ایم که توانایی یافتن حداقل یک راه حل (اگرچه غیر بهینه) برای مساله را داریم. حتی اگر جواب بهینه را نیافتیم باید از مصاحبه کننده بخواهیم که به ما اجازه دهد تا راه حل غیر بهینه را پیاده سازی کنیم تا هنر پیاده سازی یک الگوریتم را نشان بدهیم.
  3. آزمایش دستی با داده ورودی: با دادن ورودی های مناسب الگوریتم خود را امتحان می کنیم.
  4. تصمیم در مورد پیاده سازی: اگر راه حل به اندازه کافی خوب است یا وقت پیدا کردن الگوریتم مناسب گذشته است به مرحله پیاده سازی بروید.
  5. یافتن ایراد راه حل: در صورتی که الگوریتم درست است اما سرعت آن کم یا حافظه استفاده شده زیاد است باید اشکال آن را بزبان بیاوریم. مثلا اگر الگوریتمی که ارایه کرده ایم سرعت آن بصورت نمایی کند می شود باید بگوییم که این الگوریتم با یک میلیون داده ورودی بسیار کند و غیر عملی است. ممکن است الگوریتم حافظه زیادی استفاده کند. بیان ایراد راه حل به ما ضربه نمی زند بلکه کمک می کند که با هوش بنظر برسیم. علاوه بر این، باید فکر کنید که کجای الگوریتم شما باعث کندی الگوریتم است. مثلا ممکن است که الگوریتم پیشنهادی ما یک کار اضافی را تکرار کند. یافتن چنین ایرادی معمولا مقدمه ای برای ارایه راه حل بهتر است.
  6. ارایه راه حل بهتر: با تامل در ایراد روش قبلی، امتحان کردن ساختمان های داده شناخته شده، یا الگوریتم های مرتبط سعی می کنیم که راه حل بهتری بیابیم. معیار برای ارزیابی الگوریتم ها سرعت و میزان حافظه مورد استفاده برنامه است. معمولا جواب نهایی یک راه حل چند جمله ای (polynomial) یا چیزی بهتر از آن است.
  7. برو به مرحله ۳
  8. پیاده سازی: راه حل خود را پیاده سازی می کنیم. در حین نوشتن خطوط برنامه باید فکرمان را داد بزنیم. شاید لازم باشد به یکی از خطوط قبلی برنامه برگردیم تا چیزی را اصلاح کنیم. این طبیعی است و ایرادی ندارد. نوشتن برنامه یک فرایند مرحله به مرحله است و کسی ما را بخاطر بهبود آن و بالا پایین رفتن در کد، اضافه کردن متغیر، تغییر نام متغیر، و غیره سرزنش نخواهد کرد.
  9. مرور نهایی برنامه: قبل از آنکه اعلام کنیم برنامه را کامل کرده ایم یکبار دیگر منطق برنام را چک می کنیم تا مطمین شویم که آن را درست پیاده سازی کرده ایم. با این کار نشان می دهیم که دقت کافی برای اجتناب از اشکالات برنامه نویسی اجتناب ناپذیر را داریم. همیشه چیزی هستت که باید بهتر شود.
  10. تست نهایی: بعد از نوشتن برنامه با داده های ورودی تستی برنامه خود را امتحان می کنیم تا مطمین شویم که خوب کار می کند. مراحل تست را برای مصاحبه کننده تشریح می کنیم.

یک مثال عملی از اجرای استراتژی بهبود مرحله به مرحله

فرض کنیم که سوال زیر در یک مصاحبه برنامه نویسی از ما پرسیده می شود:

پرسش: یافتن دو عدد با مجموع ویژه

دنباله ای از اعداد صحیح یکتا و یک عدد ویژه (target) داده شده اند. برنامه ای بنویسید که  به عنوان خروجی، اندیس دو عنصر از این دنباله که حاصل جمعشان برابر با مقدار ویژه است را برگرداند. فرض کنید که برای هر ورودی دقیقا یک راه حل وجود دارد. 

پاسخ

ابتدا سعی کنیم با آوردن مثالی ساده پرسش را بهتر درک کنیم. فرض کنیم دنباله زیر به عنوان ورودی داده شود

و مقدار ویژه که دنبالش هستیم 10 باشد آنگاه باید اندیس زوج مقادیری را بیابیم که مجموع آنها 10 می شود. در نگاه اول ممکن است بنظر برسد که دو پاسخ برای این ورودی وجود دارد بخاطر اینکه 5+5 و 8+2 هر دو برابر 10 می شوند. این موضوع را با مصاحبه کننده در میان می گذاریم. فرض ما این است که مصاحبه کننده تاکید می کند که اندیسهای زوجی که می یابیم باید متفاوت باشند. بنابراین زوج پاسخ 8 و 2 و خروجی مورد نظر اندیسهای آندو یعنی 0 و 2 است.

حال به ارایه روش جستجوی کامل فکر و آن را تشریح می کنیم. در این پرسش جستجوی کامل یعنی عناصر دنباله را دو به دو با هم جمع کنیم و با مقدار ویژه مقایسه کنیم. هرگاه مقدار ویژه به عنوان حاصل مشاهده شد اندیس دو مقدار یافته شده را برگردانیم. روش جستجوی کامل n * (n-1)/2 زوج بوجود می آورد. بنابر این پیچیدگی محاسباتی این الگوریتم (O(n^2 می باشد.

در این لحظه مصاحبه کننده ما را برای یافتن اولین راه حل عملی تحسین می کند. اما واضح است که این روش کند است و روی یک لیست مثلا یک میلیونی خیلی کند است. مصاحبه کننده ما را برای برنامه نویسی سیستم هایی می خواهد که داده های زیادی دارند و باید الگوریتم بهینه با سرعت مناسب بکار ببرند. بنابراین از ما میپرسد که چگونه می شود این را بهتر کرد؟

در این لحظه می توانیم بررسی کنیم که بکار بردن ساختمان های داده دیگر مثلا یک دیکشنری می تواند حل مساله را تندتر کند؟ یا اینکه اگر داده ها را مرتب کنیم سریعتر به پاسخ می رسیم؟ فرض ما این است که با خونسردی  و گام به گام دیدگاههای خود را برای راه حل هایی که سریعتر هستند بیان می کنیم. اما متاسفانه هنوز سرعت کافی برای پیدا کردن سریع راه حل بهینه نداریم. بیش از نیم ساعت از مصاحبه گذشته است بنابراین محترمانه از مصاحبه کننده می خواهیم که اجازه دهد راه حل جستجوی کامل که ابتدا پیشنهاد کردیم را پیاده کنیم. بخاطر داشته باشیم که پیاده کردن درست یک راه حل کند بهتر از یک کد ناقص برای یک راه حل بهینه است. 

مصاحبه کننده به ما اجازه می دهد که راه حل را پیاده کنیم. ابتدا یک نام مناسب برای تابع و پارامترهای مناسب آن را در نظر می گیریم. سپس پارامتر ها و معنای آن را برای مصاحبه کننده توضیح می دهیم و نظر مصاحبه کننده را جویا می شویم (خط ۱). اولین پارامتر این تابع nums می باشد که یک لیست حاوی دنباله ای از اعداد است.

با بکارگیری دو متغیر به عنوان اندیس، می توانیم هر دو عنصر ممکن از لیست را با هم جمع و با مقدار ویژه مقایسه کنیم . ساده ترین روش  برای پیاده سازی استفاده از دو حلقه تو در توست (خطهای ۳ تا ۶). حلقه بیرونی (خط ۳)، عناصر لیست را به ترتیب از ابتدا تا انتها می پیماید. برای هر عنصر در حلقه بیرونی، حلقه درونی (خطوط ۴ تا ۶) تمام عناصر بعد از آن تا انتهای لیست را می پیماید. هر تکرار در حلقه  درونی یک زوج ممکن از عناصر لیست را ایجاد میکند. با محاسبه مجموع این زوج مشخص می شود که آیا مجموع آندو برابر مقدار ویژه می شود. تکه کد زیر این روش شده را پیاده می کند.

def twoSum(nums, target):
    nums_len = len(nums)
    for i in range(nums_len):
        for j in range(i+1, nums_len):
            if nums[i] + nums[j]==target:
                return [i , j]

ارایه راه حل بهتر

الگوریتم جستجوی کامل روی یک لیست طولانی کند است. بنابراین مصاحبه کننده از ما می خواهد الگوریتم بهتری ارایه کنیم. برای یافتن راه حل دیگر به تعابیر دیگر این پرسش می اندیشیم. یک تعبیر پرسش فوق آن است که عنصری با مقدار x در لیست را بیابیم که متمم آن (یعنی target-x) نیز در لیست وجود داشته باشند. این تعبیر پیشنهاد می کند که برای حل این پرسش، به ازای هر عنصر با مقدار x  در لیست، در بین مابقی عناصر داده شده مقدار target-x را جستجو کنیم. با توجه به اینکه جستجو برای یافتن مقادیر مختلف بارها تکرار می شود، یک لیست برای این کار مناسب نیست زیرا هر بار باید تک تک عناصر آن را چک کنیم. ساختمان داده دیکشنری برای این کار مناسب تر است زیرا بدون جستجوی تک تک عناصر لیست سریعا میتواند سریعا بگوید که آیا یک مقدار در بین عناصر داده شده وجود دارد. بنابراین برای حل مساله می توانیم ابتدا تنها یکبار آنرا پیمایش کنیم و مقادیر عناصر لیست (به عنوان کلید) و اندیس موقعیت آن (به عنوان مقدار) را به دیکشنری(dictionary یا hashtable) اضافه کنیم. سپس می توانیم از ابتدای لیست دوباره شروع کنیم و هر برای هر عنصر با مقدار x در دیکشنری بررسی کنیم که آیا target-x در آن وجود دارد. اگر متمم x وجود داشت آنگاه اندیس x و target-x را به عنوان پاسخ برمی گردانیم. با توجه با اینکه عمل بررسی وجود یک کلید در یک دیکشنری بی درنگ (یعنی(O(1) انجام می شود چنین الگوریتمی دارای پیچیدگی محاسباتی (O(n خواهد بود. برای اینکه از درستی عملکرد برنامه مطمین شویم اجرای آن روی مثال فوق را دنبال می کنیم. در مرحله اول با پیمایش لیست دیکشنری را تشکیل می دهیم.

سپس از ابتدای لیست دوباره شروع می کنیم. با دیدن مقدار 14 به عنوان مثال, وجود متمم آن یعنی 5- را دیکشنری وارسی می کنیم. این مقدار در دیکشنری وجود ندارد. بنابر این پاسخی شامل 14 نداریم. بنابراین سراغ عنصر بعدی یعنی 4 می رویم. سپس متمم آن یعنی 5 را در دیکشنری وارسی می کنیم. با توجه به اینکه 5 در دیکشنری هست پاسخ را یافته ایم. مقدار عنصر 5 در دیکشنری اندیس موقعیت آن در لیست اولیه است. بنابر این اندیس مربوط به عنصر 4 (یعنی 1) و مقدار مربوط به کلید 5 در دیکشنری (یعنی 3) پاسخ می باشند. بنابر این الگوریتم درست عمل می کند و شروع به پیاده سازی می کنیم.

این الگوریتم را می توانیم بگونه ای پیاده سازی کنیم که دو مرحله الگوریتم یعنی ساختن دیکشنری و پیمایش مجدد لیست را باهم ترکیب نماید. یعنی در زمان پیمایش لیست، ابتدا دیکشنری را وارسی می کنیم. در صورتی که پاسخ یافت نشد عنصر جدید را به همراه اندیسش (به عنوان زوج کلید) به دیکشنری اضافه می کنیم و به پیمایش در لیست به همین طریق ادامه می دهیم. شروع به پیاده سازی این الگوریتم بهبود یافته می کنیم. ابتدا نام مناسب به تابع و پارامترها می دهیم (خط 1). سپس یک دیکشنری خالی تعریف می کنیم (خط 2). آنگاه در یک حلقه تکرار در لیست پیش می رویم (خط 3 تا 7). هر وارسی می کنیم که آیا متمم عنصر iام در دیکشنری وجود دارد. در صورت وجود پاسخ را یافته ایم و اندیسهای مربوط به جواب مقدار عنصر متمم در دیکشنری و i خواهند بود (خط 4 و 5). در غیر این صورت عنصرi ام را به دیکشنری اضافه می کنیم (خط 7).

def twoSum(nums, target):
	h = {}
	for i in range(len(nums)):
		if target-nums[i] in h:
			return [h[target-nums[i]], i]
		else:
			h[nums[i]] = i

در انتها برنامه را دو باره مرود می کنیم و با داده های ورودی تست می کنیم. نهایتا لبخند رضایت مصاحبه کننده را تماشا می کنیم.





GiottoPress by Enrique Chavez