در این پست راه اجرای کامل مراحل استراتژی بهبود مرحله به مرحله که در پست قبلی مطرح شد را با یک مثال بصورت عملی شرح می دهیم. علاوه بر این می توانید در این ویدیو نمونه ای خلاصه از نحوه پاسخگویی به سوال یک مصاحبه الگوریتمی توسط مهندسان شرکت گوگل را ببینید.
فرض کنید که سوال زیر در یک مصاحبه برنامه نویسی از ما پرسیده می شود:
دنباله ای از اعداد صحیح یکتا و یک عدد ویژه (target) داده شده اند. برنامه ای بنویسید که به عنوان خروجی، اندیس دو عنصر از این دنباله که حاصل جمعشان برابر با مقدار ویژه است را برگرداند. فرض کنید که برای هر ورودی دقیقا یک راه حل وجود دارد.
پاسخ: ابتدا سعی می کنیم با آوردن مثالی ساده پرسش را بهتر درک کنیم (مرحله فهم مساله). فرض می کنیم دنباله زیر به عنوان ورودی داده شده است ...
... و مقدار ویژه که دنبالش هستیم 10 می باشد. برنامه ای که می نویسیم باید اندیس زوج مقادیری که مجموعشان 10 می شود را برگرداند. در نگاه اول ممکن است بنظر برسد که دو پاسخ برای این ورودی وجود دارد بخاطر اینکه 5+5 و 8+2 هر دو برابر 10 می شوند. این موضوع را با مصاحبه کننده در میان می گذاریم. فرض ما این است که مصاحبه کننده تاکید می کند که اندیسهای زوجی که می یابیم باید متفاوت باشند. بنابراین زوج پاسخ 8 و 2 و خروجی مورد نظر اندیسهای آندو یعنی 0 و 2 است.
حال سعی می کنیم الگوریتم جستجوی کامل برای این مساله را بیابیم و آن را تشریح کنیم (مرحله راه حل جستجوی کامل). الگوریتم جستجوی کامل برای حل این پرسش یعنی عناصر دنباله را دو به دو با هم جمع کنیم و با مقدار ویژه مقایسه کنیم.
با استفاده از داده های ورودی شرح می دهیم که زوج های مقادیر در مثال فوق چه هستند و چگونه بدست می آیند (آزمایش دستی با داده ورودی). به عنوان مثال می گوییم که عنصر اول در کنار هر یک از عناصر بعدی اش سه زوج (5, 8)، (2, 8), (15, 8) را تشکیل می دهند. به همین شکل هر عنصر در موقعیت iام با تمام عناصر در موقعیت i+1 تا انتهای لیست یک زوج را تشکیل می دهند. در حین تشکیل زوج های ممکن، هرگاه مقدار ویژه به عنوان حاصل مشاهده شد اندیس دو مقدار یافته شده را به عنوان حاصل برمی گردانیم. در بدترین حالت روش جستجوی کامل باید همه زوج های ممکن، یعنی n * (n-1)/2 زوج مقادیر را بوجود آورد. بنابر این پیچیدگی محاسباتی این الگوریتم (O(n^2 می باشد.
در این لحظه مصاحبه کننده ما را برای یافتن اولین راه حل عملی تحسین می کند. اما واضح است که این روش کند است و روی یک لیست مثلا یک میلیونی خیلی کند است. مصاحبه کننده ما را برای برنامه نویسی سیستم هایی می خواهد که داده های زیادی دارند و باید الگوریتم بهینه با سرعت مناسب بکار ببرند. بنابراین از ما میپرسد که چگونه می شود این را بهتر کرد؟در این لحظه می توانیم بررسی کنیم که بکار بردن ساختمان های داده دیگر مثلا یک دیکشنری می تواند حل مساله را تندتر کند؟ یا اینکه اگر داده ها را مرتب کنیم سریعتر به پاسخ می رسیم؟
فرض ما این است که با خونسردی گام به گام دیدگاههای خود را برای راه حل هایی که سریعتر هستند بیان می کنیم. ممکن است که هنوز سرعت کافی برای پیدا کردن سریع راه حل بهینه را نداشته باشیم. در بدترین حالت ممکن است بیش از نیم ساعت از مصاحبه گذشته باشد و ما راه حل نهایی را نیافته باشیم. بنابر این برای اینکه از خرابی کامل مصاحبه جلوگیری کنیم محترمانه از مصاحبه کننده می خواهیم که اجازه دهد که راه حل جستجوی کامل که پیشنهادیمان را پیاده کنیم (تصمیم به پیاده سازی الگوریتم درست ولی غیر بهینه بدلیل کمبود وقت). بخاطر داشته باشیم که پیاده کردن درست یک راه حل کند بهتر از ختم مصاحبه بدون پیاده سازی کامل یک الگوریتم است. مصاحبه کننده به ما اجازه می دهد که راه حل را پیاده کنیم.
بنابر این شروع به پیاده سازی می کنیم (پیاده سازی). ابتدا یک نام مناسب برای تابع و پارامترهای مناسب آن را در نظر می گیریم (خط ۱). سپس پارامتر ها و معنای آن را برای مصاحبه کننده توضیح می دهیم و نظر مصاحبه کننده را جویا می شویم. اولین پارامتر این تابع nums می باشد که یک لیست حاوی دنباله ای از اعداد است.با بکارگیری دو متغیر به عنوان اندیس، می توانیم هر دو عنصر ممکن از لیست را با هم جمع و با مقدار ویژه مقایسه کنیم . ساده ترین روش برای پیاده سازی استفاده از دو حلقه تو در توست (خطهای ۳ تا ۶). حلقه بیرونی (خط ۳)، عناصر لیست را به ترتیب از ابتدا تا انتها می پیماید. برای هر عنصر در حلقه بیرونی، حلقه درونی (خطوط ۴ تا ۶) تمام عناصر بعد از آن تا انتهای لیست را می پیماید. هر تکرار در حلقه درونی یک زوج ممکن از عناصر لیست را ایجاد میکند. با محاسبه مجموع این زوج مشخص می شود که آیا مجموع آندو برابر مقدار ویژه می شود. تکه کد زیر این روش را پیاده می کند.
سپس اجرای برنامه فوق را روی لیست ورودی مثال بالا بصورت دستی اجرا می کنیم. برای این کار می توانیم یک جدول مانند بسازیم که هر سطر آن یک متغیر را نشان می دهد و با اجرای الگوریتم بصورت دستی مقادیر را بروز می کنیم. مقادیر چنین جدولی در اولین اجرای حلقه داخلی چنین خواهد بود:
nums | [8, 5, 2, 15]
target | 10
nums_len | 4
i | 0
j | 1
وقتی یک متغیر مقدار جدیدی می گیرد می توانیم روی مقدار قبلی خط بکشیم و مقدار جدید را جلوی آن بنویسیم. به هر حال الگوریتم را تا انتها بصورت دستی اجرا می کنیم تا مطمین شویم که درست کار می کند.
ممکن است که مهارت کافی در یافتن راه حل های بهینهداشته باشیم. با توجه به اینکه الگوریتم جستجوی کامل فوق روی یک لیست طولانی کند است، به فکر کردن برای یافتن راه حل بهینه ادامه می دهیم (ارایه راه حل بهتر).
برای یافتن راه حل بهتر روش های متفاوتی وجود دارد. از جمله یافتن ایراد روش راه حل بهینه و یافتن قسمتی از الگوریتم که کارهای تکراری انجام می دهد. با اصلاح الگوریتم بگونه ای که تکرارهای اضافی انجام نشود به الگوریتم بهتر می رسیم. روش دیگر یافتن تعابیر دیگر مساله است که کمک می کند راه حل بهتری پیدا کنیم. در بدترین حالت می توانیم فکر کنیم که چگونه ساختمان های داده مختلف ممکن است کمک کنند که بتوانیم یک الگوریتم را سریعتر کنیم.
برای یافتن راه حل دیگر برای این مساله به تعابیر دیگر این پرسش می اندیشیم. یک تعبیر پرسش فوق آن است که باید مقدار x در لیست را بیابیم که متمم آن (یعنی target-x) نیز در لیست وجود دارد. این تعبیر پیشنهاد می کند که برای حل این پرسش، به ازای هر عنصر با مقدار x در لیست، در بین مابقی عناصر داده شده مقدار target-x را جستجو کنیم. با توجه به اینکه جستجو برای یافتن مقادیر مختلف بارها تکرار می شود، یک لیست برای این کار مناسب نیست زیرا هر بار باید تک تک عناصر آن را چک کنیم. ساختمان داده دیکشنری مشکل کندی جستجوی مجدد را حل می کند زیرا بدون جستجوی تک تک عناصر لیست سریعا میتواند بگوید که آیا یک مقدار در بین عناصر داده شده وجود دارد؟
بنابراین برای حل مساله می توانیم ابتدا تنها یکبار آنرا پیمایش کنیم و مقادیر عناصر لیست (به عنوان کلید) و اندیس موقعیت آن (به عنوان مقدار) را به دیکشنری(dictionary یا hashtable) اضافه کنیم. سپس می توانیم از ابتدای لیست دوباره شروع کنیم و هر برای هر عنصر با مقدار x در لیست بررسی کنیم که آیا target-x در دیکشنری وجود دارد؟ اگر متمم x در دیکشنری وجود داشت آنگاه اندیس x و target-x را به عنوان پاسخ برمی گردانیم. با توجه با اینکه عمل بررسی وجود یک کلید در یک دیکشنری بی درنگ (یعنی(O(1) است، الگوریتمی ارایه شده دارای پیچیدگی محاسباتی (O(n خواهد بود. همچنین برای مصاحبه کننده شرح می دهیم که بخاطر بکارگیری دیکشنری، این الگوریتم n خانه حافظه بیشتر در مقایسه با الگوریتم جستجوی کامل استفاده می کند.
برای اینکه از درستی عملکرد برنامه مطمین شویم اجرای آن روی مثال فوق را دنبال می کنیم. در مرحله اول با پیمایش لیست دیکشنری را تشکیل می دهیم (آزمایش دستی با داده ورودی).
سپس از ابتدای لیست دوباره شروع می کنیم. با دیدن مقدار 14 به عنوان مثال, وجود متمم آن یعنی 5- را دیکشنری وارسی می کنیم. این مقدار در دیکشنری وجود ندارد. بنابر این پاسخی شامل 14 نداریم. بنابراین سراغ عنصر بعدی یعنی 4 می رویم. سپس متمم آن یعنی 5 را در دیکشنری وارسی می کنیم. با توجه به اینکه 5 در دیکشنری هست پاسخ را یافته ایم. مقدار عنصر 5 در دیکشنری اندیس موقعیت آن در لیست اولیه است. بنابر این اندیس مربوط به عنصر 4 (یعنی 1) و مقدار مربوط به کلید 5 در دیکشنری (یعنی 3) پاسخ می باشند. بنابر این الگوریتم درست عمل می کند.
حال شروع به پیاده سازی الگوریتم می کنیم (پیاده سازی). این الگوریتم را می توانیم بگونه ای پیاده سازی کنیم که دو مرحله الگوریتم یعنی ساختن دیکشنری و پیمایش مجدد لیست را باهم ترکیب نماید. یعنی در زمان پیمایش لیست، ابتدا دیکشنری را وارسی می کنیم. در صورتی که پاسخ یافت نشد عنصر جدید را به همراه اندیسش (به عنوان زوج کلید) به دیکشنری اضافه می کنیم و به پیمایش در لیست به همین طریق ادامه می دهیم. ابتدا نام مناسب به تابع و پارامترها می دهیم (خط 1). سپس یک دیکشنری خالی تعریف می کنیم (خط 2). آنگاه در یک حلقه تکرار در لیست پیش می رویم (خط 3 تا 7). هر وارسی می کنیم که آیا متمم عنصر iام در دیکشنری وجود دارد. در صورت وجود پاسخ را یافته ایم و اندیسهای مربوط به جواب مقدار عنصر متمم در دیکشنری و i خواهند بود (خط 4 و 5). در غیر این صورت عنصرi ام را به دیکشنری اضافه می کنیم (خط 7).
در انتها برنامه را دو باره مرور می کنیم و با داده های ورودی تست می کنیم. نهایتا لبخند رضایت مصاحبه کننده را تماشا می کنیم.
