آموزش ۵۰۰+ سوال و جواب مصاحبه ساختارهای داده ۲۰۲۶ - آخرین آپدیت

پوشش دقیق حوزه‌های آزمون

این مخزن آزمون‌های تمرینی دقیقاً به گونه‌ای ساختار یافته است که وزن مفهومی و سخت‌گیری الگوریتمی مورد انتظار در مراحل غربالگری فنی شرکت‌های مهندسی برتر را منعکس کند.

• گراف‌ها (۲۰٪): نمایش گراف (ماتریس/لیست مجاورت)، جستجوی اول سطح (BFS)، جستجوی اول عمق (DFS)، کوتاه‌ترین مسیرها (Dijkstra، Bellman-Ford)، درخت‌های پوشای کمینه (Prim، Kruskal) و مرتب‌سازی توپولوژیک.

• برنامه‌نویسی پویا (۱۵٪): Memoization در مقابل Tabulation، طولانی‌ترین زیردنباله مشترک (LCS)، مسائل کوله‌پشتی، انواع مسیر یابی و انتقال‌های ماشین وضعیت.

• درخت‌ها و جداول هش (۱۵٪): درخت‌های جستجوی دودویی (BST)، درخت‌های متعادل AVL/Red-Black، پیمایش درخت (In-order، Pre-order، Post-order، Level-order)، پیاده‌سازی جدول هش و استراتژی‌های حل تصادم (Chaining، Open Addressing).

• آرایه‌ها و رشته‌ها (۱۰٪): تکنیک‌های دو اشاره‌گر، الگوهای پنجره لغزان (Sliding Window)، پیمایش آرایه، دستکاری رشته‌ها، جستجوی زیررشته و الگوریتم‌های تطبیق الگو (KMP، Rabin-Karp).

• پشته‌ها و صف‌ها (۱۰٪): عملیات پشته/صف، پیاده‌سازی با آرایه و لیست پیوندی، پشته‌های یکنواخت (Monotonic)، صف‌های حلقوی و تجزیه/ارزیابی عبارات ریاضی.

• دستکاری بیت و بازگشت (۱۰٪): عملیات بیتی (AND، OR، XOR، shiftها)، شمارش بیت‌های فعال، بیت‌ماسکینگ، بازگشت با عقب‌گرد (Backtracking)، پارادایم‌های تقسیم و غلبه و محاسبه سربار حافظه.

• هیپ‌ها و مرتب‌سازی (۱۰٪): پیاده‌سازی Min/Max heap، صف‌های اولویت، مرتب‌سازی Heap، بهینه‌سازی‌های Quick sort، مکانیسم‌های Merge sort و مرتب‌سازی‌های غیرمقایسه‌ای.

• مباحث پیشرفته (۱۰٪): جریان شبکه (Ford-Fulkerson)، مبانی هندسه محاسباتی، ساختارهای پیشرفته رشته (Tries، Suffix Trees)، انواع پیشرفته گراف و شناسایی مسائل NP-complete.

درباره این دوره

پشت سر گذاشتن مراحل غربالگری فنی برای نقش‌های مهندسی بسیار رقابتی، چیزی فراتر از حفظ کردن چند الگوی ساده کدنویسی است. مصاحبه‌کنندگان به دنبال چارچوب‌های شفاف حل مسئله، انتخاب‌های بهینه برای پیچیدگی زمانی-مکانی و توانایی شناسایی موارد خاص (Edge Cases) تحت فشار هستند. من این پلتفرم جامع تمرینی را طراحی کردم تا تفکر انتقادی شما را به چالش بکشم و شکاف بین کدهای ساده آموزشی و منطق تحلیلی واقعی مورد نیاز در مصاحبه‌های تخته‌سفید (Whiteboard) را پر کنم.

با ۵۵۰ سوال اصلی و با دقت طراحی شده، این منبع به جای تعاریف کلی نحو زبان، بر آگاهی عمیق از موقعیت‌ها تمرکز دارد. من سناریوهای دنیای واقعی، مسیرهای پیچیده بازگشتی، گلوگاه‌های غیرمنتظره زمان اجرا و ساختارهای پیچیده درخت/گراف را کالبدشکافی می‌کنم. هر سوال توسط یک تحلیل فنی جامع پشتیبانی می‌شود که توضیح می‌دهد چرا رویکرد بهینه موفق می‌شود و چرا گزینه‌های جایگزین از نظر مقیاس یا پیچیدگی شکست می‌خورند. چه هدف شما جایگاه مهندس نرم‌افزار، متخصص الگوریتم یا توسعه‌دهنده بک‌اند باشد، این کیت آماده‌سازی متمرکز، تمرینات لازم برای موفقیت در مصاحبه‌های الگوریتمی در اولین تلاش را به شما می‌دهد.

نمونه سوالات تمرینی

برای ارزیابی عمق، قالب‌بندی و سخت‌گیری ساختاری مطالب ارائه شده در این مخزن، لطفاً این سه نمونه سوال جامع را بررسی کنید.

سوال ۱: موازنه زمان-فضا در ارزیابی کوتاه‌ترین مسیر گراف

یک موتور مسیریابی شبکه نیاز دارد کوتاه‌ترین مسیرهای تک-منبع را در یک گراف جهت‌دار شامل ۵,۰۰۰ راس و ۱۲,۰۰۰ یال پیدا کند. نکته حیاتی این است که سیستم دارای قوانین پردازش پویا است که به برخی یال‌های نگهداری سیستم، وزن منفی اختصاص می‌دهد، اگرچه هیچ چرخه منفی وجود ندارد. کدام انتخاب الگوریتمی، دقت پاسخ را با بهترین پیچیدگی زمانی در بدترین حالت تضمین می‌کند؟

• الف) الگوریتم دایجسترا (Dijkstra) پیاده‌سازی شده با یک صف اولویت Binary Heap استاندارد.

• ب) الگوریتم دایجسترا پیاده‌سازی شده با یک آرایه خطی بدون ایندکس.

• ج) الگوریتم بلمن-فورد (Bellman-Ford) با استفاده از Relaxation تکرارشونده روی تمام یال‌ها.

• د) الگوریتم فلوید-وارشال (Floyd-Warshall) با استفاده از ماتریس برنامه‌نویسی پویا برای تمام جفت‌ها.

• ه) یک جستجوی اول سطح (BFS) استاندارد با استفاده از آرایه ردیابی و یک صف FIFO.

• و) مرتب‌سازی توپولوژیک ترکیب شده با یک چارچوب Relaxation خطی تک-مرحله‌ای.

پاسخ صحیح و توضیح:

• پاسخ صحیح: ج

• دلیل صحت: الگوریتم دایجسترا بر یک استراتژی حریصانه متکی است که فرض می‌کند وزن یال‌ها غیرمنفی است. اگر وزن‌های منفی وجود داشته باشند، این فرض کاملاً شکست می‌خورد و دایجسترا می‌تواند هزینه‌های مسیر نادرستی را برگرداند. الگوریتم بلمن-فورد تمام یال‌ها را به‌طور سیستماتیک V-1 بار ریلکس می‌کند و همین امر آن را قادر می‌سازد تا وزن‌های منفی یال‌ها را به‌درستی مدیریت کند. پیچیدگی زمانی آن O(V × E) در اینجا پذیرفته شده و کاملاً ضروری است.

• دلیل نادرستی گزینه‌های دیگر:

  • گزینه الف نادرست است: دایجسترا نمی‌تواند به‌طور قابل‌اطمینان گراف‌های با وزن منفی را پردازش کند، صرف‌نظر از بهینه‌سازی min-heap.

  • گزینه ب نادرست است: استفاده از آرایه برای دایجسترا عملکرد را باز هم پایین‌تر می‌آورد و همچنان در حل ورودی‌های منفی ناتوان است.

  • گزینه د نادرست است: فلوید-وارشال تمام جفت‌ها را در زمان O(V³) پیدا می‌کند. برای ۵,۰۰۰ راس، این یعنی ۱۲۵ میلیارد عملیات که در مقایسه با ۶۰ میلیون گام بلمن-فورد بسیار کند است.

  • گزینه ه نادرست است: BFS ساده تنها زمانی کوتاه‌ترین مسیر را می‌یابد که تمام یال‌ها دارای مقادیر یکسان و بدون وزن باشند.

  • گزینه و نادرست است: ریلکسیشن خطی روی ترتیب توپولوژیک بسیار بهینه است O(V + E)، اما فقط روی گراف‌های جهت‌دار بدون دور (DAG) کار می‌کند. مسئله می‌گوید گراف جهت‌دار است اما تضمینی نمی‌کند که بدون دور باشد.

سوال ۲: حل سربارهای هزینه استهلاکی در سناریوهای تصادم جدول هش

یک مهندس یک جدول هش سفارشی را با استفاده از Open Addressing و Linear Probing برای حل تصادم پیاده‌سازی می‌کند. ظرفیت اولیه روی ۱,۰۰۰ جایگاه تنظیم شده است. با پر شدن جدول، سیستم متوجه یک جهش شدید و غیرخطی در تأخیر جستجو می‌شود، در حالی که تابع هش انتخاب شده عناصر را به‌طور یکنواخت توزیع می‌کند. علت ساختاری این افت عملکرد چیست؟

• الف) جدول دچار Primary Clustering شده است، جایی که رشته‌های طولانی و متوالی از جایگاه‌های اشغال شده ایجاد شده و طول Probeها را افزایش می‌دهند.

• ب) قوانین Hashing جهانی دیکته می‌کنند که Open Addressing پس از عبور ظرفیت از ۵۰٪، به سرعت جستجوی O(N) سقوط می‌کند.

• ج) Linear Probing باعث Secondary Clustering می‌شود زیرا کلیدهای یکسان به مراحل توالی مشابهی هش می‌شوند.

• د) مکانیسم‌های Chaining به‌طور خودکار بلوک‌های Open Addressing را هنگام رسیدن به محدودیت حافظه بازنویسی می‌کنند.

• ه) تابع هش به دلیل گلوگاه‌های تطبیق الگوی رشته، نتوانست در زمان ثابت O(1) اجرا شود.

• و) روتین Garbage Collection سیستم‌عامل، ایندکس‌های حافظه پایین‌تر را در اولویت قرار می‌دهد و Probeهای خطی را مسدود می‌کند.

پاسخ صحیح و توضیح:

• پاسخ صحیح: الف

• دلیل صحت: Linear Probing به‌صورت متوالی برای جایگاه خالی بعدی جستجو می‌کند (i+1, i+2, ...). این الگو ذاتاً باعث ایجاد "Primary Clustering" می‌شود. با افزایش Load Factor، بلوک‌های جایگاه‌های اشغال شده بزرگتر می‌شوند. هر کلید هشی که در هر جای این کلاستر قرار بگیرد، باید کل کلاستر را طی کند تا یک فضای خالی پیدا کند یا آیتمی را بیابد، و این امر عملیات زمان ثابت O(1) را به اسکن‌های خطی هزینه‌بر O(N) تبدیل می‌کند.

• دلیل نادرستی گزینه‌های دیگر:

  • گزینه ب نادرست است: هیچ قانون ریاضی ثابتی وجود ندارد که عملکرد را دقیقاً در ۵۰٪ ظرفیت به سرعت خطی تبدیل کند، هرچند عملکرد با نزدیک شدن Load Factor به ۱.۰ به‌طور پیوسته کاهش می‌یابد.

  • گزینه ج نادرست است: Secondary Clustering زمانی رخ می‌دهد که کلیدهای مختلف دقیقاً یک توالی Probe یکسان را دنبال کنند (رایج در Quadratic Probing)، در حالی که Linear Probing از Primary Clustering رنج می‌برد.

  • گزینه د نادرست است: Chaining و Open Addressing استراتژی‌های متضاد هستند؛ یکی به‌طور خودکار در زمان اجرا به دیگری تبدیل نمی‌شود.

  • گزینه ه نادرست است: سناریو ذکر می‌کند که تابع هش عناصر را به‌طور یکنواخت توزیع می‌کند؛ گلوگاه کاملاً ناشی از مکانیسم حل تصادم است، نه زمان محاسبه هش.

  • گزینه و نادرست است: Garbage Collection حافظه را مدیریت می‌کند اما با حلقه‌های پیمایش ایندکس منطقی یک سیستم ردیابی آرایه تداخلی ندارد.

سوال ۳: فرمول‌بندی وضعیت برنامه‌نویسی پویا برای انواع مسائل کوله‌پشتی

یک توسعه‌دهنده باید مسئله‌ای را حل کند که در آن آیتم‌ها دارای وزن و ارزش خاصی هستند و یک کوله‌پشتی حداکثر ظرفیت W را دارد. اما، هر نوع آیتم می‌تواند به تعداد نامحدود انتخاب شود. توسعه‌دهنده یک آرایه وضعیت یک‌بعدی DP را تنظیم می‌کند که در آن DP[w] نشان‌دهنده حداکثر ارزش قابل دستیابی با ظرفیت w است. کدام رابطه بازگشتی انتقال وضعیت، این مدل خاص را به‌درستی مدل‌سازی می‌کند؟

• الف) DP[w] = max(DP[w], DP[w - weight[i]] + value[i]) در حالی که حلقه ظرفیت از W به پایین تا ۰ اجرا می‌شود.

• ب) DP[w] = max(DP[w], DP[w - weight[i]] + value[i]) در حالی که حلقه ظرفیت از ۰ به بالا تا W اجرا می‌شود.

• ج) DP[w] = max(DP[w - 1], DP[w - weight[i]]) + value[i] برای مجموعه‌های آیتم محدود.

• د) DP[w] = DP[w] + max(value[i], DP[w - weight[i]]) با استفاده از جستجوی تقسیم و غلبه.

• ه) DP[w] = min(DP[w], DP[W - w] + value[i]) با هدف قرار دادن فضای مرزی باقی‌مانده.

• و) DP[w] = max(DP[w], DP[w - weight[i-1]] + DP[weight[i]]) با اتکا به ضرب ماتریسی سخت‌گیرانه.

پاسخ صحیح و توضیح:

• پاسخ صحیح: ب

• دلیل صحت: این مسئله "Unbounded Knapsack Problem" (کوله‌پشتی نامحدود) را توصیف می‌کند زیرا آیتم‌ها می‌توانند به‌طور نامحدود استفاده شوند. هنگام به‌روزرسانی یک آرایه DP یک‌بعدی، اجرای حلقه ظرفیت به جلو از ۰ تا W به این معنی است که به‌روزرسانی DP[w] می‌تواند بر اساس به‌روزرسانی قبلی صورت گرفته در DP[w - weight[i]] در همان تکرار آیتم باشد. این امر به‌وضوح اجازه می‌دهد یک آیتم چندین بار انتخاب شود.

• دلیل نادرستی گزینه‌های دیگر:

  • گزینه الف نادرست است: اجرای حلقه ظرفیت به عقب از W تا ۰ تضمین می‌کند که هر آیتم حداکثر یک بار در هر سطح ظرفیت در نظر گرفته شود. این مدل "0/1 Knapsack Problem" است و از انتخاب‌های متعدد یک آیتم جلوگیری می‌کند.

  • گزینه ج نادرست است: این رابطه یک مقایسه نادرست بین ظرفیت‌های مجاور (w-1) ایجاد می‌کند و استثنائات وزن آیتم را به‌درستی محاسبه نمی‌کند.

  • گزینه د نادرست است: اضافه کردن مستقیم وضعیت پایه DP[w] به تابع max منجر به شمارش دوبرابر مقادیر شده و ریاضیات بهینه‌سازی را کاملاً باطل می‌کند.

  • گزینه ه نادرست است: هدف به حداکثر رساندن ارزش است، بنابراین استفاده از استراتژی min باعث به حداقل رساندن ارزش کل می‌شود که برعکس هدف است.

  • گزینه و نادرست است: این گزینه به ایندکس‌های دلخواه (i-1) اشاره می‌کند و محاسبات را بین ایندکس‌های وزن نامرتبط تقسیم می‌کند.

چه انتظاراتی داشته باشید

• به آزمون‌های سوالات مصاحبه خوش آمدید تا شما را برای آزمون تمرینی سوالات مصاحبه ساختار داده و الگوریتم آماده کنیم.

• شما می‌توانید هر چند بار که بخواهید در آزمون‌ها شرکت کنید.

• این یک بانک سوالات اصلی و بسیار بزرگ است.

• اگر سوالی داشته باشید، از پشتیبانی مدرسان بهره‌مند می‌شوید.

• هر سوال دارای یک توضیح دقیق است.

• با اپلیکیشن Udemy سازگار با موبایل است.

امیدواریم تا الان متقاعد شده باشید! سوالات بسیار بیشتری در داخل دوره وجود دارد.