سلام دوست عزیز! به آزمون ورودی آزمون ورودی کارآموزی تابستانه کداستار که توسط آکادمی ستاره برگزار میشه خوش اومدی! هدف این آزمون سنجش شیوهی برنامهنویسیات، در موضوعاتی مثل الگوریتم، گراف و شیگرایی هست. ترتیب سوالا هم از آسون به سخت هست. بعد از مسابقه شیوهی برنامهنویسی و امتیازی که توی این مسابقه گرفتی بررسی میشه و امیدواریم به مرحلهی بعدی که مصاحبهی اسکایپی هست، دعوت بشی! ما در تیم آکادمی ستاره برات از صمیم قلب آرزوی موفقیت داریم و امیدواریم بتونیم توی کارآموزی ببینیمت و به زودی همکار بشیم :)
برای شرکت بهتر در مسابقه پیشنهاد میکنیم لینکهای زیر را مطالعه کنی!
میتونی سوالاتت رو هم از قسمت "سوال بپرسید" مطرح کنی. همچنین برای دسترسی به آخرین اخبار و اطلاعیهها (روال مصاحبه و دورههای بعدی) بعد از آزمون کانال رو چک کن:
یکی از بهروزترین و پیشرفتهترین روشهای تحلیل داده و خلق ارزش با استفاده از دادهها، تحلیل داده مبتنی بر گراف است. در این روش همهی دادههای موجود در مسئله به صورت راسها و یالهای یک گراف بزرگ مدل میشوند و جواب سوالات تحلیلگر داده با اجرای الگوریتمهای پرکاربرد گراف آماده میشود.
یکی از این الگوریتمها یافتن تمام مسیرهای موجود بین دو راس مشخص از گراف است که کاربرد وسیعی در تحلیل دادههای مالی دارد. مثالهای عملیاتی زیر را در نظر بگیرید:
مثال اول: یک مزایده برگزار شده است که نتیجه آن واگذاری یک ملک/کارخانه به قیمت پایینتر از ارزش واقعی بوده، میخواهیم در مورد احتمال رد و بدل شدن رشوه بین برنده مزایده و برگزار کنندگان تحقیق کنیم. اگر رشوهدهنده با چند واسطه رشوه داده باشد تشخیص آن با روشهای معمولی سخت است اما با الگوریتم یافتن مسیرها میتوان تمام مسیرهای انتقال پول بین رشوهدهنده و رشوهگیرنده به طول ۳، ۴ یا حتی بیشتر را روی گراف روابط مالی در چند ثانیه به دست آورد. در صورت وجود حداقل یک مسیر احتمال وجود تبانی در این مزایده بالاست.
مثال دوم: یکی از حوزههای پرکاربرد تحلیل دادهی گرافی، حوزهی بانکی است. یکی از مسائل آن احتمال تبانی وام گیرنده با کارمندان شعبهی بانک است به این صورت که وام گیرنده ممکن است با پرداخت رشوه به کارمند بانک بتواند وام کلانی را بگیرد در صورتی که شرایط دریافت آن وام را نداشته (مثلاً از بدهکاران بانکی بوده و قسطهای وامهای کلان قبلی را هنوز تسویه نکرده است) واحد بازرسی بانک با اجرای الگوریتم یافتن مسیرها روی تراکنشها و خرید و فروشهای وام گیرنده و کارمندان بانکی که از آن وام گرفته است به راحتی میتواند به وجود رابطهی مالی (حتی با چندین واسطه) پی ببرد و جلوی ادامهی تخلفات را بگیرد.
در این مسئله یک گراف (جهتدار یا بدون جهت) به همراه یک راس مبدا و یک راس مقصد به شما داده میشود و از شما خواسته میشود تمام مسیرهای از مبدا تا مقصد که طولشان در بازهی مشخصی قرار دارد، را بیابید. سپس تعداد و شناسهی تمام یالهای موجود در این مسیرها را در خروجی چاپ کنید.
توجه: برنامهی شما حتما باید به زبان باشد و شما مجاز به ایجاد هر گونه کلاس، تابع، اینترفیس و ... هستید.
در خط اول خروجی تعداد تمام یالهایی که در مسیرهایی به کمترین و بیشترین طول داده شده وجود دارند نمایش داده میشوند. در خط دوم خروجی شناسهی تمام یالهای مذکور به ترتیب (از کوچک به بزرگ) با یک فاصله از هم نمایش داده میشوند.
با توجه به جدول زیر تعداد مسیر به حداقل طول ۲ و حداکثر طول ۴، ۲ تاست و یالهای ۲، ۳ و ۴ در آن وجود دارند. بنابراین عدد ۳ (تعداد یالها) و شناسهی یالها در خروجی چاپ میشود.
یالهای موجود | |
---|---|
مسیر ۱ | ۳ ۲ |
مسیر ۲ | ۴ ۲ |
با توجه به جهتدار بودن گراف هیچ مسیری از مبدا (راس ۱) به مقصد (راس ۳) به حداقل طول ۲ و حداکثر طول ۵، وجود ندارد. بنابراین عدد ۰ در خروجی چاپ میشود.