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

DSA محلولة (الجزء 2): Linked Lists وStacks وTrees وHeaps وGraphs

DSA Solved Problems Part 2 — Lists, Stacks, Trees, Heaps, Graphs, Recursion

ثمان مسائل إضافية بـ C# تغطي linked list وmin stack وBST وheap وgraph DFS/topological sort وbacktracking، مع brute force وتحسين وتعقيد وedge cases.

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

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

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

01

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

Measurable outcomes
Basics

نكمّل الجزء الأول بالـ structures اللي ناقصة: linked list و stack و tree و heap و graph. الهدف نفسه: تفكير + brute force + تحسين + تعقيد مبرر.

  • تحل 8 مسائل على structures مختلفة بـ C#‎.
  • تشرح complexity بالعدّ (مثلاً ليه build heap = O(n) مش O(n log n) في الحالة العامة، وليه DFS = O(V+E)).
  • تحدد edge cases: قائمة فاضية، شجرة بعنصر، graph فيه cycle.
  • تتحقق من الفكرة بمقارنة بـ brute force.

تنبيه الصدق: كود C#‎ هنا Not Executed. اللي اتنفّذ نسخة Python بنفس الخوارزميات على مدخلات عشوائية.

02

الـ pointers والأشجار والـ graphs في رسمة

Linked list reversal and LRU structure
Basics
Reverse stepprevcurrnextsave next → curr.next = prev → prev = curr → curr = nextLRU cachemap: key → nodek1k2k3headmost recent ← … → least recent (evict)
Reversal moves three pointers one step at a time; LRU = hash map pointing into a doubly linked list
03

1 · Reverse Linked List + Detect Cycle — Easy/Medium

Linked list
Practical

Reverse: محتاج 3 مؤشرات (prev, cur, next). كل node بيتزار مرة: O(n) وقت، O(1) مساحة. Cycle: brute force: خزّن الـ nodes في HashSet (O(n) مساحة). التحسين: Floyd — مؤشر بطيء (خطوة) وسريع (خطوتين)؛ لو في cycle هيتقابلوا لأن السريع بيقفل المسافة بينهم بمقدار 1 كل خطوة. O(n) وقت، O(1) مساحة.

C#LinkedListProblems.cs
public class ListNode { public int Val; public ListNode? Next; public ListNode(int v) => Val = v; }

public static ListNode? Reverse(ListNode? head)
{
    ListNode? prev = null, cur = head;
    while (cur != null)
    {
        var next = cur.Next;     // احفظ التالي قبل ما تكسر الرابط
        cur.Next = prev;
        prev = cur; cur = next;
    }
    return prev;
}

public static bool HasCycle(ListNode? head)
{
    ListNode? slow = head, fast = head;
    while (fast?.Next != null)
    {
        slow = slow!.Next; fast = fast.Next.Next;
        if (ReferenceEquals(slow, fast)) return true;
    }
    return false;
}

Edge cases: قائمة فاضية، node واحد، cycle يشاور على نفسه.

04

2 · Min Stack — Medium

Stack design
Practical

المسألة: stack بيدعم Push/Pop/Top/GetMin كلها O(1). Brute force: GetMin بمسح كل العناصر = O(n). التحسين: stack تاني (أو زوج) بيحتفظ بالـ minimum الحالي عند كل مستوى. كل عملية O(1)، مساحة إضافية O(n).

C#MinStack.cs
public class MinStack
{
    private readonly Stack<(int val, int min)> _s = new();
    public void Push(int x) => _s.Push((x, _s.Count == 0 ? x : Math.Min(x, _s.Peek().min)));
    public int Pop() => _s.Pop().val;                       // InvalidOperationException لو فاضي
    public int Top() => _s.Peek().val;
    public int GetMin() => _s.Peek().min;
}
05

3 · Validate BST + Level Order — Medium

Trees
Practical

Validate BST: الخطأ الشائع: مقارنة الـ node بأولاده المباشرين فقط. القاعدة: كل node لازم يكون ضمن مدى (min, max) موروث من الأجداد. O(n) وقت، O(h) مساحة (عمق الـ recursion). تحذير: الـ recursion العميقة على شجرة منحرفة (n = مئات الآلاف) ممكن تعمل stack overflow؛ بدّلها بـ stack صريح لو لازم.

C#TreeProblems.cs
public class TreeNode { public int Val; public TreeNode? Left, Right; public TreeNode(int v) => Val = v; }

public static bool IsValidBst(TreeNode? n, long min = long.MinValue, long max = long.MaxValue)
{
    if (n == null) return true;
    if (n.Val <= min || n.Val >= max) return false;       // long عشان int.MinValue كقيمة صحيحة
    return IsValidBst(n.Left, min, n.Val) && IsValidBst(n.Right, n.Val, max);
}

public static IList<IList<int>> LevelOrder(TreeNode? root)
{
    var res = new List<IList<int>>();
    if (root == null) return res;
    var q = new Queue<TreeNode>(); q.Enqueue(root);
    while (q.Count > 0)
    {
        int size = q.Count; var level = new List<int>(size);
        for (int i = 0; i < size; i++)
        {
            var n = q.Dequeue(); level.Add(n.Val);
            if (n.Left != null) q.Enqueue(n.Left);
            if (n.Right != null) q.Enqueue(n.Right);
        }
        res.Add(level);
    }
    return res;
}
06

4 · Kth Largest (Heap) — Medium

Heap
Practical

Brute force: رتّب كله O(n log n) وخد العنصر k. التحسين: min-heap حجمه k: كل عنصر جديد أكبر من الجذر بيستبدله. كل عملية heap = O(log k) فالإجمالي O(n log k) وقت، O(k) مساحة. مفيد جدًا لما n ضخم (stream) و k صغير.

C#KthLargest.cs
public static int KthLargest(int[] nums, int k)
{
    if (k < 1 || k > nums.Length) throw new ArgumentOutOfRangeException(nameof(k));
    var heap = new PriorityQueue<int, int>();          // min-heap: العنصر الأصغر أولاً
    foreach (var x in nums)
    {
        if (heap.Count < k) heap.Enqueue(x, x);
        else if (x > heap.Peek()) { heap.Dequeue(); heap.Enqueue(x, x); }
    }
    return heap.Peek();
}
07

5 · Number of Islands (Graph DFS/BFS) — Medium

Graph traversal on a grid
Practical

كل خلية '1' هي node، والجيران الأربعة edges. بنعد الـ connected components: لكل '1' لسه ما اتزارتش نزوّر كل الجزيرة ونعلّمها. كل خلية بتتزار مرة والجيران 4 ثابتة: O(R·C) وقت. Brute force لا يفيد هنا (الحل الطبيعي هو الـ traversal). نستخدم stack صريح بدل recursion لتجنب overflow.

C#Islands.cs
public static int NumIslands(char[][] grid)
{
    if (grid.Length == 0) return 0;
    int R = grid.Length, C = grid[0].Length, count = 0;
    var dirs = new (int, int)[] { (1, 0), (-1, 0), (0, 1), (0, -1) };
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
        {
            if (grid[r][c] != '1') continue;
            count++;
            var st = new Stack<(int, int)>(); st.Push((r, c)); grid[r][c] = '0';   // علّم عند الإدخال
            while (st.Count > 0)
            {
                var (cr, cc) = st.Pop();
                foreach (var (dr, dc) in dirs)
                {
                    int nr = cr + dr, nc = cc + dc;
                    if (nr >= 0 && nc >= 0 && nr < R && nc < C && grid[nr][nc] == '1') { grid[nr][nc] = '0'; st.Push((nr, nc)); }
                }
            }
        }
    return count;
}

ملاحظة: الحل بيعدّل الـ input. لو ممنوع، استخدم bool[,] seen (مساحة O(R·C)).

08

6 · Course Schedule (Topological Sort) — Medium

Graph: cycle detection
Practical

المسألة: n مقررات ومتطلبات سابقة؛ هل ممكن تخلصهم كلهم؟ يعني: هل الـ directed graph من غير cycle؟ Kahn's algorithm: احسب in-degree، ابدأ بالـ nodes اللي in-degree = 0، شيلهم وقلل in-degree للجيران. لو عدد اللي اتشالوا = n يبقى مفيش cycle. O(V+E) وقت و O(V+E) مساحة.

C#CourseSchedule.cs
public static bool CanFinish(int n, int[][] prereqs)      // prereq = [course, mustTakeFirst]
{
    var adj = new List<int>[n]; for (int i = 0; i < n; i++) adj[i] = new();
    var indeg = new int[n];
    foreach (var p in prereqs) { adj[p[1]].Add(p[0]); indeg[p[0]]++; }
    var q = new Queue<int>(); for (int i = 0; i < n; i++) if (indeg[i] == 0) q.Enqueue(i);
    int done = 0;
    while (q.Count > 0)
    {
        int u = q.Dequeue(); done++;
        foreach (var v in adj[u]) if (--indeg[v] == 0) q.Enqueue(v);
    }
    return done == n;
}
09

7 · Subsets (Backtracking/Recursion) — Medium

Backtracking
Practical

لكل عنصر قرارين: ندخله أو لأ → 2ⁿ subset. ده أسي بطبيعة المسألة (حجم الخرج نفسه 2ⁿ)، فمفيش حل أسرع من O(n·2ⁿ) (النسخ). Backtracking: ندخل عنصر، نكمل، نشيله (undo) ونكمل بدونه. أهم نقطة: لما نضيف النتيجة لازم ننسخ القائمة الحالية.

C#Subsets.cs
public static IList<IList<int>> Subsets(int[] nums)
{
    var res = new List<IList<int>>(); var cur = new List<int>();
    void Go(int i)
    {
        if (i == nums.Length) { res.Add(new List<int>(cur)); return; }   // انسخ! مش تضيف المرجع
        cur.Add(nums[i]); Go(i + 1);        // choose
        cur.RemoveAt(cur.Count - 1); Go(i + 1);   // un-choose ثم تخطّى
    }
    Go(0);
    return res;
}
10

8 · LRU Cache (Hash Map + Doubly Linked List) — Medium

Design
Practical

المطلوب Get/Put بـ O(1). Dictionary للوصول السريع + linked list مزدوجة لترتيب الاستخدام (الأحدث في الأول). عند الـ Get ننقل الـ node للأول؛ عند تجاوز السعة نحذف آخر node. في ‎.NET استخدم LinkedList<T> مع LinkedListNode للحذف O(1).

C#LruCache.cs
public class LruCache<TK, TV> where TK : notnull
{
    private readonly int _cap;
    private readonly Dictionary<TK, LinkedListNode<(TK key, TV val)>> _map = new();
    private readonly LinkedList<(TK key, TV val)> _order = new();     // First = most recently used
    public LruCache(int capacity) { if (capacity < 1) throw new ArgumentOutOfRangeException(nameof(capacity)); _cap = capacity; }

    public bool TryGet(TK key, out TV value)
    {
        if (_map.TryGetValue(key, out var node)) { _order.Remove(node); _order.AddFirst(node); value = node.Value.val; return true; }
        value = default!; return false;
    }

    public void Put(TK key, TV value)
    {
        if (_map.TryGetValue(key, out var node)) { _order.Remove(node); }
        else if (_map.Count == _cap) { var last = _order.Last!; _map.Remove(last.Value.key); _order.RemoveLast(); }
        _map[key] = _order.AddFirst((key, value));
    }
}

ملاحظة: الكلاس ده مش thread-safe. في تطبيق ويب متعدد الـ threads لف الوصول بـ lock أو استخدم MemoryCache/IMemoryCache الجاهز.

11

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

The reasoning path behind each solution
Deep dive

نفس منهج الجزء الأول: إشارة ← نمط ← brute force ← نقطة الاختناق ← هيكل البيانات المناسب ← invariant ← edge cases. هنا المسائل فيها pointers وأشجار و graphs، فالرسم على الورق (أو الـ whiteboard) جزء من الحل مش رفاهية.

1 · Reverse Linked List + Detect Cycle

  1. Reverse: كل node محتاج يشاور على اللي قبله بدل اللي بعده. لو عكست next هتفقد الطريق لباقي القائمة ← احفظ next في متغير قبل ما تعكس. تلات pointers: prev، curr، next.
  2. الـ invariant: «من head لـ prev معكوس، ومن curr لآخر القائمة لسه زي ما هو».
  3. Cycle: brute force = HashSet للـ nodes اللي شفتها O(n) مساحة. المحاور بيطلب O(1) ← Floyd: slow خطوة، fast خطوتين. لو فيه دايرة، fast هيلحق slow (المسافة بينهم بتقل واحدة كل خطوة جوه الدايرة)، ولو مفيش fast هيوصل null.
  4. Edge cases: قائمة فاضية، node واحد، node بيشاور على نفسه.

2 · Min Stack: «افتكر الـ min في كل لحظة»

  1. الـ min الحالي ممكن يتشال بـ pop، ووقتها محتاج الـ min اللي قبله — يعني الـ min «تاريخ» مش قيمة واحدة.
  2. الفكرة: stack تاني (أو tuple مع كل عنصر) فيه الـ min لحد العنصر ده. push: min(x, currentMin). pop: الاتنين مع بعض.
  3. كل العمليات O(1)، والمساحة O(n). تحسين: الـ min stack ياخد العنصر بس لما يكون ≤ الـ min الحالي (انتبه للتكرار: ≤ مش <).

3 · Validate BST + Level Order

  1. الفخ: مقارنة كل node بأولاده المباشرين بس مش كفاية — node في الـ subtree اليمين لازم يكون أكبر من كل الأجداد اللي هو على يمينهم.
  2. الحل: مرّر حدود (min, max) نازلة: الشمال بياخد (min, node.val)، اليمين (node.val, max). أو inorder traversal لازم يطلع مرتب تصاعدي.
  3. استخدم long أو nullable للحدود عشان قيم زي int.MinValue.
  4. Level order: «طبقة طبقة» = BFS بـ queue؛ خد count = queue.Count في بداية كل level وعالجهم بس.

4 · Kth Largest: ليه min-heap بحجم k؟

  1. Sort كله O(n log n) — شغال، قوله الأول.
  2. محتاج أكبر k بس. min-heap بحجم k: الـ top هو أصغر واحد فيهم = الـ kth largest. أي عنصر أكبر منه يدخل ويطرده.
  3. O(n log k) — أحسن بكتير لما k صغير، ومناسب للـ streams (مش محتاج كل البيانات في الذاكرة).
  4. بديل: Quickselect متوسط O(n) بس أسوأ حالة O(n²) وبيعدل المصفوفة — اذكره كـ trade-off.

5 · Number of Islands

  1. «مجموعات متصلة» في grid = connected components ← كل ما تلاقي 1 مش متزار، ابدأ DFS/BFS يعلّم الجزيرة كلها، وزوّد العداد.
  2. كل خلية بتتزار مرة ← O(R×C).
  3. DFS recursive على grid كبير (10⁶ خلية) ممكن يعمل stack overflow ← BFS أو DFS بـ stack صريح.
  4. Follow-up شائع: الجزر بتتضاف ديناميكيًا ← Union-Find (disjoint set).

6 · Course Schedule (Topological Sort)

  1. «متطلبات قبل» = directed graph. «ينفع نخلص كل الكورسات؟» = هل فيه cycle؟
  2. Kahn's algorithm: احسب in-degree، ابدأ بكل اللي in-degree = 0، وكل ما تشيل node قلل in-degree جيرانه. لو عدد اللي اتشالوا < n ← فيه cycle.
  3. O(V + E). نفس الفكرة في الحياة الحقيقية: ترتيب migrations، build dependencies، خطوات workflow في الـ agents.

7 · Subsets (Backtracking)

  1. لكل عنصر قرارين: آخده أو لأ ← 2ⁿ نتيجة. مفيش أسرع من حجم الناتج نفسه، فالسؤال إزاي تولدهم بنضافة.
  2. Backtracking: اختار ← نزّل recursion ← تراجع عن الاختيار (remove). الـ «تراجع» هو اللي بيخلي list واحدة تكفي.
  3. انسخ الـ path لما تضيفه للنتيجة (new List<int>(path)) — إضافة نفس الـ reference أشهر bug.
  4. مع تكرار في الـ input: رتّب واتجاهل نفس القيمة في نفس المستوى.

8 · LRU Cache

  1. المطلوب get و put في O(1)، والطرد للأقدم استخدامًا.
  2. Lookup O(1) ← hash map. ترتيب الاستخدام مع نقل أي عنصر للأول في O(1) ← doubly linked list (تقدر تشيل node من النص لو معاك reference ليه).
  3. الـ map بيشاور على الـ nodes. get: انقل للأول. put: لو موجود حدّث وانقل، لو جديد ضيف في الأول ولو الحجم زاد اشيل الآخر (ومن الـ map كمان).
  4. Sentinel head/tail nodes بتلغي حالات null. وفي ‎.NET الإنتاجي: MemoryCache بـ size limits، لكن الإنترفيو عايز يشوفك تبنيه.
12

إزاي تتكلم وانت بتحل: سكريبت 45 دقيقة

Communicating during a coding interview
Practical
الدقيقةانت بتعمل إيهجملة نموذجية
0–5توضيح المسألة والحدود وأمثلة«الـ graph ممكن يبقى فيه cycles؟ الـ nodes بأرقام من 0 لـ n−1؟»
5–10brute force بتعقيده«أبسط حل O(n²)؛ مع n = 10⁵ مش هيكفي، فهدور على O(n log n)»
10–15الفكرة المحسنة + الـ invariant«هستخدم min-heap بحجم k؛ الـ top دايمًا الـ kth largest لحد دلوقتي»
15–35الكود بأسماء واضحة«هعمل helper للـ neighbors عشان الحدود تبقى في مكان واحد»
35–42trace على مثال + edge cases«خليني أجرب الـ input الفاضي والـ node الواحد»
42–45التعقيد النهائي وتحسينات«O(V+E) وقت؛ لو الـ graph ضخم ممكن نعمل BFS بـ iterative عشان الـ stack»

المحاور بيقيّم طريقة تفكيرك وتواصلك بنفس وزن الكود الصح. الصمت 10 دقايق ثم كود صح أضعف من تفكير مسموع وصل لحل شبه كامل.

13

تحقق منطق الخوارزميات (Python mirror) مقابل brute force

Executed cross-check
Deep dive
Pythoncross_check_2.pyExecuted ✓
import heapq, itertools, random
from collections import OrderedDict, deque

random.seed(11)

# --- Floyd cycle detection vs visited-set
def make_list(n, cycle_to):
    nxt = {i: i + 1 for i in range(n - 1)}
    if n and cycle_to is not None: nxt[n - 1] = cycle_to
    return nxt
def floyd(nxt, n):
    if n == 0: return False
    slow = fast = 0
    while fast in nxt and nxt[fast] in nxt:
        slow, fast = nxt[slow], nxt[nxt[fast]]
        if slow == fast: return True
    return False
def brute_cycle(nxt, n):
    seen, cur = set(), 0
    while cur is not None and n:
        if cur in seen: return True
        seen.add(cur); cur = nxt.get(cur)
    return False

# --- Min stack vs recompute-min
class MinStack:
    def __init__(self): self.s = []
    def push(self, x): self.s.append((x, min(x, self.s[-1][1]) if self.s else x))
    def pop(self): return self.s.pop()[0]
    def get_min(self): return self.s[-1][1]

# --- BST validation: range check vs inorder strictly increasing
def valid_bst(t, lo=float("-inf"), hi=float("inf")):
    if t is None: return True
    v, l, r = t
    return lo < v < hi and valid_bst(l, lo, v) and valid_bst(r, v, hi)
def inorder(t):
    return [] if t is None else inorder(t[1]) + [t[0]] + inorder(t[2])
def rand_tree(depth):
    if depth == 0 or random.random() < 0.25: return None
    return (random.randint(0, 9), rand_tree(depth - 1), rand_tree(depth - 1))

# --- Kth largest heap vs sort
def kth_heap(nums, k):
    h = []
    for x in nums:
        if len(h) < k: heapq.heappush(h, x)
        elif x > h[0]: heapq.heapreplace(h, x)
    return h[0]

# --- islands DFS vs union-find
def islands(grid):
    g = [row[:] for row in grid]; R, C = len(g), len(g[0]); cnt = 0
    for r in range(R):
        for c in range(C):
            if g[r][c] == 1:
                cnt += 1; st = [(r, c)]; g[r][c] = 0
                while st:
                    cr, cc = st.pop()
                    for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                        nr, nc = cr + dr, cc + dc
                        if 0 <= nr < R and 0 <= nc < C and g[nr][nc] == 1: g[nr][nc] = 0; st.append((nr, nc))
    return cnt
def islands_uf(grid):
    R, C = len(grid), len(grid[0]); p = list(range(R * C))
    def f(x):
        while p[x] != x: p[x] = p[p[x]]; x = p[x]
        return x
    for r in range(R):
        for c in range(C):
            if grid[r][c]:
                for dr, dc in ((1,0),(0,1)):
                    nr, nc = r + dr, c + dc
                    if nr < R and nc < C and grid[nr][nc]: p[f(r*C+c)] = f(nr*C+nc)
    return len({f(r*C+c) for r in range(R) for c in range(C) if grid[r][c]})

# --- course schedule Kahn vs DFS colouring
def kahn(n, pre):
    adj = [[] for _ in range(n)]; indeg = [0]*n
    for a, b in pre: adj[b].append(a); indeg[a] += 1
    q = deque(i for i in range(n) if indeg[i] == 0); done = 0
    while q:
        u = q.popleft(); done += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return done == n
def dfs_acyclic(n, pre):
    adj = [[] for _ in range(n)]
    for a, b in pre: adj[b].append(a)
    state = [0]*n
    def go(u):
        state[u] = 1
        for v in adj[u]:
            if state[v] == 1 or (state[v] == 0 and not go(v)): return False
        state[u] = 2; return True
    return all(state[i] == 2 or go(i) for i in range(n))

# --- subsets count and uniqueness
def subsets(nums):
    res, cur = [], []
    def go(i):
        if i == len(nums): res.append(cur[:]); return
        cur.append(nums[i]); go(i + 1); cur.pop(); go(i + 1)
    go(0); return res

# --- LRU vs OrderedDict reference
class LRU:
    def __init__(self, cap): self.cap, self.d = cap, OrderedDict()
    def get(self, k):
        if k not in self.d: return None
        self.d.move_to_end(k, last=False); return self.d[k]
    def put(self, k, v):
        if k in self.d: self.d.move_to_end(k, last=False)
        elif len(self.d) == self.cap: self.d.popitem(last=True)
        self.d[k] = v; self.d.move_to_end(k, last=False)

counts = dict.fromkeys(["cycle", "min_stack", "bst", "kth_largest", "islands", "course_schedule", "subsets", "lru"], 0)
for _ in range(300):
    n = random.randint(0, 8); cyc = random.choice([None] + list(range(max(n, 1))))
    nxt = make_list(n, cyc if n else None)
    assert floyd(nxt, n) == brute_cycle(nxt, n); counts["cycle"] += 1

    ms, ref = MinStack(), []
    for _ in range(12):
        if ref and random.random() < 0.4: assert ms.pop() == ref.pop()
        else: x = random.randint(-5, 5); ms.push(x); ref.append(x)
        if ref: assert ms.get_min() == min(ref)
    counts["min_stack"] += 1

    t = rand_tree(4); io = inorder(t)
    assert valid_bst(t) == all(a < b for a, b in zip(io, io[1:])); counts["bst"] += 1

    nums = [random.randint(-9, 9) for _ in range(random.randint(1, 10))]; k = random.randint(1, len(nums))
    assert kth_heap(nums, k) == sorted(nums, reverse=True)[k - 1]; counts["kth_largest"] += 1

    g = [[random.randint(0, 1) for _ in range(5)] for _ in range(5)]
    assert islands(g) == islands_uf(g); counts["islands"] += 1

    nc = random.randint(1, 6); pre = [(random.randrange(nc), random.randrange(nc)) for _ in range(random.randint(0, 7))]
    assert kahn(nc, pre) == dfs_acyclic(nc, pre); counts["course_schedule"] += 1

    s = subsets(list(range(random.randint(0, 6))))
    assert len(s) == 2 ** len({x for sub in s for x in sub} | set()) or True
    m = random.randint(0, 6); s = subsets(list(range(m)))
    assert len(s) == 2 ** m and len({tuple(x) for x in s}) == 2 ** m; counts["subsets"] += 1

    lru, ref = LRU(3), OrderedDict()
    for _ in range(20):
        key = random.randint(0, 5)
        if random.random() < 0.5:
            got = lru.get(key)
            if key in ref: ref.move_to_end(key, last=False)
            assert got == ref.get(key)
        else:
            lru.put(key, key * 10)
            if key in ref: ref.move_to_end(key, last=False)
            elif len(ref) == 3: ref.popitem(last=True)
            ref[key] = key * 10; ref.move_to_end(key, last=False)
    counts["lru"] += 1
print("all cross-checks passed:")
for k, v in counts.items(): print(f"  {k:16s} {v} random cases")
ConsoleOutput — captured from a real run
all cross-checks passed:
  cycle            300 random cases
  min_stack        300 random cases
  bst              300 random cases
  kth_largest      300 random cases
  islands          300 random cases
  course_schedule  300 random cases
  subsets          300 random cases
  lru              300 random cases

ملاحظة: اختبار الـ LRU هنا بيقارن النسخة المكتوبة يدويًا بنفس المنطق على OrderedDict (reference ثاني بنفس الفكرة)، يعني بيثبت اتساق الـ implementation مش صحة الفكرة من مصدر مستقل.

14

أخطاء شائعة

Common mistakes
Pitfalls
  • نسيان حفظ next قبل عكس الرابط.
  • مقارنة BST بالأبناء المباشرين فقط بدل المدى.
  • إضافة نفس مرجع القائمة للنتيجة في backtracking بدل نسخة.
  • تعليم visited وقت الـ pop بدل الـ push فتتكرر عناصر في الـ stack/queue.
  • recursion عميقة بدون وعي بـ stack overflow.
  • ادّعاء O(1) لـ LRU بدون Dictionary + node references.
15

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

Practice with worked solutions
Practical
1 (Easy): Merge two sorted linked lists

الحل: node وهمي (dummy) + مؤشر tail؛ قارن رأسي القائمتين واربط الأصغر وحرّك. في الآخر اربط الباقي. O(n+m) وقت، O(1) مساحة. الـ dummy بيلغي حالة خاصة للـ head.

2 (Easy): Max depth of a binary tree — recursion مقابل BFS

الحل: recursion: 1 + max(depth(left), depth(right))، O(n) وقت، O(h) مساحة. BFS: عدد المستويات في level-order. اختار BFS لو الشجرة عميقة جدًا (تجنب overflow).

3 (Intermediate): Top K frequent words باستخدام heap — اشرح التعقيد

الحل: عدّ بـ Dictionary O(n)، بعدين min-heap حجمه k على (التكرار، الكلمة): O(u log k) حيث u عدد الكلمات المميزة. مقارنة بالترتيب الكامل O(u log u). مهم: حدد قاعدة كسر التعادل (alphabetical) صراحة.

4 (Intermediate): Clone Graph — إزاي تتجنب loop لا نهائي؟

الحل: Dictionary من الـ node الأصلي للنسخة. قبل ما تنسخ node شوف لو اتنسخ؛ ده بيكسر الـ cycles. DFS أو BFS، O(V+E).

5 (Challenging): Word Ladder (أقصر سلسلة) — اختار الخوارزمية وبرّر

الحل: الكلمات nodes، وبينهم edge لو بيختلفوا في حرف واحد؛ كل edge تكلفتها 1 فـ BFS بيضمن الأقصر. التحسين: لتوليد الجيران استخدم patterns زي h*t في Dictionary بدل مقارنة كل زوج (O(N²·L)) → O(N·L²). BFS ثنائي الاتجاه بيقلل المساحة المستكشفة عمليًا.

16

Mini Project: مكتبة Collections مع اختبارات

Mini project
Practical

اعمل class library Structures فيها MinStack و LruCache و TrieNode، ومشروع xUnit. لكل structure: اختبارات حدية، واختبار عشوائي بـ seed ثابت مقابل نسخة reference (زي List/Dictionary). معيار النجاح: dotnet test أخضر، وتعليقات complexity مبررة، وبنشمارك بسيط (Stopwatch) يوضح فرق LRU الـ O(1) عن نسخة O(n).

17

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

Interview questions
Basics
ليه Floyd cycle detection بيلاقي الـ cycle؟
لو في cycle فالمؤشر السريع بيدخل الـ cycle ويبقى بينه وبين البطيء مسافة بتتناقص بواحد كل خطوة (سرعتهم الفرق = 1)، فلازم يتقابلوا في أقل من طول الـ cycle خطوات.
ليه build heap من مصفوفة O(n) مش O(n log n)؟
لأن معظم الـ nodes قريبة من الـ leaves وتكلفة sift-down بتتناسب مع ارتفاعها: المجموع Σ(n/2^(h+1))·h = O(n). لكن إدخال n عنصر واحد واحد = O(n log n).
DFS مقابل BFS في graph؟
BFS لأقصر مسار في graph غير موزون، DFS لاستكشاف مسارات/cycle detection/topological sort. التعقيد الزمني الاتنين O(V+E)، والمساحة تختلف (عرض مقابل عمق).
إزاي تنفذ LRU بـ O(1)؟
Dictionary يشاور على nodes في doubly linked list مرتبة بالاستخدام؛ الـ Get ينقل الـ node للأول، والـ eviction يحذف آخر node.
إيه عيب recursion في الـ production؟
stack overflow على المدخلات العميقة (والـ process بيقع في ‎.NET ومش ممكن تمسكه بـ try/catch)، فنستخدم stack صريح لما العمق مش مضمون.
(أصعب) Topological sort: إيه اللي بيحصل لو في cycle؟
الـ Kahn هيخلص قبل ما يشيل كل الـ nodes (done < n) لأن nodes الـ cycle ماوصلش in-degree بتاعها لصفر؛ فمفيش ترتيب صالح.
↗

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

References & further reading

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

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

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