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

هياكل البيانات والخوارزميات

Data Structures & Algorithms

مش حفظ حلول Leetcode: ده فهم ليه List أسرع من LinkedList في الواقع، وإزاي الـ Dictionary بيدور في O(1)، ومتى تستخدم Heap أو Graph، وإزاي تحلل تعقيد أي كود بتكتبه في الـ backend.

  • Foundation
  • ~30 min read
  • 18 sections
  • 12 code examples
  • 8 diagrams
  • 10 questions
  • Priority L2 · Essential
  • .NET 10 · C# 14

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

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

مستوى التعمق المطلوب

STRONG FOUNDATIONSPrioritize common structures, complexity, and problem-solving over rare competitive-programming topics.

01

Big O: تعقيد الزمن والمساحة

Big O time and space complexity
Basics

لما بتكتب كود، السؤال مش بس «هل بيشتغل؟» لكن «هيشتغل إزاي لما الداتا تكبر؟». الـ Big O هي لغة بنوصف بيها معدل نمو عدد العمليات (أو الذاكرة) بالنسبة لحجم المدخلات n. هي مش بتقيس ثواني، بتقيس الشكل اللي الأداء بيتغير بيه.

إيه اللي بنهمله؟

  • الثوابت: 3n و 100n الاتنين O(n).
  • الحدود الصغيرة: n² + n هي O(n²).
  • ليه؟ لأن لما n تكبر الحد الأكبر هو اللي بيحكم.

Best / Average / Worst

نفس الخوارزمية ليها حالات: البحث الخطي عن عنصر ممكن يلاقيه في أول خانة (best = O(1)) أو آخر خانة أو مش موجود (worst = O(n)). في الـ production بنهتم غالباً بالـ worst/average لأن الـ SLA بيتكسر في الحالات الوحشة.

Time vs Space

Time: عدد العمليات الأساسية. Space: الذاكرة الإضافية اللي الخوارزمية بتحتاجها (من غير المدخلات نفسها). كتير بنبدّل واحدة بالتانية: نخزن في Dictionary (ذاكرة أكتر) عشان نوفر زمن.

input size n → operations O(2ⁿ) exponential (dashed)O(n²) quadraticO(n log n)O(n) linearO(log n)O(1) constant
نمو عدد العمليات مع زيادة n: الفرق بين O(n) و O(n²) بيبقى مدمر في الـ datasets الكبيرة
Complexityالاسمn = 1,000n = 1,000,000مثال
O(1)Constant11Array index, Dictionary lookup (average)
O(log n)Logarithmic~10~20Binary search, balanced tree lookup
O(n)Linear1,0001,000,000Loop over a list, List.Contains
O(n log n)Linearithmic~10,000~20,000,000Merge sort, Array.Sort
O(n²)Quadratic1,000,00010¹²Nested loops over the same data
O(2ⁿ)Exponentialتقريباً مستحيلمستحيلNaive recursive Fibonacci, subsets

إزاي تحلل كود فعلي

C#Complexity.cs — counting operations
// 1) O(1): one operation regardless of size
static int First(int[] a) => a[0];

// 2) O(n): one pass
static int Sum(int[] a)
{
    int total = 0;
    foreach (var x in a) total += x;        // n iterations
    return total;
}

// 3) O(n²): nested pass over the same data
static bool HasDuplicateSlow(int[] a)
{
    for (int i = 0; i < a.Length; i++)
        for (int j = i + 1; j < a.Length; j++)   // ~ n(n-1)/2 comparisons
            if (a[i] == a[j]) return true;
    return false;
}

// 4) O(n) time, O(n) extra space: trade memory for speed
static bool HasDuplicateFast(int[] a)
{
    var seen = new HashSet<int>();
    foreach (var x in a)
        if (!seen.Add(x)) return true;      // Add returns false if it already exists
    return false;
}

// 5) O(log n): the search space is halved each step
static int CountHalvings(int n)
{
    int steps = 0;
    while (n > 1) { n /= 2; steps++; }
    return steps;                           // log2(n)
}

الشرح

  1. First: عملية واحدة. مهما كبر المصفوفة التكلفة ثابتة.
  2. Sum: الـ foreach بيعدي على كل عنصر مرة واحدة: n عملية جمع ⇒ O(n). مساحة إضافية O(1) (متغير واحد).
  3. HasDuplicateSlow: الـ loop الداخلي بيشتغل (n-1) ثم (n-2) … ⇒ مجموعها n(n-1)/2 وده O(n²). مساحة إضافية O(1).
  4. HasDuplicateFast: مرور واحد، وكل Add في HashSet متوسطه O(1) ⇒ O(n) زمن. التكلفة إن الـ set ممكن يخزن لحد n عنصر ⇒ O(n) مساحة.
  5. CountHalvings: كل دورة بتقسم n على 2 ⇒ عدد الدورات log₂ n.

نفس المشكلة (هل فيه تكرار؟) اتحلت مرتين: واحدة O(n²) / O(1) ومرة O(n) / O(n). ده Space-Time Trade-off في أبسط صوره.

Amortized Analysis

بعض العمليات غالباً سريعة وأحياناً غالية جداً. List<T>.Add مثال: لما الـ capacity تخلص بيتعمل array جديد بضعف الحجم وبيتنسخ فيه كل العناصر (O(n)). لكن ده بيحصل نادراً، فلو حسبت المتوسط على n عملية Add يطلع O(1) amortized. لو عارف العدد مقدماً استخدم new List<int>(capacity) وتجنب النسخ كلها.

الـ Big O في الـ backend

لما endpoint بيتأخر، غالباً السبب O(n²) مخفي: loop فيه list.Contains(...) أو FirstOrDefault(...) جوه loop تانية. أو N+1 queries على الـ database (n استعلام بدل واحد). تحليل الـ Big O بيخليك تشوف ده قبل ما يوصل Production.

02

Arrays والـ List<T>

Arrays
Deep dive

الـ Array هو أبسط وأسرع هيكل: مساحة متصلة (contiguous) في الذاكرة لعناصر من نفس النوع. عشان كده الوصول لأي عنصر بالـ index هو عملية حسابية بسيطة: العنوان = عنوان_البداية + index × حجم_العنصر، فهو O(1).

int[] a = [10, 20, 30, 40, 50] (كل عنصر 4 bytes) 1020304050 a[0]a[1]a[2]a[3]a[4] 0x10000x10040x10080x100C0x1010 Insert at index 2 → shift 30,40,50 right (O(n)) a[i] = base + i × 4 → one multiplication (O(1))
الـ Array متصل في الذاكرة، فالـ index بيتحول لعنوان بحسبة واحدة. الإدراج في النص بيزحزح كل اللي بعده
OperationArray (T[])List<T>
Index read/writeO(1)O(1)
Append at endغير ممكن (الحجم ثابت)O(1) amortized
Insert / Remove in the middleO(n) (يدوي)O(n)
Search unsortedO(n)O(n)
Search sortedO(log n) binary searchO(log n) BinarySearch
C#Arrays.cs — arrays, List growth, Span
int[] a = [10, 20, 30, 40, 50];             // collection expression (C# 12+)
Console.WriteLine(a[2]);                     // 30  -> O(1)

// Insert 25 at index 2 in a raw array: build a new one (O(n))
int[] b = new int[a.Length + 1];
Array.Copy(a, 0, b, 0, 2);                   // copy [10,20]
b[2] = 25;
Array.Copy(a, 2, b, 3, a.Length - 2);        // copy [30,40,50] shifted by one
// b = [10,20,25,30,40,50]

// List<T> manages the array for you
var list = new List<int>();
int lastCapacity = -1;
for (int i = 0; i < 20; i++)
{
    list.Add(i);
    if (list.Capacity != lastCapacity)
    {
        lastCapacity = list.Capacity;
        Console.WriteLine($"Count={list.Count} Capacity={list.Capacity}");
    }
}
// Typical output: Capacity grows 4 -> 8 -> 16 -> 32 (doubling)

// Span<T>: a view over part of an array — NO copy
Span<int> slice = a.AsSpan(1, 3);            // [20,30,40]
slice[0] = 99;                               // writes through to a
Console.WriteLine(string.Join(",", a));      // 10,99,30,40,50

الشرح وتتبع التنفيذ

  1. a[2] بيتحول لـ base + 2×4 فمفيش loop ⇒ O(1).
  2. الإدراج في array عادي محتاج array جديد + نسخ جزئين: كل العناصر اللي بعد نقطة الإدراج بتتحرك ⇒ O(n).
  3. الـ List<int> بيبدأ بـ capacity = 0، أول Add بيخليها 4 ثم 8 ثم 16… (تضاعف). لما بيتعدى الـ capacity بيعمل array جديد وينسخ — ده الـ O(n) النادر اللي بنحسبه amortized.
  4. الـ Span<int> مش بتنسخ حاجة، هي «نافذة» على نفس الذاكرة، فالتعديل بيظهر في a. استخدمها لو بتعالج slices كتير وعايز تتجنب allocations.
أخطاء شائعة

(1) استخدام list.Insert(0, x) أو RemoveAt(0) في loop كبيرة ⇒ O(n²) كلها. استخدم Queue<T> أو LinkedList<T> أو اعكس الترتيب. (2) IndexOutOfRangeException من off-by-one: آخر index هو Length - 1.

03

Linked Lists

Linked lists
Deep dive

الـ Linked List كل عنصر فيها (node) بيحمل القيمة + مؤشر للي بعده (وفي الـ doubly linked كمان للي قبله). العناصر مش لازم تكون متجاورة في الذاكرة. ده بيدّيك إدراج وحذف O(1) لو عندك الـ node نفسه، لكن الوصول بالـ index O(n) لأنك لازم تمشي من البداية.

head 10 20 30 null value | next
Singly linked list: كل node بيشاور على اللي بعده، والـ tail بيشاور على null
C#SinglyLinkedList.cs — implement + reverse
public sealed class Node<T>(T value)
{
    public T Value { get; set; } = value;
    public Node<T>? Next { get; set; }
}

public sealed class SinglyLinkedList<T>
{
    private Node<T>? _head;
    private Node<T>? _tail;
    public int Count { get; private set; }

    // O(1): we keep a tail pointer
    public void AddLast(T value)
    {
        var node = new Node<T>(value);
        if (_head is null) _head = _tail = node;
        else { _tail!.Next = node; _tail = node; }
        Count++;
    }

    // O(1)
    public void AddFirst(T value)
    {
        var node = new Node<T>(value) { Next = _head };
        _head = node;
        _tail ??= node;
        Count++;
    }

    // O(n): must walk from the head
    public bool Contains(T value)
    {
        for (var cur = _head; cur is not null; cur = cur.Next)
            if (EqualityComparer<T>.Default.Equals(cur.Value, value)) return true;
        return false;
    }

    // O(n) time, O(1) space: reverse by flipping each Next pointer
    public void Reverse()
    {
        Node<T>? prev = null, cur = _head;
        _tail = _head;
        while (cur is not null)
        {
            var next = cur.Next;   // 1) remember the rest
            cur.Next = prev;       // 2) flip the pointer
            prev = cur;            // 3) advance prev
            cur = next;            // 4) advance cur
        }
        _head = prev;
    }

    public IEnumerable<T> Items()
    {
        for (var cur = _head; cur is not null; cur = cur.Next) yield return cur.Value;
    }
}

تتبع Reverse على [10 → 20 → 30]

البداية: prev=null, cur=10. next=20 ⇒ 10.Next=null ⇒ prev=10, cur=20.
next=30 ⇒ 20.Next=10 ⇒ prev=20, cur=30.
next=null ⇒ 30.Next=20 ⇒ prev=30, cur=null ⇒ الـ loop خلص.
_head = prev = 30، والنتيجة 30 → 20 → 10 → null.

الشرط المهم: لازم تحفظ next قبل ما تقلب المؤشر، وإلا ضيّعت باقي القائمة.

الحقيقة العملية: List<T> غالباً أسرع

رغم إن Linked List نظرياً أفضل في الإدراج، الـ cache locality بتخلي الـ array أسرع بمراحل: عناصر الـ array متجاورة فبتتحمل في الـ CPU cache مع بعض، لكن الـ nodes منتشرة في الـ heap وكل Next ممكن يكون cache miss، إضافة لتكلفة allocation لكل node. في ‎.NET بتستخدم LinkedList<T> فقط لو عندك الـ LinkedListNode وبتعمل إدراج/حذف كتير في النص، زي الـ LRU cache.

04

Stacks و Queues

Stacks and queues
Practical

Stack — LIFO

آخر عنصر دخل هو أول واحد يطلع (زي طبق فوق طبق). العمليات: Push / Pop / Peek كلها O(1). استخدامه: call stack، undo، parsing، DFS، التحقق من الأقواس.

Queue — FIFO

أول عنصر دخل هو أول واحد يطلع (طابور). العمليات: Enqueue / Dequeue / Peek كلها O(1) (amortized). استخدامه: job processing، message queues، BFS، rate limiting.

C#StackQueue.cs — balanced brackets and a job queue
static bool IsBalanced(string s)
{
    var stack = new Stack<char>();
    var pairs = new Dictionary<char, char> { [')'] = '(', [']'] = '[', ['}'] = '{' };

    foreach (var ch in s)
    {
        if (ch is '(' or '[' or '{') stack.Push(ch);
        else if (pairs.TryGetValue(ch, out var open))
        {
            if (stack.Count == 0 || stack.Pop() != open) return false;
        }
    }
    return stack.Count == 0;
}

Console.WriteLine(IsBalanced("{[()]}"));   // True
Console.WriteLine(IsBalanced("{[(])}"));   // False

// Queue: process jobs in arrival order
var jobs = new Queue<string>();
jobs.Enqueue("send-email");
jobs.Enqueue("resize-image");
jobs.Enqueue("generate-report");

while (jobs.TryDequeue(out var job))
    Console.WriteLine($"Processing {job}");
// send-email, resize-image, generate-report

الشرح وتتبع "{[(])}"

  1. كل قوس فتح بنعمله Push. كل قوس قفل لازم يكون مطابق لآخر قوس فتح لسه مفتوح (اللي فوق الـ stack).
  2. التتبع على {[(])}: Push {، Push [، Push (. بعدها ]: Pop ⇒ طلع ( مش [ ⇒ false فوراً.
  3. على {[()]}: كل قفل بيطابق قمة الـ stack وفي الآخر الـ stack فاضي ⇒ true. بدون الفحص الأخير stack.Count == 0 كان "((" هيعدي غلط.
  4. زمن O(n) ومساحة O(n) في الأسوأ. استخدمنا TryDequeue بدل Dequeue عشان نتجنب exception على queue فاضية.
ربط بالـ runtime

الـ Call Stack اللي بتتخزن فيه الـ method calls هو stack فعلاً. لو recursion عميقة جداً بيحصل StackOverflowException وفي ‎.NET ده مينفعش يتمسك بـ try/catch والـ process بيقفل. وفي الـ backend: الـ Channel<T> و Message Brokers هي queues متقدمة للـ producer/consumer.

05

Hash Tables و Dictionaries و Sets

Hash tables, dictionaries and sets
Deep dive

الـ Hash Table هو أهم هيكل بيانات في الـ backend. بيدّيك بحث وإدراج وحذف في O(1) متوسط عن طريق إنك بتحول الـ key لرقم (hash) يحدد المكان اللي هتدور فيه مباشرة بدل ما تمشي على كل العناصر.

key = "ali" hash GetHashCode() = 7381 % size bucket index 3 buckets[] 0 : -1 1 : -1 2 : 0 3 : 1 entries[] (hash, key, value, next) [0] "sara" → 90 next = -1 [1] "ali" → 75 next = 2 [2] "omar" → 60 next = -1 (collision chain) "ali" و "omar" وقعوا في نفس الـ bucket → chain عن طريق next
Dictionary في ‎.NET: الـ key بيتعمله hash ثم modulo على عدد الـ buckets. الـ collision بتتحل بسلسلة من الـ entries

إزاي بيشتغل (Internal Mechanics)

  1. Hashing: الـ key بيتعمله GetHashCode() فيطلع int.
  2. Bucket: الـ hash بيتحول لـ index داخل مصفوفة الـ buckets (غالباً بـ modulo على حجم أولي).
  3. Collision: أكتر من key ممكن يوصلوا لنفس الـ bucket. الـ Dictionary في ‎.NET بيحلها بـ chaining: كل entry فيها next يشاور على entry تانية في نفس الـ bucket. البحث بيمشي على السلسلة ويقارن بـ Equals.
  4. Resize: لما العناصر تتكاثر بيتم تكبير الـ buckets (تقريباً الضعف) وإعادة توزيع كل العناصر (O(n) نادراً ⇒ amortized O(1)).
  5. لو الـ hash function سيئة وكل الـ keys وقعت في bucket واحد، البحث بيتحول لـ O(n).
عقد GetHashCode و Equals

لو a.Equals(b) لازم a.GetHashCode() == b.GetHashCode(). لو كسرت العقد ده الـ Dictionary مش هيلاقي الـ key اللي حطيته. ولو استخدمت object mutable كـ key وغيرت الحقول اللي دخلت في الـ hash بعد الإدراج، الـ entry هتضيع (موجودة بس مفيش طريق توصلها). استخدم record أو struct readonly أو string/int/Guid كـ keys.

C#HashDemo.cs — two sum, frequency count, custom key
// 1) Two Sum in O(n): "have I seen the complement before?"
static int[]? TwoSum(int[] nums, int target)
{
    var indexOf = new Dictionary<int, int>();          // value -> index
    for (int i = 0; i < nums.Length; i++)
    {
        int need = target - nums[i];
        if (indexOf.TryGetValue(need, out int j)) return [j, i];
        indexOf[nums[i]] = i;
    }
    return null;
}
Console.WriteLine(string.Join(",", TwoSum([2, 7, 11, 15], 9)!));   // 0,1

// 2) Frequency count with a Dictionary
var counts = new Dictionary<char, int>();
foreach (var ch in "mississippi")
    counts[ch] = counts.GetValueOrDefault(ch) + 1;
// m:1, i:4, s:4, p:2

// 3) HashSet: uniqueness and set algebra
var a = new HashSet<int> { 1, 2, 3, 4 };
var b = new HashSet<int> { 3, 4, 5 };
a.IntersectWith(b);                                     // a = {3,4}
Console.WriteLine(a.Contains(3));                       // True  (O(1) average)

// 4) A proper composite key: record gives value-based Equals/GetHashCode
public readonly record struct CellKey(int Row, int Col);
var grid = new Dictionary<CellKey, string> { [new(0, 1)] = "wall" };
Console.WriteLine(grid.ContainsKey(new CellKey(0, 1)));  // True

الشرح

  1. TwoSum: بدل loop متداخلة O(n²)، بنسأل كل عنصر «هل مكمّلي target - x شفته قبل كده؟». الـ Dictionary بيجاوب في O(1). التتبع على [2,7,11,15] و target 9: عند 2 ⇒ need 7 مش موجود ⇒ نخزن 2→0. عند 7 ⇒ need 2 موجود في index 0 ⇒ نرجّع [0,1].
  2. Frequency: GetValueOrDefault بيرجّع 0 لو الـ key مش موجود فبنزود 1 من غير exception. ده pattern بتشوفه في كل مكان (word count, group by).
  3. HashSet: بيمنع التكرار وبيدعم عمليات المجموعات: UnionWith و IntersectWith و ExceptWith.
  4. record struct: بيولّد Equals و GetHashCode على أساس القيم، فمفتاح مركب (Row, Col) شغال صح من غير ما تكتب العقد بإيدك.
الهيكلإمتى؟
Dictionary<K,V>عايز تدور على value بالـ key بسرعة (lookup / cache / index)
HashSet<T>عايز تعرف «موجود ولا لأ» أو تشيل التكرار
SortedDictionary<K,V> / SortedSet<T>محتاج ترتيب الـ keys أو range queries (O(log n))
ConcurrentDictionary<K,V>أكتر من thread بيكتبوا في نفس الوقت (مش Dictionary العادي!)
ملحوظة مهمة

ترتيب التعداد (enumeration) في Dictionary مش مضمون. متبنيش منطق يعتمد على ترتيب الإدراج.

06

Trees و Binary Search Trees

Trees and BSTs
Deep dive

الـ Tree هيكل هرمي: root، وكل node ليها أبناء. الـ Binary Search Tree (BST) قاعدته: لكل node، كل القيم في الـ left subtree أصغر منها وكل القيم في الـ right subtree أكبر. ده بيخلي البحث زي binary search: كل خطوة بتتخلص من نص الشجرة.

3 ⇒ يمين، لقيناه في 3 خطوات بدل المرور على كل العناصر"> 8 3 10 1 6 14 4 7 left < root < right ← search(6)
C#Bst.cs — insert, search, traversals
public sealed class TreeNode(int value)
{
    public int Value { get; } = value;
    public TreeNode? Left { get; set; }
    public TreeNode? Right { get; set; }
}

public sealed class Bst
{
    private TreeNode? _root;

    public void Insert(int value) => _root = Insert(_root, value);

    private static TreeNode Insert(TreeNode? node, int value)
    {
        if (node is null) return new TreeNode(value);          // found an empty spot
        if (value < node.Value) node.Left = Insert(node.Left, value);
        else if (value > node.Value) node.Right = Insert(node.Right, value);
        return node;                                           // equal: ignore duplicate
    }

    public bool Contains(int value)
    {
        var cur = _root;
        while (cur is not null)
        {
            if (value == cur.Value) return true;
            cur = value < cur.Value ? cur.Left : cur.Right;    // discard half
        }
        return false;
    }

    // In-order (Left, Root, Right) yields values in sorted order
    public IEnumerable<int> InOrder() => InOrder(_root);
    private static IEnumerable<int> InOrder(TreeNode? n)
    {
        if (n is null) yield break;
        foreach (var x in InOrder(n.Left)) yield return x;
        yield return n.Value;
        foreach (var x in InOrder(n.Right)) yield return x;
    }

    public int Height() => Height(_root);
    private static int Height(TreeNode? n) => n is null ? 0 : 1 + Math.Max(Height(n.Left), Height(n.Right));
}

var t = new Bst();
foreach (var v in new[] { 8, 3, 10, 1, 6, 14, 4, 7 }) t.Insert(v);
Console.WriteLine(string.Join(",", t.InOrder()));   // 1,3,4,6,7,8,10,14
Console.WriteLine(t.Contains(6));                    // True

الشرح

  1. Insert بتنزل يمين أو شمال حسب المقارنة لحد ما توصل لمكان فاضي (null) وتحط فيه node جديدة. الـ recursion بترجّع الـ node في كل مستوى عشان تربط الأبناء.
  2. Contains بتنفذ نفس المنطق iteratively: كل مقارنة بتتخلص من فرع كامل.
  3. InOrder (يسار، الجذر، يمين) بتطلع القيم مرتبة — دي خاصية الـ BST.
  4. الأنواع الأخرى من الـ traversal: Pre-order (الجذر الأول، لنسخ الشجرة)، Post-order (الجذر الأخير، لحذف الشجرة)، و Level-order (BFS بـ queue).
مشكلة الـ BST غير المتوازن

لو أدخلت قيم مرتبة 1,2,3,4,5 الشجرة بتتحول لـ linked list (كلها يمين) والبحث بيبقى O(n). الحل: Self-balancing trees زي Red-Black و AVL بتعيد التوازن أوتوماتيك للحفاظ على O(log n). في ‎.NET: SortedDictionary<K,V> و SortedSet<T> مبنيين على red-black tree. وقواعد البيانات بتستخدم B-Trees (للـ indexes) لأنها بتقلل عدد قراءات الـ disk.

07

Heaps و Priority Queues

Heaps and priority queues
Practical

الـ Priority Queue هي queue بس اللي بيخرج منها أعلى أولوية مش الأقدم. بتتنفذ بـ Binary Heap: شجرة كاملة بتتخزن في array، وقاعدتها في الـ min-heap إن كل أب ≤ أبنائه، فالأصغر دايماً في الـ index 0.

1 3 2 7 5 4 array: [1, 3, 2, 7, 5, 4] index: 0 1 2 3 4 5
Min-heap مخزن في array: لأي node عند index i: الأب عند (i-1)/2، والأبناء عند 2i+1 و 2i+2
OperationCostHow
Peek (min)O(1)index 0
EnqueueO(log n)أضف في آخر الـ array ثم sift up لحد ما الـ heap property ترجع
Dequeue (min)O(log n)شيل الجذر، حط آخر عنصر مكانه، ثم sift down
Build from n itemsO(n)heapify
C#PriorityQueueDemo.cs — scheduler and top-K
// PriorityQueue<TElement, TPriority> is a MIN-heap: smallest priority comes out first
var tasks = new PriorityQueue<string, int>();
tasks.Enqueue("backup-db", 5);
tasks.Enqueue("send-alert", 1);      // most urgent
tasks.Enqueue("cleanup-logs", 9);

while (tasks.TryDequeue(out var task, out var priority))
    Console.WriteLine($"{priority}: {task}");
// 1: send-alert   5: backup-db   9: cleanup-logs

// Top-K largest numbers with a size-K min-heap: O(n log k)
static List<int> TopK(IEnumerable<int> nums, int k)
{
    var heap = new PriorityQueue<int, int>();      // element == priority
    foreach (var x in nums)
    {
        heap.Enqueue(x, x);
        if (heap.Count > k) heap.Dequeue();        // drop the smallest, keep K largest
    }
    var result = new List<int>();
    while (heap.Count > 0) result.Add(heap.Dequeue());
    result.Reverse();
    return result;
}
Console.WriteLine(string.Join(",", TopK([5, 1, 9, 3, 7, 8, 2], 3)));   // 9,8,7

الشرح

  1. الـ PriorityQueue (من ‎.NET 6) بتاخد element و priority منفصلين. الأولوية الأصغر بتخرج الأول (min-heap). لو عايز max-heap اعكس الأولوية أو مرر Comparer مقلوب.
  2. الـ Top-K: بنحافظ على heap حجمه k فقط. أي عنصر جديد بندخله وبنشيل الأصغر لو عدينا k. فالباقي هو أكبر k عناصر. كل عملية O(log k) فالإجمالي O(n log k) أحسن من ترتيب كل الـ n.
  3. تحذير: الـ PriorityQueue مش stable: عناصر بنفس الأولوية مش مضمون ترتيب خروجها.
  4. استخدامات: Dijkstra، job schedulers، merging sorted streams، median بـ heaps اتنين.
08

Graphs و BFS و DFS

Graphs, BFS and DFS
Deep dive

الـ Graph هو مجموعة nodes (vertices) بينهم edges. بيمثل أي حاجة فيها علاقات: شبكة طرق، صداقات، dependencies بين packages، أو microservices بتنادي بعض. الـ edges ممكن تكون directed (اتجاه واحد) أو undirected، weighted (لها تكلفة) أو لأ.

Adjacency List

لكل node قايمة جيرانها. المساحة O(V + E). هو التمثيل الافتراضي للـ graphs المتفرقة (sparse).

Adjacency Matrix

مصفوفة V×V. المساحة O(V²) لكن فحص «هل فيه edge بين a و b؟» هو O(1). مناسب للـ dense graphs.

A B C D E F level 0: Alevel 1: B, Clevel 2: D, Elevel 3: F
Graph بسيط (undirected). BFS بيزور المستويات تباعاً من A: A ثم (B,C) ثم (D,E) ثم F
C#GraphDemo.cs — adjacency list, BFS shortest path, DFS, cycle detection
// Build an undirected graph as an adjacency list
var graph = new Dictionary<string, List<string>>
{
    ["A"] = ["B", "C"], ["B"] = ["A", "D"], ["C"] = ["A", "E"],
    ["D"] = ["B", "E", "F"], ["E"] = ["C", "D", "F"], ["F"] = ["D", "E"]
};

// BFS: shortest path (fewest edges) in an UNWEIGHTED graph — O(V + E)
static List<string>? BfsPath(Dictionary<string, List<string>> g, string start, string goal)
{
    var parent = new Dictionary<string, string?> { [start] = null };
    var queue = new Queue<string>();
    queue.Enqueue(start);

    while (queue.Count > 0)
    {
        var cur = queue.Dequeue();
        if (cur == goal)
        {
            var path = new List<string>();
            for (string? n = goal; n is not null; n = parent[n]) path.Add(n);
            path.Reverse();
            return path;
        }
        foreach (var next in g[cur])
            if (parent.TryAdd(next, cur))        // TryAdd doubles as the "visited" check
                queue.Enqueue(next);
    }
    return null;                                 // unreachable
}
Console.WriteLine(string.Join("->", BfsPath(graph, "A", "F")!));   // A->B->D->F

// DFS (recursive): visit as deep as possible, then backtrack
static void Dfs(Dictionary<string, List<string>> g, string node, HashSet<string> visited, List<string> order)
{
    if (!visited.Add(node)) return;
    order.Add(node);
    foreach (var next in g[node]) Dfs(g, next, visited, order);
}
var order = new List<string>();
Dfs(graph, "A", [], order);
Console.WriteLine(string.Join(",", order));   // A,B,D,E,C,F

// DFS (iterative with an explicit Stack): avoids StackOverflow on huge graphs
static List<string> DfsIterative(Dictionary<string, List<string>> g, string start)
{
    var visited = new HashSet<string>();
    var stack = new Stack<string>();
    var order = new List<string>();
    stack.Push(start);
    while (stack.Count > 0)
    {
        var node = stack.Pop();
        if (!visited.Add(node)) continue;
        order.Add(node);
        foreach (var next in Enumerable.Reverse(g[node])) stack.Push(next);
    }
    return order;
}

شرح BFS وتتبعه

  1. الـ queue بتخلي الزيارة بالمستويات: كل الجيران على بُعد خطوة قبل اللي على بُعد خطوتين. عشان كده أول مرة نوصل فيها لـ goal نبقى وصلناله بأقل عدد edges.
  2. parent بيخدم غرضين: visited set (عشان منزورش node مرتين وندخل في loop لانهائي في الـ cycles)، و تتبع المسار لإعادة بناء الطريق بالرجوع من الهدف للبداية.
  3. التتبع من A إلى F: queue=[A] ⇒ visit A، أضف B,C ⇒ visit B، أضف D ⇒ visit C، أضف E ⇒ visit D، أضف F (parent[F]=D) ⇒ ... نوصل F والمسار A→B→D→F.
  4. الـ DFS بيستخدم stack (الـ call stack في النسخة recursive). الاتنين زمنهم O(V+E) ومساحتهم O(V).
BFSDFS
الهيكل المساعدQueueStack / Recursion
بيناسبأقصر مسار (unweighted)، levels، أقرب جارالكشف عن cycles، topological sort، backtracking، connected components
الذاكرةممكن تكبر (عرض الـ graph)عمق المسار (خطر stack overflow لو recursive)
في الـ backend

Dependency resolution (ترتيب بناء المشاريع في الـ solution، ترتيب الـ migrations، الـ DI circular dependency detection) كلها graph problems: الـ circular dependency اللي شفناها في درس DI هي cycle في directed graph بتتكشف بـ DFS.

09

Binary Search

Binary search
Practical

لو الداتا مرتبة، بدل ما تدور واحد واحد (O(n)) بتقارن بالعنصر اللي في النص وبتتخلص من نص الاحتمالات كل مرة ⇒ O(log n). في مليون عنصر بتحتاج ~20 مقارنة بس.

C#BinarySearch.cs — classic, lower bound, search on answer
// 1) Classic: returns the index or -1
static int BinarySearch(int[] a, int target)
{
    int lo = 0, hi = a.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;          // NOT (lo + hi) / 2 -> can overflow int
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;      // answer is in the right half
        else hi = mid - 1;                      // answer is in the left half
    }
    return -1;
}

// 2) Lower bound: first index whose value >= target (insertion point)
static int LowerBound(int[] a, int target)
{
    int lo = 0, hi = a.Length;                  // hi is EXCLUSIVE here
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 3) Binary search on the ANSWER: min capacity so that packages ship within `days`
static int MinShipCapacity(int[] weights, int days)
{
    int lo = weights.Max(), hi = weights.Sum();      // answer lies in [heaviest, total]
    while (lo < hi)
    {
        int cap = lo + (hi - lo) / 2;
        if (CanShip(weights, days, cap)) hi = cap;   // feasible -> try smaller
        else lo = cap + 1;                           // not feasible -> need bigger
    }
    return lo;

    static bool CanShip(int[] w, int days, int cap)
    {
        int used = 1, load = 0;
        foreach (var x in w)
        {
            if (load + x > cap) { used++; load = 0; }
            load += x;
        }
        return used <= days;
    }
}

int[] sorted = [1, 3, 5, 7, 9, 11];
Console.WriteLine(BinarySearch(sorted, 7));     // 3
Console.WriteLine(LowerBound(sorted, 6));       // 3  (insert 6 before 7)
Console.WriteLine(Array.BinarySearch(sorted, 4));  // negative: ~insertionIndex (here ~2 = -3)

الشرح

  1. الـ invariant: لو الهدف موجود، فهو دايماً جوه [lo, hi]. كل خطوة بتصغّر النطاق من غير ما تفقد الهدف.
  2. mid = lo + (hi - lo) / 2 يتجنب overflow لما lo+hi يعدي int.MaxValue (bug مشهور استمر سنين في مكتبات كبيرة).
  3. Lower bound بتستخدم نطاق نصف مفتوح [lo, hi)؛ لما a[mid] < target نتخطى mid، وغير كده hi = mid (mid ممكن يكون هو الإجابة).
  4. Binary search on answer: حتى لو مفيش array مرتب، لو الدالة «ممكنة؟» monotonic (لو سعة X تنفع فكل سعة أكبر تنفع) نقدر نبحث عن أقل قيمة ممكنة.
  5. Array.BinarySearch بترجّع index العنصر لو موجود، وغير كده complement bitwise (~index) للمكان اللي ينفع تدخله فيه.
أخطاء شائعة

تطبيقها على بيانات مش مرتبة (نتيجة غلط من غير error)، lo < hi بدل lo <= hi (بيفوّت العنصر الأخير)، أو lo = mid بدل mid + 1 (infinite loop). الحل: فكّر في الـ invariant وجرب على حالات: array فاضية، عنصر واحد، الهدف في الأول/الآخر/غير موجود.

10

Sorting Algorithms

Sorting algorithms
Deep dive

في الواقع هتستخدم Array.Sort أو OrderBy دايماً. لكن فهم الخوارزميات بيعلمك مفاهيم عامة: divide & conquer، stability، in-place، وتحليل الـ trade-offs.

AlgorithmBestAverageWorstSpaceStableملاحظة
Bubble sortO(n)O(n²)O(n²)O(1)Yesتعليمي فقط
Insertion sortO(n)O(n²)O(n²)O(1)Yesممتاز للداتا الصغيرة / شبه المرتبة
Merge sortO(n log n)O(n log n)O(n log n)O(n)Yesثابت الأداء، خارجي (external sort)
Quick sortO(n log n)O(n log n)O(n²)O(log n)Noسريع عملياً؛ pivot سيء = أسوأ حالة
Heap sortO(n log n)O(n log n)O(n log n)O(1)Noأسوأ حالة مضمونة بدون ذاكرة

Stable يعني العناصر المتساوية بتحافظ على ترتيبها الأصلي (مهم لما بترتب بمعيار ثانوي بعد أول). وكمان لحد Comparison sort مستحيل يبقى أسرع من O(n log n) في الأسوأ.

C#Sorting.cs — merge sort, quick sort, and what .NET does
static int[] MergeSort(int[] a)
{
    if (a.Length <= 1) return a;
    int mid = a.Length / 2;
    int[] left  = MergeSort(a[..mid]);          // range slicing creates a copy
    int[] right = MergeSort(a[mid..]);
    return Merge(left, right);
}

static int[] Merge(int[] l, int[] r)
{
    var result = new int[l.Length + r.Length];
    int i = 0, j = 0, k = 0;
    while (i < l.Length && j < r.Length)
        result[k++] = l[i] <= r[j] ? l[i++] : r[j++];   // <= keeps it STABLE
    while (i < l.Length) result[k++] = l[i++];
    while (j < r.Length) result[k++] = r[j++];
    return result;
}

static void QuickSort(int[] a, int lo, int hi)
{
    if (lo >= hi) return;
    int p = Partition(a, lo, hi);
    QuickSort(a, lo, p - 1);
    QuickSort(a, p + 1, hi);
}

static int Partition(int[] a, int lo, int hi)
{
    int pivot = a[hi];                         // Lomuto scheme (simple, not the fastest)
    int i = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) { (a[i], a[j]) = (a[j], a[i]); i++; }
    (a[i], a[hi]) = (a[hi], a[i]);
    return i;
}

int[] data = [38, 27, 43, 3, 9, 82, 10];
Console.WriteLine(string.Join(",", MergeSort(data)));   // 3,9,10,27,38,43,82

// In real code:
Array.Sort(data);                                       // introsort, unstable, in-place
var people = new[] { ("Sara", 30), ("Ali", 25), ("Omar", 30) };
var sorted = people.OrderBy(p => p.Item2).ThenBy(p => p.Item1);  // LINQ OrderBy is STABLE

الشرح وتتبع Merge Sort

  1. Divide: نقسم المصفوفة نصين لحد ما نوصل لعنصر واحد (مرتب بديهياً). عمق الـ recursion = log n.
  2. Conquer/Merge: ندمج نصين مرتبين بـ مؤشرين i و j: بنختار الأصغر من الرأسين. الدمج O(n) لكل مستوى ⇒ الإجمالي O(n log n). الـ <= هي اللي بتخلي الخوارزمية stable.
  3. الـ QuickSort: Partition بتحط الـ pivot في مكانه النهائي (كل الأصغر قبله والأكبر بعده)، ثم بنرتب الجزئين. لو الـ pivot دايماً أصغر/أكبر عنصر (مصفوفة مرتبة بالفعل مع Lomuto) بيتحول لـ O(n²).
  4. في ‎.NET: Array.Sort/List.Sort بتستخدم Introsort (quicksort يتحول لـ heapsort لو العمق زاد، و insertion sort للأجزاء الصغيرة) فأسوأ حالة O(n log n) وهي غير stable. بينما OrderBy في LINQ stable.
11

Recursion

Recursion
Deep dive

الـ Recursion إن الدالة تنادي نفسها على نسخة أصغر من نفس المشكلة. كل recursion صح لازمله: Base case (حالة بتقف عندها) و Recursive case (بتقرّب للـ base case). كل نداء بياخد stack frame جديد على الـ call stack.

C#Recursion.cs — factorial, fibonacci, memoization, tree depth
// 1) Factorial: n! = n * (n-1)!
static long Factorial(int n) => n <= 1 ? 1 : n * Factorial(n - 1);   // base: n <= 1

// 2) Naive Fibonacci: O(2^n) — recomputes the same subproblems
static long FibSlow(int n) => n < 2 ? n : FibSlow(n - 1) + FibSlow(n - 2);

// 3) Memoization: remember results -> O(n) time, O(n) space
static long FibMemo(int n, Dictionary<int, long>? memo = null)
{
    memo ??= [];
    if (n < 2) return n;
    if (memo.TryGetValue(n, out var cached)) return cached;
    return memo[n] = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);
}

// 4) Iterative version: O(n) time, O(1) space, no stack risk
static long FibIter(int n)
{
    long a = 0, b = 1;
    for (int i = 0; i < n; i++) (a, b) = (b, a + b);
    return a;
}

Console.WriteLine(Factorial(5));    // 120
Console.WriteLine(FibMemo(50));     // 12586269025  (FibSlow(50) would take minutes)

تتبع Factorial(3)

Factorial(3) ⇒ محتاج 3 * Factorial(2) ⇒ بينادي.
Factorial(2) ⇒ 2 * Factorial(1) ⇒ بينادي.
Factorial(1) ⇒ base case ⇒ بيرجع 1.
الرجوع: 2 * 1 = 2 ثم 3 * 2 = 6. الـ stack وصل عمق 3 frames.
  1. FibSlow(5) بينادي FibSlow(3) مرتين FibSlow(2) تلات مرات… عدد النداءات بيتضاعف ⇒ O(2ⁿ).
  2. الـ memoization بيخزن كل fib(k) أول ما يتحسب، فكل قيمة بتتحسب مرة واحدة ⇒ O(n).
  3. النسخة الـ iterative بتحتاج متغيرين بس، ومفيش stack growth.
خطر Stack Overflow

recursion بعمق عشرات الآلاف (زي القايمة المرتبطة أو DFS على graph ضخم) ممكن تعمل StackOverflowException وده بيقفل الـ process في ‎.NET. للعمق الكبير حوّلها لـ iterative بـ Stack<T> صريح. وكمان ‎.NET مش بيضمن tail-call optimization في C#‎، فمتعتمدش عليها.

12

Two Pointers و Sliding Window

Two pointers and sliding window
Practical

دي patterns بتحول حلول O(n²) البديهية لـ O(n) من غير هياكل بيانات إضافية. الفكرة: بدل ما تفحص كل الأزواج/المجالات، بتحرك مؤشرات بناءً على معلومة تخلّيك تستبعد احتمالات كتير.

Two Pointers

مؤشرين على array مرتب (من الطرفين غالباً) أو مؤشر بطيء وسريع. بتتحرك حسب النتيجة: لو المجموع كبير نقص الأيمن، لو صغير زوّد الأيسر.

Sliding Window

نافذة [left, right] بتتمدد من اليمين وبتتقلص من الشمال للحفاظ على شرط معين، فكل عنصر بيدخل ويخرج مرة واحدة ⇒ O(n).

C#Pointers.cs — pair sum, remove duplicates, longest unique substring, max window sum
// Two pointers: does a SORTED array contain a pair summing to target? O(n), O(1)
static bool HasPair(int[] a, int target)
{
    int l = 0, r = a.Length - 1;
    while (l < r)
    {
        int sum = a[l] + a[r];
        if (sum == target) return true;
        if (sum < target) l++;     // need a bigger sum -> move the left pointer up
        else r--;                  // need a smaller sum -> move the right pointer down
    }
    return false;
}

// Slow/fast pointers: remove duplicates in-place from a sorted array
static int RemoveDuplicates(int[] a)
{
    if (a.Length == 0) return 0;
    int write = 1;                                   // next position to write
    for (int read = 1; read < a.Length; read++)
        if (a[read] != a[read - 1]) a[write++] = a[read];
    return write;                                    // new logical length
}

// Sliding window (variable size): longest substring without repeating chars
static int LongestUnique(string s)
{
    var lastSeen = new Dictionary<char, int>();
    int best = 0, left = 0;
    for (int right = 0; right < s.Length; right++)
    {
        if (lastSeen.TryGetValue(s[right], out int prev) && prev >= left)
            left = prev + 1;                         // shrink window past the duplicate
        lastSeen[s[right]] = right;
        best = Math.Max(best, right - left + 1);
    }
    return best;
}

// Sliding window (fixed size k): maximum sum of k consecutive elements
static int MaxWindowSum(int[] a, int k)
{
    int window = 0;
    for (int i = 0; i < k; i++) window += a[i];
    int best = window;
    for (int i = k; i < a.Length; i++)
    {
        window += a[i] - a[i - k];                   // add the new, remove the old
        best = Math.Max(best, window);
    }
    return best;
}

Console.WriteLine(HasPair([1, 3, 4, 6, 9], 10));        // True (1+9)
Console.WriteLine(LongestUnique("abcabcbb"));           // 3 ("abc")
Console.WriteLine(MaxWindowSum([2, 1, 5, 1, 3, 2], 3)); // 9 (5+1+3)

الشرح

  1. HasPair: لأن الـ array مرتب: لو a[l] + a[r] أصغر من الهدف، فـ a[l] مع أي عنصر ≤ a[r] هيفضل أصغر ⇒ نقدر نستبعد a[l]. نفس المنطق للعكس. ده بيبرّر تحريك المؤشر (فهو correctness argument مش تخمين).
  2. RemoveDuplicates: read بيمسح الـ array و write بيحدد أين نكتب القيمة الجديدة. القيمة بتتكتب بس لو مختلفة عن اللي قبلها.
  3. LongestUnique: lastSeen بيخزن آخر ظهور لكل حرف. لو الحرف ظهر داخل النافذة الحالية بننقل left لبعده. على "abcabcbb": النافذة abc (3) ثم لما يجي a تاني left يروح لـ 1…
  4. MaxWindowSum: بدل ما نجمع k عنصر في كل موقع (O(nk))، بنحدّث المجموع بإضافة العنصر الجديد وطرح القديم ⇒ O(n).
13

Greedy و Basic Dynamic Programming

Greedy algorithms and DP basics
Deep dive

Greedy

في كل خطوة بتاخد الاختيار الأفضل محلياً وماتبصش وراك. بتشتغل بس لو المشكلة ليها greedy-choice property (الاختيار المحلي الأمثل بيوصّل للحل الأمثل الكلي). لازم تثبت إنها صح، مش تفترض.

Dynamic Programming

للمشاكل اللي فيها subproblems متداخلة و optimal substructure: الحل الأمثل مبني من حلول أمثل لمشاكل أصغر. بنخزن حل كل subproblem مرة واحدة (memoization أو tabulation).

C#GreedyDp.cs — interval scheduling, coin change, climbing stairs, LCS
// GREEDY: max number of non-overlapping meetings. Sort by END time, take whatever fits.
static int MaxMeetings((int Start, int End)[] meetings)
{
    var sorted = meetings.OrderBy(m => m.End).ToArray();
    int count = 0, lastEnd = int.MinValue;
    foreach (var m in sorted)
        if (m.Start >= lastEnd) { count++; lastEnd = m.End; }
    return count;
}
Console.WriteLine(MaxMeetings([(1, 3), (2, 4), (3, 5), (0, 6), (5, 7)]));   // 3

// DP (tabulation): fewest coins to make `amount`. Greedy FAILS for coins {1,3,4}, amount 6.
static int CoinChange(int[] coins, int amount)
{
    int[] dp = new int[amount + 1];                 // dp[x] = min coins for amount x
    Array.Fill(dp, int.MaxValue);
    dp[0] = 0;
    for (int x = 1; x <= amount; x++)
        foreach (var c in coins)
            if (c <= x && dp[x - c] != int.MaxValue)
                dp[x] = Math.Min(dp[x], dp[x - c] + 1);
    return dp[amount] == int.MaxValue ? -1 : dp[amount];
}
Console.WriteLine(CoinChange([1, 3, 4], 6));       // 2  (3+3). Greedy would give 4+1+1 = 3 coins

// DP (space-optimized): climbing stairs, 1 or 2 steps at a time
static int ClimbStairs(int n)
{
    int prev = 1, cur = 1;
    for (int i = 2; i <= n; i++) (prev, cur) = (cur, prev + cur);
    return cur;
}

// DP on two strings: Longest Common Subsequence, O(m*n) time
static int Lcs(string a, string b)
{
    var dp = new int[a.Length + 1, b.Length + 1];
    for (int i = 1; i <= a.Length; i++)
        for (int j = 1; j <= b.Length; j++)
            dp[i, j] = a[i - 1] == b[j - 1]
                ? dp[i - 1, j - 1] + 1
                : Math.Max(dp[i - 1, j], dp[i, j - 1]);
    return dp[a.Length, b.Length];
}
Console.WriteLine(Lcs("ABCBDAB", "BDCABA"));      // 4

الشرح

  1. Meetings (Greedy): الاختيار الأمثل: الاجتماع اللي بينتهي أبكر بيسيب أكبر وقت للباقي. إثبات الصحة: أي حل أمثل ممكن نستبدل أول اجتماع فيه بالأبكر انتهاءً من غير ما نقلل العدد.
  2. Coin change: مثال بيوضح إن الـ greedy ممكن يفشل: بعملات {1,3,4} للمبلغ 6 الـ greedy بياخد 4 ثم 1+1 (3 عملات)، والأمثل 3+3 (عملتين). الـ DP بيجرب كل عملة لكل مبلغ فرعي: dp[x] = min(dp[x-c] + 1). زمن O(amount × coins).
  3. Climbing stairs: ways(n) = ways(n-1) + ways(n-2) (فيبوناتشي). لاحظ إننا بنخزن آخر قيمتين بس: space optimization.
  4. LCS: لو الحرفين متساويين نزوّد القطري، وغير كده ناخد أحسن من (تخطي حرف من a) أو (تخطي حرف من b). الجدول بيتملي صف صف.
  5. خطوات حل أي DP: (1) عرّف الـ state (إيه معنى dp[i])، (2) اكتب الـ recurrence، (3) حدد الـ base cases، (4) حدد ترتيب الملء، (5) راجع إمكانية تقليل المساحة.
14

Algorithm Correctness

Reasoning about correctness
Basics

الخوارزمية الصح مش اللي «اشتغلت على 3 أمثلة». هي اللي تقدر تبرر إنها بتدي الإجابة الصح لكل المدخلات المسموحة وإنها بتقف. الأدوات الأساسية: Loop Invariant، Termination، وEdge Cases.

Loop Invariant

شرط بيبقى صحيح قبل أول دورة، وبعد كل دورة، وفي الآخر بيوصّلك للنتيجة المطلوبة. بتثبته بالـ induction: (1) Initialization (2) Maintenance (3) Termination.

Termination

لازم في مقدار بيتناقص (زي hi - lo) ويقف عند حد معين. أغلب الـ infinite loops بتجي من إن التحديث ممكن مايغيّرش المقدار (lo = mid بدل mid + 1).

Edge Cases

فاضي، عنصر واحد، كل العناصر متساوية، سالب/صفر، int.MaxValue (overflow)، قيم مكررة، مدخلات كبيرة جداً.

C#Invariants.cs — finding the maximum, with the proof written next to the code
static int Max(int[] a)
{
    if (a.Length == 0) throw new ArgumentException("array must not be empty");

    int max = a[0];
    // INVARIANT: before each iteration, `max` equals the largest of a[0..i-1]
    for (int i = 1; i < a.Length; i++)
    {
        if (a[i] > max) max = a[i];
        // MAINTENANCE: now `max` is the largest of a[0..i]
    }
    // TERMINATION: i == a.Length, so the invariant says `max` is the largest of ALL elements
    return max;
}

// Edge-case driven tests (xUnit)
public class MaxTests
{
    [Theory]
    [InlineData(new[] { 5 }, 5)]                       // single element
    [InlineData(new[] { -3, -1, -7 }, -1)]             // all negative (a naive `max = 0` start fails here!)
    [InlineData(new[] { 2, 2, 2 }, 2)]                 // all equal
    [InlineData(new[] { int.MinValue, int.MaxValue }, int.MaxValue)]
    public void Max_returns_largest(int[] input, int expected) => Assert.Equal(expected, Max(input));

    [Fact] public void Max_throws_on_empty() => Assert.Throws<ArgumentException>(() => Max([]));
}
  1. Initialization: قبل الدورة الأولى max = a[0] وهو أكبر عنصر في a[0..0] ✓.
  2. Maintenance: لو الـ invariant صح قبل الدورة i ومقارنّا a[i] بـ max فالـ max الجديد أكبر في a[0..i] ✓.
  3. Termination: الـ loop بتقف لما i = a.Length فالـ invariant بيقول إن max هو الأكبر في كل المصفوفة ✓.
  4. لاحظ إن إهمال حالة «array فاضية» هو سبب exception غامض. حددنا السلوك صراحة. والاختبار all negative بيكشف الـ bug الكلاسيكي int max = 0.
في الـ production

الـ correctness بتتحول لـ: unit tests على الـ edge cases، property-based testing (مثلاً: ناتج الترتيب لازم يكون مرتب وبنفس العناصر)، ومقارنة الحل السريع بحل بسيط بطيء على مدخلات عشوائية (differential testing).

15

اختيار الـ Data Structure والـ Trade-offs

Choosing data structures · .NET collections complexity
Deep dive

اختيار الهيكل هو أول قرار أداء بتاخده. القاعدة: ابدأ من العمليات اللي بتعملها أكتر، مش من الهيكل اللي حافظه. اسأل: إيه الـ operations الأساسية؟ محتاج ترتيب؟ كام عنصر؟ مين بيقرأ ومين بيكتب؟ بيتشارك بين threads؟

‎.NET typeAccess / LookupAddRemoveOrdered?Notes
T[]O(1) index——by indexحجم ثابت، أسرع حاجة
List<T>O(1) index / O(n) searchO(1) amortized (end)O(n)by indexالافتراضي لأغلب الحالات
LinkedList<T>O(n)O(1) with nodeO(1) with nodeby linkscache-unfriendly
Dictionary<K,V>O(1) avgO(1) avgO(1) avgnoالأساس في الـ lookup
HashSet<T>O(1) avgO(1) avgO(1) avgnouniqueness، set operations
SortedDictionary<K,V>O(log n)O(log n)O(log n)sorted by keyred-black tree
SortedSet<T>O(log n)O(log n)O(log n)sortedrange queries (GetViewBetween)
SortedList<K,V>O(log n)O(n)O(n)sortedذاكرة أقل، إدراج بطيء
Stack<T> / Queue<T>peek O(1)O(1)O(1)LIFO / FIFOQueue بيستخدم circular buffer
PriorityQueue<E,P>peek O(1)O(log n)O(log n)by prioritymin-heap، not stable
What do you need most? Find by keyfast, no order Keep sequence /index access Order matterssorted / priority DictionaryHashSet List<T> (default)Queue / Stack if ends only Sorted*by key/range PriorityQnext best
شجرة قرار مبسطة لاختيار الـ collection

أمثلة قرارات واقعية

السيناريوالاختيارليه
لوحة نتايج (leaderboard) بتتحدث وبتعرض الأفضل 10PriorityQueue أو SortedSetمحتاج الأكبر/الأصغر بسرعة مع تحديثات
تحويل كود دولة لاسمها من 200 عنصر ثابتينDictionary (أو FrozenDictionary لقراءة فقط)lookup بالـ key و read-mostly
تاريخ عمليات بيتقرأ بالترتيب وبيتضاف في الآخرList<T>append O(1)، cache-friendly
معالجة طلبات بترتيب الوصولQueue<T> / Channel<T>FIFO
حذف التكرار من 1M رقمHashSet<int>O(n) بدل O(n²)
Trade-offs مهمة

الـ O(1) في Dictionary ليها تكلفة ذاكرة أعلى وثابت أكبر؛ على 10 عناصر قد يكون الـ List.Contains أسرع. قيس قبل ما تحسن (BenchmarkDotNet) واختار الأبسط الأوضح أولاً. والتعقيد النظري مش بيحسب cache misses ولا الـ allocations.

16

الأنماط الشائعة، Trie، Union-Find، وطريقة التدريب

Common problem patterns · Trie and Union-Find (later) · practice
Practical

الأنماط الـ 14 الشائعة للمشاكل

بدل ما تحفظ مئات الحلول، اتعلم تتعرف على الـ pattern من شكل المشكلة:

#Patternإيه اللي بيدل عليهالأداة
1Hash Map / Setتكرار، عد، lookup سريع، two-sumDictionary, HashSet
2Two Pointersarray مرتب، palindrome، pairsمؤشرين
3Sliding Windowأطول/أقصر subarray بشرطleft/right
4Fast & Slow Pointerscycles في linked listمؤشر بسرعتين
5Binary Searchمرتب، أو «أقل قيمة ممكنة»lo/hi
6BFSأقصر مسار، levelsQueue
7DFS / Backtrackingكل التراكيب، permutations، pathsrecursion
8Heap / Top-Kأكبر/أصغر K، merge streamsPriorityQueue
9Intervalsدمج مجالات، جدولةSort + sweep
10Stack (Monotonic)next greater element، parsingStack
11Prefix Sumمجاميع مجالات متكررةarray تراكمي
12Dynamic Programmingأحسن/عدد الطرق مع subproblems متكررةdp table
13Greedyاختيار محلي مثبتSort + loop
14Topological Sort / Graphdependencies، ترتيب مهامindegree + queue

Trie و Union-Find (متقدم — بعدين)

الاتنين مش أولوية في الأول، لكن مهم تعرف الفكرة:

C#TrieUnionFind.cs
// Trie: tree of characters — prefix search in O(length), used by autocomplete
public sealed class Trie
{
    private sealed class Node { public Dictionary<char, Node> Next = []; public bool IsWord; }
    private readonly Node _root = new();

    public void Insert(string word)
    {
        var cur = _root;
        foreach (var ch in word)
        {
            if (!cur.Next.TryGetValue(ch, out var nxt)) cur.Next[ch] = nxt = new Node();
            cur = nxt;
        }
        cur.IsWord = true;
    }

    public bool StartsWith(string prefix)
    {
        var cur = _root;
        foreach (var ch in prefix)
            if (!cur.Next.TryGetValue(ch, out cur)) return false;
        return true;
    }
}

// Union-Find (Disjoint Set): "are a and b in the same group?" in ~O(1) amortized
public sealed class UnionFind(int n)
{
    private readonly int[] _parent = Enumerable.Range(0, n).ToArray();
    private readonly int[] _rank = new int[n];

    public int Find(int x) => _parent[x] == x ? x : _parent[x] = Find(_parent[x]);   // path compression

    public bool Union(int a, int b)
    {
        int ra = Find(a), rb = Find(b);
        if (ra == rb) return false;                       // already connected
        if (_rank[ra] < _rank[rb]) (ra, rb) = (rb, ra);   // union by rank
        _parent[rb] = ra;
        if (_rank[ra] == _rank[rb]) _rank[ra]++;
        return true;
    }
}
  1. Trie: كل node فيها أبناءها حسب الحرف. كلمة بتبقى مسار من الجذر، و IsWord بتحدد إن المسار ده كلمة كاملة. StartsWith بتمشي بطول الـ prefix فقط (مش بعدد الكلمات المخزنة). المقايضة: ذاكرة أعلى.
  2. Union-Find: كل مجموعة ليها «ممثل» (root). Find بتعمل path compression (بتوصّل كل node بالـ root مباشرة) و Union بتستخدم union by rank عشان الشجرة تفضل قصيرة. ده بيخلي الاستخدام أسرع بكتير (inverse Ackermann). بتستخدم في كشف cycles في graph وفي Kruskal's MST و friend groups.

إزاي تتدرب بدون ما تتحول لحفظ

الهدف بناء مهارة مش تجميع حلول. نظام بسيط مجرّب (مش جدول إجباري): حل 3 إلى 4 مسائل أسبوعياً بـ C#‎ مقسمة على patterns مختلفة، وكل مسألة اتبع الخطوات دي: (1) افهم المدخلات والقيود واكتب أمثلة صغيرة وحالات حافة، (2) اكتب حل بسيط (brute force) وحدد تعقيده، (3) اسأل «إيه الـ pattern؟ وإيه اللي بيتكرر؟»، (4) حسّن، (5) اكتب unit tests، (6) بعد يومين حلها تاني من الصفر من غير ما تبص. الاستمرارية بتغلب الكمية.

17

أخطاء شائعة في الـ Backend بسبب الـ DSA

Common mistakes and troubleshooting
Pitfalls
الكودالمشكلةالتصحيح
foreach (var o in orders) { var c = customers.First(x => x.Id == o.CustomerId); }O(n·m) — First بتعمل scan لكل ordervar byId = customers.ToDictionary(x => x.Id); ثم byId[o.CustomerId] ⇒ O(n+m)
if (list.Contains(x)) ... داخل loop كبيرةO(n²)حوّل الـ list لـ HashSet قبل الـ loop
استدعاء query.Count() ثم query.ToList() على IQueryableاستعلامين للـ DB، وأحياناً تكرار التنفيذنفّذ مرة واحدة (ToList) وخد .Count
str += x داخل loopO(n²) نسخ strings (immutable)StringBuilder
Mutable key في Dictionaryentry بتضيعkeys immutable (record/string)
Dictionary مشترك بين threads من غير lockcorruption / infinite loop نادرConcurrentDictionary أو lock
تعديل collection أثناء foreachInvalidOperationException (Collection was modified)اتفرج على نسخة ToList() أو اجمع التغييرات وطبّقها بعد الـ loop

إزاي تكتشف المشكلة؟ لو الـ endpoint بطيء مع كبر الداتا: (1) جرّب بـ n مختلفة وشوف هل الزمن بيتضاعف مع n أو n²، (2) استخدم profiler (dotnet-trace / Visual Studio Profiler) وشوف أي method بتاخد الوقت، (3) راجع الـ loops المتداخلة وأي Contains/First/Where جواها، (4) قيس بـ BenchmarkDotNet قبل وبعد التعديل.

18

Knowledge Check

Takeaways · conceptual questions · code reading · interview questions
Basics

أهم النقاط

  • Big O بيوصف معدل النمو، مش الثواني. اهمل الثوابت، وركّز على الحد الأكبر وعلى حالة الـ worst/average.
  • Array/List: وصول O(1) وإدراج في النص O(n). الـ List هو الافتراضي لأن cache-friendly.
  • Dictionary/HashSet: بحث O(1) متوسط بالـ hashing، بشرط عقد Equals/GetHashCode وكلمة keys immutable.
  • BST متوازن: O(log n) مع ترتيب. Heap: الأصغر/الأكبر بسرعة. Graph: BFS لأقصر مسار، DFS للـ cycles والـ backtracking.
  • Binary search على بيانات مرتبة أو على «الإجابة» نفسها؛ احذر overflow والـ off-by-one.
  • Recursion محتاج base case، وخطر stack overflow؛ memoization بتحول exponential لـ linear.
  • الـ correctness = invariant + termination + edge cases، مش «اشتغلت على مثال».

أسئلة مفاهيمية

ليه Dictionary.TryGetValue أسرع من اختبار ContainsKey ثم الـ indexer؟

لأن ContainsKey + dict[key] بيعملوا hash lookup مرتين. TryGetValue بيعمل lookup واحد ويرجّع الـ value.

ليه List.Insert(0, x) في loop بتبطّئ الكود؟

كل Insert(0) بتزحزح كل العناصر خانة (O(n)) فـ n إدراجات = O(n²). استخدم Queue أو LinkedList أو أضف في الآخر ثم Reverse.

امتى القطع في Quick Sort بيبقى O(n²)؟ وإزاي يتجنبوه؟

لما الـ pivot دايماً أصغر أو أكبر عنصر (مثلاً مصفوفة مرتبة مع اختيار آخر عنصر كـ pivot). الحل: pivot عشوائي أو median-of-three، وIntrosort بيتحول لـ heapsort لو العمق زاد (زي Array.Sort).

الفرق بين Memoization و Tabulation؟

Memoization: top-down recursion + cache (بيحسب بس اللي محتاجه). Tabulation: bottom-up بـ loops وجدول (من غير recursion فمفيش stack overflow).

ليه BFS بيدي أقصر مسار في graph غير موزون و DFS لأ؟

BFS بيزور الـ nodes بترتيب المسافة (levels)، فأول مرة بنوصل فيها لـ node بتبقى بأقل عدد edges. DFS بيمشي عميق في مسار ممكن يكون طويل.

قراءة كود

C#What is the complexity?
static List<int> Common(int[] a, int[] b)
{
    var result = new List<int>();
    foreach (var x in a)
        if (Array.IndexOf(b, x) >= 0 && !result.Contains(x))
            result.Add(x);
    return result;
}
إيه تعقيدها؟ وإزاي تحسنها؟

IndexOf O(m) و result.Contains O(k) داخل loop على n ⇒ تقريباً O(n·(m+k)) أي O(n²) تقريباً. تحسين: var set = new HashSet<int>(b); var res = new HashSet<int>(); foreach (var x in a) if (set.Contains(x)) res.Add(x); ⇒ O(n+m).

C#Bug hunt
static int FirstGreater(int[] sorted, int target)   // first index with value > target
{
    int lo = 0, hi = sorted.Length - 1;
    while (lo < hi)
    {
        int mid = (lo + hi) / 2;
        if (sorted[mid] <= target) lo = mid;
        else hi = mid;
    }
    return lo;
}
فين الأخطاء؟

(1) lo = mid ممكن يعمل infinite loop لما hi = lo + 1 لأن mid == lo فمفيش تقدم. لازم lo = mid + 1. (2) (lo + hi) / 2 ممكن يعمل overflow. (3) لو مفيش عنصر أكبر من target بيرجّع index غلط بدل إشارة «مفيش». نسخة صحيحة: نطاق [0, n) و if (sorted[mid] <= target) lo = mid + 1; else hi = mid; وبترجّع lo (ولو lo == n يبقى مفيش).

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

إزاي الـ Dictionary بيشتغل داخلياً؟ وإيه اللي بيحصل في الـ collisions؟

Buckets + entries: الـ hash بيحدد bucket، وكل entry فيها next بتكوّن chain لنفس الـ bucket. الـ lookup بيقارن بالـ Equals على السلسلة. لو العناصر كترت بيتعمل resize. أسوأ حالة O(n) لو الـ hash سيء.

Array.Sort في ‎.NET بتستخدم إيه؟ وهل stable؟

Introsort: quicksort + heapsort fallback + insertion sort للأجزاء الصغيرة. غير stable. للـ stable استخدم LINQ OrderBy.

لو عندك مليار رقم ومحتاج الـ median، تعمل إيه؟

مش هتحمل الكل في الذاكرة. استخدم two-heaps (max-heap للنص الأصغر و min-heap للنص الأكبر) لو stream، أو خوارزميات تقريبية/ترتيب خارجي (external merge sort) أو histogram/bucketing لو النطاق معروف.

↗

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

References & further reading

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

خريطة التغطية: 25 عنصر من الـ Roadmap ومكان شرحه في الدرس
RoadmapBig O Time and Space Complexity§01
RoadmapArrays§02
RoadmapLinked Lists§03
RoadmapStacks§04
RoadmapQueues§04
RoadmapHash Tables§05
RoadmapDictionaries and Sets§05
RoadmapTrees and Binary Search Trees§06
RoadmapHeaps and Priority Queues§07
RoadmapGraphs§08
RoadmapBFS and DFS§08
RoadmapBinary Search§09
RoadmapSorting Algorithms§10
RoadmapRecursion§11
RoadmapTwo Pointers§12
RoadmapSliding Window§12
RoadmapGreedy Algorithms§13
RoadmapBasic Dynamic Programming§13
RoadmapAlgorithm Correctness§14
RoadmapChoosing Data Structures§15
RoadmapTrade-Offs§15
SuggestedThe ~14 common problem patterns§16
SuggestedA steady routine (3-4 problems per week, in C#)§16
SuggestedComplexity of .NET collections: List, Dictionary, HashSet, SortedDictionary§15
SuggestedTrie and Union-Find (later)§16

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

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