هرگز برای شغلی مصاحبه کرده اید و در انتها اشک شوق مصاحبه کننده را دیده باشید؟ شاید در آن لحظه مصاحبه کننده با خود می گوید: 'یافتمش! برنامه نویسی که دنبالش بودم را یافتم!'
اگر این اتفاق تابحال نیافتاده نگران نباشید. شما تنها نیستید. صادقانه بگویم که این برای من نیز به عنوان مصاحبه شونده اتفاق نیافتاده است. به عنوان مصاحبه کننده نیز هرگز اشک شوق نریخته ام، اما فکر کنم اوقاتی بوده که برق چشمانم نشان داده که چقدر از دیدن یک برنامه نویس خوب ذوق کرده ام.
این رویایی است که پیشنهاد می کنم حین آمادگی برای مصاحبه های برنامه نویسی در سر بپرورانید. به اصطلاح دیگر تلاش کنید حداقل لبخندی از رضایت در چهره مصاحبه کننده بنشانید!
پرسش: برنامه ای بنویسید که مینیمم ارتفاع برگ یک درخت را محاسبه نماید.
پاسخ: حل مساله را با یک مثال شروع می کنیم تا مطمین شویم که آن را درست فهمیده ایم. درخت زیر را در نظر بگیریم.
ارایه راه حل را با روش جستجوی کامل شروع می کنیم. روش جستجوی کامل شامل محاسبه ارتفاع برای همه برگها و محاسبه مقدار مینیمم بین آنهاست.
راه راحت پیاده سازی این الگوریتم استفاده از فراخوانی بازگشتی برای پیمایش عمقی درخت است. اما علاوه بر پیمایش درخت، باید ارتفاع هر گره را هم حساب کنیم. چالش معمول آن است که چطور پس از رسیدن به یک برگ (leaf) بدانیم که ارتفاع آن چقدر بوده است؟ و اینکه نهایتا در چه نقطه ای از الگوریتم باید مینیمم بین ارتفاع همه برگها را حساب کنیم؟ آیا باید ارتفاع ها را در یک لیست بریزیم و نهایتا مینیمم آن را بگیریم یا یک متغیر عمومی داشته باشیم که همیشه مینیمم در آن قرار دارد و کمترین ارتفاع برگ در حین محاسبات در آن قرار گیرد؟
واقعیت این است که محاسبه مقدار نهایی در برگها تنها مدل فکر کردن در برنامه های بازگشتی نیست. البته در برخی از مسایل از جمله برنامه بازگشتی مربوط به ب.م.م (gcd) از این روش استفاده می شود. اما در بسیاری مسایل دیگر محاسبات نهایی پس از برگرداندن مقادیر محاسبه شده از زیر درخت ها و در گره پدر انجام می شود.
برای رسیدن به پیاده سازی تمیزتر باید محاسبات در راه حل کنونی در گره های پدر انجام شوند. باید به این فکر کنیم که چگونه می توان کمترین ارتفاع برگها نسبت به گره پدر را بر اساس مینیمم ارتفاع برگ ها در زیر درخت های سمت چپ و راست آن بدست آورد؟ منظور از مینیمم ارتفاع زیر درخت ها بدون توجه به ارتفاع آنها در درخت پدر است. یعنی اگر زیر درخت تنها یک گره باشد، مینیمم ارتفاع برگها در آن 0 است.
برای ترکیب نتیجه محاسبات زیر درخت ها در گره پدر باید مینیمم بین نتیجه محاسبه برای زیر درخت چپ و راست را بگیریم و یک واحد به آن اضافه نماییم تا مینیمم ارتفاع برگ ها در درخت پدر محاسبه شود. با اجرای بازگشتی این رویه از ریشه درخت، فراخوانی به زیر درخت ها می رسد. با بازگشت از هر زیر درخت، نتایج محاسبات برای زیر برگها ترکیب می شود و نتیجه برای زیر درخت کنونی را می سازد. نهایتا ترکیب نتیجه محاسبات برای زیر درخت های چپ و راست ریشه، نتیجه نهایی را بدست می دهد.
این پیمایش از ریشه تا هریک از برگها می رود و همه گره ها را تنها یکبار مشاهده می کند. چنانچه درخت دارای n گره باشد، پیچیدگی محاسباتی این الگوریتم (O(n می باشد.
در یک مصاحبه واقعی الگوریتم را روی یک مثال اجرا می کنیم تا مطمین شویم که درست کار می کند.
سپس شروع به پیاده سازی الگوریتم می کنیم. نوشتن ساختار گره (Node) اختیاری است ولی برای واضح شدن الگوریم آن را می آوریم. سپس شروع به نوشت الگوریتم بازگشتی می کنیم. نام و پارامتر مناسب برای تابع در نظر می گیریم (خط 1). اگر ریشه زیر درخت Null باشد، مقدار 1- را برمی گردانیم (خط 9 و 10). با توجه به نحوه فراخوانی بازگشتی، این شرط تنها یکبار ممکن است اجرا شود و آن حالتی است که ریشه درخت اصلی Null باشد. سپس بررسی می کنیم که آیا گره ریشه زیر درخت یک برگ است. در این صورت مینیمم ارتفاع برگ در این زیر درخت 0 می باشد و درجا آن را برمی گردانیم (خط 11 و 12).
دو خط بعدی برنامه (خط 13 و 14) فشرده است و نیاز به تمرکز زیادی برای نوشت دارد. در این خط مینیمم ارتفاع برگ برای زیردرخت راست و چپ محاسبه می کنیم. سپس مینیمم بین حاصل فراخوانی های بازگشتی را محاسبه می کنیم. با توجه به اینکه ریشه یک واحد به ارتفاع مینیمم برگ اضافه می کند، نهایتا یک واحد به مینیمم حاصل های می افزاییم و نتیجه را برمی گردانیم.
البته قبل از فراخوانی بازگشتی بررسی می کنیم که آیا زیر درخت چپ و راست خالی هستند. در صورتی که خالی هستند مقدار بینهایت (یعنی بزرگتری مقدار صحیحی ممکن) را به عنوان مینیمم ارتفاع برگ در زیردرخت در نظر می گیریم تا اثر آن در محاسبه مینیمم خنثی شود.
اشکال استفاده روش پیمایش عمقی برای این مساله آن است که همه برگها از جمله عمیق ترین را نیز باید پیمایش کند. درحالیکه اگر بصورت سطح به سطح درخت را پیمایش کنیم، آنگاه اولین برگی که به آن برمی خوریم کم ارتفاع ترین است و در نتیجه نیاز به پیمایش مابقی درخت نخواهیم داشت.
در صورتی که مصاحبه کننده تمایل داشته باشد شروع به پیاده سازی روش دوم می کنیم. همزمان با نوشتن کد سطرها را توضیح می دهیم. برای جلوگیری از اطاله کلام، در این نوشته تنها بخشهایی از کد را توضیح می دهیم. نکته قابل توجه آن است که به همراه گره ها در صف، سطحی که در آن مشاهده شده اند نیز در صف قرار می گیرد. در واقع یک تاپل در صف قرار می دهیم. مثلا در سطر 6, گره ریشه با همراه سطح آن که 0 می باشد به صف اضافه می شود. وقتی که فرزندهای یک گره را به آخر صف اضافه می کنیم، سطح آنها برابر می شود با سطح گره کنونی بعلاوه یک (خط های 11 تا 14). سطح اولین گره ای که مشاهده کردیم برابراست با مینیمم ارتفاع برگهای درخت (خط 9 و 10). قطعه کد زیر پیاده سازی الگوریتم با روش جستجوی سطح به سطح را نشان می دهد.
گفتن اینکه شما روش های مختلف حل مساله را دیده اید و توانایی پیاده سازی آن را دارید، ممکن است اشک شوق مصاحبه کننده را درنیاورد، اما مطمینا وی را تحت تاثیر قرار خواهد داد!
