Software Engineer Encyclopedia
0%
Domain 01 · Computer Science & Programming Fundamentals · Pillar

DSA محلولة بالتفصيل: من Easy لـ Medium بـ C#

DSA Solved Problems — Easy to Medium in C#

ثمانية مسائل أساسية (hash table، stack، binary search، two pointers، sliding window، BFS، DP، intervals) من brute force لحل محسّن مع شرح Big O وedge cases.

  • Foundation
  • ~15 min read
  • 18 sections
  • 8 code examples
  • 1 diagrams
  • 6 questions
  • Priority L2 · Essential
  • C# 14 / .NET 10 للحلول (Not Executed) · Python 3 للتحقق من منطق الخوارزميات (Executed)

المتطلبات قبل ما تبدأ

مفيش متطلبات — ده أول الطريق. يكفي إنك كتبت كود بأي لغة قبل كده.

01

هنطلع من الدرس بإيه؟

Measurable outcomes
Basics

الهدف إنك تتعلم طريقة تفكير مش حفظ حلول: تفهم المسألة، تكتب brute force صحيح، تحدد الجزء المتكرر اللي بيضيّع وقت، وتختار data structure أو pattern يحذفه، وبعدين تشرح الـ Big O بالسبب.

  • تحل 8 مسائل من patterns مختلفة بـ C#‎.
  • تحسب time و space complexity بالعد مش بالحفظ.
  • تحدد edge cases قبل ما تكتب الكود.
  • تتأكد من صحة الحل بمقارنته بـ brute force على مدخلات عشوائية.

المتطلبات: Data Structures & Algorithms (النظرية). الدرس ده هو الجانب التطبيقي.

02

المنهج: 5 خطوات قبل أي كود

A repeatable method
Basics
  1. افهم: إيه المدخلات والمخرجات؟ هل فيه تكرار؟ سالب؟ فاضي؟
  2. أمثلة: جرّب مثال صغير على الورق.
  3. Brute force: اكتب أبسط حل صحيح وحدد تعقيده.
  4. التحسين: فين العمل المتكرر؟ هل data structure تحذفه؟
  5. تحقق: edge cases ومقارنة بالـ brute force.

Big O بالعد: لو عندك loop من 1 لـ n وجواه loop من 1 لـ n → n×n عملية = O(n²). لو الـ loop بتقسم المدى على 2 كل مرة → عدد الدورات = log₂ n (لأن 2^k = n). لو بتخزن n عنصر في hash table → space O(n). الأرقام مش «سحر»: كل واحد جاي من عدّ العمليات.

03

الأنماط في رسمة: Two pointers و Sliding window و BFS

Three core patterns at a glance
Basics
Two pointersL →← Rdrop the side that cannot improve the answerSliding window[left … right]grow right; shrink left while invalidBFS ringsSd=1d=2Each pattern keeps an invariant; say it out loud before you code:"the window never contains a repeated char", "every cell in the queue is at distance d or d+1".
Two pointers shrink from both ends; a sliding window grows right and shrinks left; BFS expands in rings of equal distance

الرسمة دي ملخص بصري للأنماط اللي هتتكرر في المسائل الجاية. لما تقرأ مسألة، اسأل نفسك: أنهي شكل فيهم بيوصف حركة البحث؟

04

1 · Two Sum (Hash Table) — Easy

Two Sum
Practical

المسألة: مصفوفة nums وهدف target؛ رجّع index عنصرين مجموعهم = target (يفترض وجود حل واحد). Brute force: جرّب كل زوج: n(n−1)/2 مقارنة = O(n²) وقت، O(1) مساحة. التحسين: لكل عنصر x، المطلوب target−x. لو خزّنت العناصر اللي عدّيت عليها في Dictionary (قيمة → index)، البحث عن المكمّل بيبقى O(1) متوسط: مرور واحد = O(n) وقت، O(n) مساحة (نبادل مساحة بوقت).

C#TwoSum.cs
public static int[] TwoSum(int[] nums, int target)
{
    var seen = new Dictionary<int, int>();            // value -> index
    for (int i = 0; i < nums.Length; i++)
    {
        int need = target - nums[i];
        if (seen.TryGetValue(need, out int j)) return new[] { j, i };
        seen[nums[i]] = i;                              // بنضيف بعد الفحص: عشان ما نستخدمش نفس العنصر مرتين
    }
    return Array.Empty<int>();                         // مفيش حل
}

Edge cases: تكرار القيم ([3,3] و target 6: بنضيف بعد الفحص فبيشتغل)، سالب، مصفوفة فاضية. Trace لـ [2,7,11,15] و target 9: i=0 need=7 (مش موجود) نخزن 2→0؛ i=1 need=2 موجود عند 0 → [0,1].

05

2 · Valid Parentheses (Stack) — Easy

Valid Parentheses
Practical

المسألة: نص فيه ()[]{}؛ هل الأقواس متوازنة ومقفولة بالترتيب الصح؟ الملاحظة: آخر قوس اتفتح لازم يكون أول واحد يتقفل (LIFO) → Stack. Brute force: امسح الأزواج المتجاورة () [] {} بشكل متكرر لحد ما النص ما يتغيرش: كل مسح O(n) وممكن n/2 مرة = O(n²). التحسين: مرور واحد: O(n) وقت، O(n) مساحة (أسوأ حالة كلها أقواس فتح).

C#ValidParentheses.cs
public static bool IsValid(string s)
{
    var stack = new Stack<char>();
    foreach (char c in s)
    {
        if (c is '(' or '[' or '{') stack.Push(c);
        else
        {
            if (stack.Count == 0) return false;          // قفل من غير فتح
            char open = stack.Pop();
            if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
        }
    }
    return stack.Count == 0;                              // لازم ما يفضلش أقواس مفتوحة
}

Edge cases: نص فاضي (true)، "(" (false بسبب الـ Count)، ")(" (false).

06

3 · Binary Search — Easy

Binary Search
Practical

المسألة: مصفوفة مرتبة وقيمة؛ رجّع الـ index أو −1. Brute force: مسح خطي O(n). التحسين: قارن بالمنتصف وارمِ نصف المدى: بعد k خطوة المدى n/2^k، ويقف لما يوصل 1 → k ≈ log₂ n، فـ O(log n) وقت و O(1) مساحة. مثال: n = 1,000,000 → حوالي 20 مقارنة.

C#BinarySearch.cs
public static int Search(int[] a, int target)
{
    int lo = 0, hi = a.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;                    // مش (lo+hi)/2 عشان تتجنب overflow
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

Edge cases: مصفوفة فاضية (الـ loop ما بتشتغلش)، عنصر واحد، الهدف أصغر/أكبر من كل العناصر. الخطأ الشائع: lo < hi بدل <= فتفوّت عنصر.

07

4 · Container With Most Water (Two Pointers) — Medium

Two pointers
Practical

المسألة: أعمدة بارتفاعات h؛ اختار عمودين بحيث المساحة بينهم (العرض × الأقصر) أكبر ما يمكن. Brute force: كل زوج = O(n²). التحسين: ابدأ بأوسع زوج (أول وآخر عمود). المساحة محكومة بالأقصر؛ تحريك الأطول لجوه بيقلل العرض ومش هيزود الارتفاع (لسه محكوم بالأقصر) فمفيش فايدة. لازم نحرّك المؤشر على الأقصر أملاً في عمود أطول. كل خطوة بتتخلص من عمود → n−1 خطوة: O(n) وقت، O(1) مساحة.

C#MaxWater.cs
public static int MaxArea(int[] h)
{
    int l = 0, r = h.Length - 1, best = 0;
    while (l < r)
    {
        best = Math.Max(best, (r - l) * Math.Min(h[l], h[r]));
        if (h[l] < h[r]) l++; else r--;                  // حرّك الأقصر
    }
    return best;
}
08

5 · Longest Substring Without Repeating (Sliding Window) — Medium

Sliding window
Practical

المسألة: أطول substring من غير حروف متكررة. Brute force: كل substring وفحص التكرار: O(n³) (أو O(n²) لو بنوقف عند أول تكرار). التحسين: نافذة [left, right] بنوسّعها يمين، ولو الحرف الجديد موجود جوه النافذة بنخلي left يعدي آخر ظهور له. كل مؤشر بيمشي للأمام بس: O(n) وقت، O(min(n, k)) مساحة (k حجم الـ alphabet).

C#LongestUnique.cs
public static int LengthOfLongestSubstring(string s)
{
    var last = new Dictionary<char, int>();           // char -> آخر index
    int left = 0, best = 0;
    for (int right = 0; right < s.Length; right++)
    {
        if (last.TryGetValue(s[right], out int prev) && prev >= left) left = prev + 1;
        last[s[right]] = right;
        best = Math.Max(best, right - left + 1);
    }
    return best;
}

الشرط prev >= left مهم: ممكن الحرف يكون ظهر قبل بداية النافذة الحالية فمايتحسبش تكرار.

09

6 · Shortest Path in a Grid (BFS) — Medium

BFS
Practical

المسألة: شبكة 0/1 (1 = حاجز)؛ أقصر مسار من (0,0) لآخر خلية بحركات 4 اتجاهات. ليه BFS؟ لأن كل حركة تكلفتها 1، فالـ BFS بيزور الخلايا بترتيب المسافة، وأول مرة بيوصل للهدف تبقى هي الأقصر. DFS مش بيضمن الأقصر. Brute force: استكشاف كل المسارات الممكنة (أسي). BFS: كل خلية تتزار مرة واحدة × 4 جيران: O(R·C) وقت، O(R·C) مساحة للـ queue و visited.

C#GridBfs.cs
public static int ShortestPath(int[][] g)
{
    int R = g.Length, C = g[0].Length;
    if (g[0][0] == 1 || g[R - 1][C - 1] == 1) return -1;
    var q = new Queue<(int r, int c, int d)>();
    var seen = new bool[R, C];
    q.Enqueue((0, 0, 1)); seen[0, 0] = true;               // المسافة = عدد الخلايا في المسار
    int[] dr = { 1, -1, 0, 0 }, dc = { 0, 0, 1, -1 };
    while (q.Count > 0)
    {
        var (r, c, d) = q.Dequeue();
        if (r == R - 1 && c == C - 1) return d;
        for (int k = 0; k < 4; k++)
        {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nc < 0 || nr >= R || nc >= C || g[nr][nc] == 1 || seen[nr, nc]) continue;
            seen[nr, nc] = true;                          // علّم وقت الـ enqueue مش الـ dequeue عشان ما تتكررش
            q.Enqueue((nr, nc, d + 1));
        }
    }
    return -1;
}

Edge cases: شبكة 1×1 (المسافة 1)، البداية أو النهاية حاجز، مفيش مسار.

10

7 · Coin Change (Basic DP) — Medium

Dynamic programming
Practical

المسألة: أقل عدد عملات لتكوين مبلغ amount (أو −1). Greedy بيفشل: للعملات {1,3,4} والمبلغ 6، الـ greedy يختار 4+1+1 (3 عملات) لكن الأفضل 3+3 (2). Brute force: recursion بتجرب كل عملة لكل مبلغ فرعي → أسي لأن نفس المبلغ الفرعي بيتحسب مرات كتير. DP: dp[a] = أقل عدد عملات للمبلغ a. dp[a] = 1 + min(dp[a − coin]) على كل العملات. عدد الحالات = amount، وكل حالة بتجرب k عملة: O(amount × k) وقت، O(amount) مساحة.

C#CoinChange.cs
public static int CoinChange(int[] coins, int amount)
{
    var dp = new int[amount + 1];
    Array.Fill(dp, amount + 1);                           // "لانهاية" أكبر من أي إجابة ممكنة
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        foreach (int c in coins)
            if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
    return dp[amount] > amount ? -1 : dp[amount];
}
11

8 · Merge Intervals (Sorting) — Medium

Sorting + sweep
Practical

المسألة: دمج الفترات المتداخلة. Brute force: قارن كل فترة بكل فترة وكرر لحد الثبات: O(n²) أو أسوأ. التحسين: رتّب بالبداية (O(n log n))، وبعدين مرور واحد: لو بداية الفترة الحالية ≤ نهاية آخر فترة مدموجة ندمجهم، وإلا نبدأ فترة جديدة. الوقت الكلي محكوم بالترتيب O(n log n)، والمساحة O(n) للنتيجة.

C#MergeIntervals.cs
public static int[][] Merge(int[][] intervals)
{
    if (intervals.Length == 0) return Array.Empty<int[]>();
    var sorted = intervals.OrderBy(i => i[0]).ToArray();
    var result = new List<int[]>{ new[] { sorted[0][0], sorted[0][1] } };
    foreach (var cur in sorted.Skip(1))
    {
        var last = result[^1];
        if (cur[0] <= last[1]) last[1] = Math.Max(last[1], cur[1]);   // تداخل (أو تلامس)
        else result.Add(new[] { cur[0], cur[1] });
    }
    return result.ToArray();
}
12

إزاي وصلنا للحل؟ مسار التفكير لكل مسألة

The reasoning path behind each solution
Deep dive

الحفظ مش هيفيدك في الإنترفيو: المسألة هتيجي بشكل مختلف. اللي بينفع هو إنك تعرف الإشارات في نص المسألة اللي بتوديك لنمط معين، وتعرف تمشي من الـ brute force للحل المحسّن بخطوات منطقية. لكل مسألة من الثمانية فوق، ده المسار اللي المفروض تقوله بصوت عالي.

الإشارة في المسألةالنمط اللي بتفكر فيه أول حاجة
«زوج/مكمّل/شفته قبل كده؟»Hash map (قيمة → index أو عدد)
أقواس، «آخر حاجة اتفتحت»، undoStack
مصفوفة مرتبة، «أصغر قيمة تحقق شرط»Binary search (على الـ index أو على الإجابة)
مصفوفة، طرفين، «أقصى/أقل مسافة أو مساحة»Two pointers
«أطول/أقصر substring/subarray متصل بشرط»Sliding window
«أقل عدد خطوات» على grid/graph بدون أوزانBFS
«عدد طرق/أقل تكلفة» + اختيارات بتتكررDynamic programming
فترات (start, end)، تداخلSort بالبداية ثم مرور واحد

1 · Two Sum: من «جرّب كل الأزواج» لـ «افتكر اللي شفته»

  1. Brute force وتكلفته: زوجين متداخلين = O(n²). مع n = 10⁵ ده 5×10⁹ عملية — مرفوض.
  2. إيه اللي بيتكرر؟ لكل عنصر بنسأل نفس السؤال: «هل المكمّل موجود قبلي؟». السؤال «موجود؟» = lookup.
  3. أسرع lookup: hash set/map = O(1) متوسط. ومحتاجين الـ index مش القيمة بس ← map.
  4. الـ invariant: قبل ما نعالج i، الـ map فيها كل العناصر من 0 لـ i−1. عشان كده بنفحص قبل ما نضيف (ما نستخدمش العنصر مع نفسه).
  5. بديل يستاهل يتقال: لو المصفوفة مرتبة أو مسموح نرتب ونرجّع القيم مش الـ indices، two pointers بـ O(n log n) و O(1) مساحة إضافية.

2 · Valid Parentheses: «آخر واحد اتفتح لازم أول واحد يتقفل»

  1. جرّب بإيدك على ([)]: العد لوحده (عدد الفتح = عدد القفل) بيقول صح، وده غلط. يبقى الترتيب مهم.
  2. «آخر مفتوح أول مقفول» = LIFO = stack.
  3. القواعد: فتح ← push. قفل ← لازم الـ stack مش فاضي والـ top هو المقابل، وإلا false. في الآخر الـ stack لازم يبقى فاضي.
  4. Edge cases تقولها قبل ما المحاور يسأل: نص فاضي (true)، أول حرف قفل، فتح بس من غير قفل.
  5. التعقيد: O(n) وقت، O(n) مساحة في أسوأ حالة (كله فتح).

3 · Binary Search: الـ invariant قبل الكود

  1. «مرتبة» = إشارة قوية. كل مقارنة بتشيل نص الاحتمالات ← O(log n).
  2. أغلب الأخطاء في الحدود. اختار شكل واحد والتزم بيه: [lo, hi] مقفولة من الناحيتين ← while (lo <= hi)، و hi = mid − 1 / lo = mid + 1.
  3. الـ invariant: «لو الهدف موجود، فهو جوه [lo, hi]». كل خطوة لازم تحافظ عليه.
  4. mid = lo + (hi − lo) / 2 يتجنب overflow في لغات بـ int ثابت الحجم.
  5. التعميم المهم: «أصغر x يحقق شرط monotonic» (أقل سعة شاحنة تشحن في D أيام) = binary search على الإجابة نفسها مش على مصفوفة.

4 · Container With Most Water: ليه نحرّك المؤشر الأقصر؟

  1. Brute force: كل زوج O(n²). المساحة = min(h[i], h[j]) × (j − i).
  2. ابدأ بأوسع عرض: i = 0، j = n−1. أي حركة هتقلل العرض، فالأمل الوحيد إن الارتفاع الأصغر يزيد.
  3. الإثبات بالكلام: لو h[i] < h[j]، أي container بيستخدم i مع أي j' < j هيبقى عرضه أقل وارتفاعه ≤ h[i] — يعني مش ممكن يغلب الحالي. فـ i «خلص» ونقدر نرميه بأمان. ده اللي بيبرر الـ greedy.
  4. كل خطوة بترمي عنصر واحد ← O(n).
  5. المحاور غالبًا بيسأل «ليه مش بنحرك الأطول؟» — الإثبات فوق هو الإجابة.

5 · Longest Substring Without Repeating: نافذة بتتمد وتنكمش

  1. «substring متصل» + «أطول بشرط» = sliding window.
  2. Brute force: كل substring O(n²) وفحص التكرار O(n) ← O(n³).
  3. النافذة [left, right] فيها حروف مش متكررة (الـ invariant). مد right؛ لو الحرف الجديد موجود في النافذة، حرّك left لبعد آخر ظهور ليه.
  4. map من الحرف لآخر index بيخلي القفزة O(1) بدل ما نحرك left واحدة واحدة. انتبه: left = max(left, last[c] + 1) — آخر ظهور ممكن يكون قبل النافذة الحالية.
  5. كل index بيدخل ويخرج مرة ← O(n). المساحة O(حجم الأبجدية).

6 · Shortest Path in a Grid: ليه BFS مش DFS؟

  1. «أقل عدد خطوات» وكل خطوة بنفس التكلفة ← BFS بيزور الخلايا بترتيب المسافة: أول مرة توصل للهدف = أقصر مسار.
  2. DFS ممكن يلاقي مسار طويل الأول، ولازم يستكشف كله عشان يتأكد ← أبطأ وأصعب.
  3. علّم الخلية visited لما تدخلها الـ queue مش لما تطلعها — وإلا نفس الخلية تتضاف كذا مرة.
  4. لو الخطوات بأوزان مختلفة ← Dijkstra (priority queue). لو أوزان 0/1 بس ← 0-1 BFS بـ deque.
  5. O(R×C) وقت ومساحة.

7 · Coin Change: من recursion لـ DP

  1. عرّف المسألة الصغيرة: f(a) = أقل عدد عملات لعمل المبلغ a.
  2. العلاقة: f(a) = 1 + min(f(a − c)) لكل عملة c ≤ a، و f(0) = 0.
  3. Recursion مباشر بيحسب نفس f(a) آلاف المرات (subproblems متداخلة) ← memoization أو جدول من 0 لـ amount.
  4. ليه greedy (أكبر عملة الأول) غلط؟ عملات {1, 3, 4} ومبلغ 6: greedy = 4+1+1 (3 عملات)، الأمثل 3+3 (2). مثال مضاد واحد كفاية تقوله.
  5. O(amount × عدد العملات) وقت، O(amount) مساحة. التفاصيل والأنماط الأوسع في درس Dynamic Programming.

8 · Merge Intervals: الترتيب بيحوّل المسألة لمرور واحد

  1. من غير ترتيب، كل interval محتاج يتقارن بالكل ← O(n²).
  2. بعد الترتيب بالبداية، أي interval ممكن يتداخل مع آخر واحد في النتيجة بس — مش مع اللي قبله.
  3. القاعدة: لو start ≤ last.end ← last.end = max(last.end, end)، وإلا ضيف جديد. الـ max مهم: [1,10] ثم [2,3].
  4. O(n log n) بسبب الترتيب. اسأل: هل الحدود المتلامسة ([1,2] و [2,3]) تعتبر تداخل؟ سؤال توضيح بيكسبك نقط.
13

اقرأ الـ constraints: هي بتقولك التعقيد المطلوب

Constraints tell you the target complexity
Basics
n تقريبًاالتعقيد المقبول (≈10⁸ عملية/ثانية)غالبًا
≤ 20O(2ⁿ)، O(n!)backtracking، كل الـ subsets
≤ 500O(n³)DP على فترات، Floyd–Warshall
≤ 5,000O(n²)DP ثنائي الأبعاد، كل الأزواج
≤ 10⁵ – 10⁶O(n log n) أو O(n)sorting، heap، two pointers، hashing، segment tree
≥ 10⁹O(log n) أو O(1)binary search على الإجابة، رياضة

دي أول حاجة تعملها قبل ما تفكر في الحل: لو n = 10⁵ وفكرتك O(n²)، ابحث عن حاجة أحسن قبل ما تكتب. الشرح الأعمق للـ Big-O والـ amortized analysis في Range Queries & Complexity.

14

تحقق من منطق الخوارزميات: brute force مقابل المحسّن

Executed cross-check (Python mirror)
Deep dive

مفيش ‎.NET SDK في بيئة بناء الموسوعة، فحلول C#‎ فوق Not Executed. اللي اتنفّذ فعلاً هو نسخة Python بنفس الخوارزميات ومقارنتها بالـ brute force على آلاف المدخلات العشوائية. ده بيثبت صحة الفكرة (مش كود C#‎ نفسه): لو طلعت اختلاف في حلك بـ C#‎، قارنه بالمنطق ده.

Pythoncross_check.pyExecuted ✓
import random
from collections import deque

def two_sum_fast(a, t):
    seen = {}
    for i, x in enumerate(a):
        if t - x in seen: return (seen[t - x], i)
        seen[x] = i
def two_sum_brute(a, t):
    return next(((i, j) for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] + a[j] == t), None)

def max_area_fast(h):
    l, r, best = 0, len(h) - 1, 0
    while l < r:
        best = max(best, (r - l) * min(h[l], h[r]))
        if h[l] < h[r]: l += 1
        else: r -= 1
    return best
def max_area_brute(h):
    return max((j - i) * min(h[i], h[j]) for i in range(len(h)) for j in range(i + 1, len(h)))

def longest_fast(s):
    last, left, best = {}, 0, 0
    for r, ch in enumerate(s):
        if ch in last and last[ch] >= left: left = last[ch] + 1
        last[ch] = r; best = max(best, r - left + 1)
    return best
def longest_brute(s):
    return max((j - i for i in range(len(s) + 1) for j in range(i, len(s) + 1) if len(set(s[i:j])) == j - i), default=0)

def coin_fast(coins, amt):
    dp = [amt + 1] * (amt + 1); dp[0] = 0
    for a in range(1, amt + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]: dp[a] = dp[a - c] + 1
    return -1 if dp[amt] > amt else dp[amt]
def coin_brute(coins, amt):
    best = [None]
    def go(rem, used):
        if rem == 0: best[0] = used if best[0] is None else min(best[0], used); return
        for c in coins:
            if c <= rem and (best[0] is None or used + 1 < best[0]): go(rem - c, used + 1)
    go(amt, 0); return -1 if best[0] is None else best[0]

def merge_fast(iv):
    out = []
    for s, e in sorted(iv):
        if out and s <= out[-1][1]: out[-1][1] = max(out[-1][1], e)
        else: out.append([s, e])
    return out
def merge_brute(iv):
    pts = set()
    for s, e in iv: pts.update(range(s * 2, e * 2 + 1))     # نقط بنص وحدة عشان التلامس
    res, cur = [], None
    for p in sorted(pts):
        if cur and p == cur[1] + 1: cur[1] = p
        elif cur is None or p > cur[1] + 1:
            if cur: res.append(cur)
            cur = [p, p]
    if cur: res.append(cur)
    return [[a // 2, b // 2] for a, b in res]

def bfs(g):
    R, C = len(g), len(g[0])
    if g[0][0] or g[R-1][C-1]: return -1
    q, seen = deque([(0, 0, 1)]), {(0, 0)}
    while q:
        r, c, d = q.popleft()
        if (r, c) == (R-1, C-1): return d
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            n = (r+dr, c+dc)
            if 0 <= n[0] < R and 0 <= n[1] < C and not g[n[0]][n[1]] and n not in seen:
                seen.add(n); q.append((n[0], n[1], d+1))
    return -1
def dfs_all_paths_min(g):                                      # brute force: كل المسارات البسيطة
    R, C = len(g), len(g[0]); best = [-1]
    def go(r, c, vis, d):
        if (r, c) == (R-1, C-1):
            best[0] = d if best[0] == -1 else min(best[0], d); return
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r+dr, c+dc
            if 0 <= nr < R and 0 <= nc < C and not g[nr][nc] and (nr, nc) not in vis:
                go(nr, nc, vis | {(nr, nc)}, d+1)
    if g[0][0] or g[R-1][C-1]: return -1
    go(0, 0, {(0, 0)}, 1); return best[0]

random.seed(7)
checks = {"two_sum": 0, "max_area": 0, "longest_unique": 0, "coin_change": 0, "merge_intervals": 0, "grid_bfs": 0}
for _ in range(400):
    a = [random.randint(-5, 9) for _ in range(random.randint(2, 9))]; t = random.randint(-5, 15)
    f, b = two_sum_fast(a, t), two_sum_brute(a, t)
    assert (f is None) == (b is None) and (f is None or a[f[0]] + a[f[1]] == t); checks["two_sum"] += 1
    h = [random.randint(0, 9) for _ in range(random.randint(2, 10))]
    assert max_area_fast(h) == max_area_brute(h); checks["max_area"] += 1
    s = "".join(random.choice("abcd") for _ in range(random.randint(0, 9)))
    assert longest_fast(s) == longest_brute(s); checks["longest_unique"] += 1
    coins = random.sample([1, 2, 3, 4, 5, 7], random.randint(1, 3)); amt = random.randint(0, 14)
    assert coin_fast(coins, amt) == coin_brute(coins, amt); checks["coin_change"] += 1
    iv = [[x, x + random.randint(0, 4)] for x in [random.randint(0, 12) for _ in range(random.randint(0, 6))]]
    assert merge_fast(iv) == merge_brute(iv); checks["merge_intervals"] += 1
    g = [[1 if random.random() < 0.3 else 0 for _ in range(4)] for _ in range(4)]
    assert bfs(g) == dfs_all_paths_min(g); checks["grid_bfs"] += 1
print("all cross-checks passed (fast == brute force):")
for k, v in checks.items(): print(f"  {k:16s} {v} random cases")
print("greedy counter-example: coins [1,3,4], amount 6 ->", coin_fast([1, 3, 4], 6), "coins (greedy would use 3)")
ConsoleOutput — captured from a real run
all cross-checks passed (fast == brute force):
  two_sum          400 random cases
  max_area         400 random cases
  longest_unique   400 random cases
  coin_change      400 random cases
  merge_intervals  400 random cases
  grid_bfs         400 random cases
greedy counter-example: coins [1,3,4], amount 6 -> 2 coins (greedy would use 3)
15

أخطاء شائعة

Common mistakes
Pitfalls
  • كتابة الحل المحسّن قبل ما يكون عندك brute force صحيح تقارن بيه.
  • تحريك المؤشر الغلط في two pointers (لازم الأقصر).
  • تعليم visited وقت الـ dequeue في BFS فتدخل نفس الخلية الـ queue أكتر من مرة.
  • استخدام greedy لمسائل العملات بدون إثبات.
  • نسيان الحالات الحدية: فاضي، عنصر واحد، تكرار، سالب.
  • ذكر Big O من غير تبرير: «O(n)» لوحدها مش إجابة.
16

خمس تمارين إضافية محلولة

Practice with worked solutions
Practical
1 (Easy): Contains Duplicate — حدد الحل والتعقيد

الحل: brute force: قارن كل زوج O(n²). الأفضل: HashSet<int>؛ لو Add رجّع false يبقى تكرار. O(n) وقت، O(n) مساحة. بديل بدون مساحة إضافية: رتّب O(n log n) وقارن المتجاورين.

2 (Easy): اعكس linked list — اشرح الـ pointers

الحل: محتاج 3 مؤشرات: prev=null, cur=head؛ في كل خطوة: احفظ next=cur.next، اعكس cur.next=prev، حرّك prev=cur; cur=next. O(n) وقت و O(1) مساحة. الخطأ الشائع إنك تنسى تحفظ next قبل ما تكسر الرابط.

3 (Intermediate): أقصى مجموع subarray (Kadane)

الحل: cur = max(x, cur + x) و best = max(best, cur). التفكير: لو المجموع التراكمي بقى سالب، البدء من جديد أحسن. O(n) وقت و O(1) مساحة. Edge: كل العناصر سالبة → الإجابة أكبر عنصر (ابدأ بـ best = a[0] مش 0).

4 (Intermediate): Level-order traversal لشجرة

الحل: BFS بـ Queue: في كل مستوى خد q.Count الحالي واعمل dequeue لعددهم وضيف أولادهم. O(n) وقت، O(w) مساحة (w أكبر عرض). الشجرة الفاضية ترجّع قائمة فاضية.

5 (Challenging): Top K Frequent Elements — قارن بين طريقتين

الحل: (1) عدّ بـ Dictionary O(n) ثم رتّب الـ keys بالتكرار O(u log u) (u عدد القيم المميزة). (2) عدّ ثم Min-Heap حجمه k: كل عنصر O(log k) فالإجمالي O(n + u log k)، أحسن لما k صغير. (3) bucket sort: مصفوفة بكتس حسب التكرار (التكرار ≤ n) فتبقى O(n). الاختيار حسب k و n؛ اشرح الـ trade-off في الإنترفيو.

17

Mini Project: مكتبة اختبارات خوارزميات

Mini project
Practical

اعمل solution C#‎ فيها class library Algos ومشروع xUnit. نفّذ المسائل الثمانية، واكتب لكل واحدة: اختبارات للـ edge cases، واختبار property-based بسيط يقارن الحل المحسّن بالـ brute force على 1000 مدخل عشوائي (Random بـ seed ثابت). معيار النجاح: dotnet test أخضر، وكل class فيه تعليق بالـ Time/Space complexity ومبرراتهم.

18

أسئلة إنترفيو

Interview questions
Basics
ليه HashMap بيحسّن Two Sum؟ وإيه التكلفة؟
بيحوّل البحث عن المكمّل من O(n) لـ O(1) متوسط، فالمجموع O(n) بدل O(n²). التكلفة O(n) مساحة، وأسوأ حالة لـ hash collisions نظريًا أبطأ.
إمتى BFS ومتى DFS؟
BFS لأقصر مسار في graph غير موزون (أو level-order). DFS لاستكشاف كل الاحتمالات أو مسائل backtracking أو topological sort، ومساحته O(عمق).
ليه lo + (hi - lo) / 2؟
يتجنب integer overflow لما lo و hi كبار؛ (lo+hi) ممكن يتجاوز حدود int.
إيه الفرق بين Greedy و DP؟
Greedy بيختار الأفضل محليًا ولا يراجع (بيحتاج إثبات صحة). DP بيحل مسائل فرعية متداخلة ويخزن نتائجها عشان يوصل للأمثل عالميًا.
ليه sliding window O(n) رغم وجود loop جوه loop أحيانًا؟
لأن كل من المؤشرين بيتحرك للأمام فقط ومجموع حركتهم ≤ 2n؛ العد بيتم على الحركات الكلية مش على شكل الـ loops.
(أصعب) اشرح ليه Merge Intervals O(n log n) مش O(n)
المرور بعد الترتيب O(n)، لكن الترتيب نفسه مقارن-based ومحكوم بـ Ω(n log n)، فالإجمالي محكوم بالترتيب.
↗

المراجع والقراءة الإضافية

References & further reading

الدرس بيشرح الفكرة نفسها؛ الروابط دي للتحقق والتعمق والرجوع لتفاصيل الـ API. (محتاجة إنترنت.)

خلصت الدرس وحليت الأسئلة؟ علّم عليه عشان يتحسب في تقدّمك.

محتويات الدرس