Big O: تعقيد الزمن والمساحة
لما بتكتب كود، السؤال مش بس «هل بيشتغل؟» لكن «هيشتغل إزاي لما الداتا تكبر؟». الـ 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 (ذاكرة أكتر) عشان نوفر زمن.
| Complexity | الاسم | n = 1,000 | n = 1,000,000 | مثال |
|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | Array index, Dictionary lookup (average) |
| O(log n) | Logarithmic | ~10 | ~20 | Binary search, balanced tree lookup |
| O(n) | Linear | 1,000 | 1,000,000 | Loop over a list, List.Contains |
| O(n log n) | Linearithmic | ~10,000 | ~20,000,000 | Merge sort, Array.Sort |
| O(n²) | Quadratic | 1,000,000 | 10¹² | Nested loops over the same data |
| O(2ⁿ) | Exponential | تقريباً مستحيل | مستحيل | Naive recursive Fibonacci, subsets |
إزاي تحلل كود فعلي
// 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)
}الشرح
First: عملية واحدة. مهما كبر المصفوفة التكلفة ثابتة.Sum: الـforeachبيعدي على كل عنصر مرة واحدة:nعملية جمع ⇒ O(n). مساحة إضافية O(1) (متغير واحد).HasDuplicateSlow: الـ loop الداخلي بيشتغل (n-1) ثم (n-2) … ⇒ مجموعهاn(n-1)/2وده O(n²). مساحة إضافية O(1).HasDuplicateFast: مرور واحد، وكلAddفيHashSetمتوسطه O(1) ⇒ O(n) زمن. التكلفة إن الـ set ممكن يخزن لحد n عنصر ⇒ O(n) مساحة.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) وتجنب النسخ كلها.
لما endpoint بيتأخر، غالباً السبب O(n²) مخفي: loop فيه list.Contains(...) أو FirstOrDefault(...) جوه loop تانية. أو N+1 queries على الـ database (n استعلام بدل واحد). تحليل الـ Big O بيخليك تشوف ده قبل ما يوصل Production.
Arrays والـ List<T>
الـ Array هو أبسط وأسرع هيكل: مساحة متصلة (contiguous) في الذاكرة لعناصر من نفس النوع. عشان كده الوصول لأي عنصر بالـ index هو عملية حسابية بسيطة: العنوان = عنوان_البداية + index × حجم_العنصر، فهو O(1).
| Operation | Array (T[]) | List<T> |
|---|---|---|
| Index read/write | O(1) | O(1) |
| Append at end | غير ممكن (الحجم ثابت) | O(1) amortized |
| Insert / Remove in the middle | O(n) (يدوي) | O(n) |
| Search unsorted | O(n) | O(n) |
| Search sorted | O(log n) binary search | O(log n) BinarySearch |
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الشرح وتتبع التنفيذ
a[2]بيتحول لـbase + 2×4فمفيش loop ⇒ O(1).- الإدراج في array عادي محتاج array جديد + نسخ جزئين: كل العناصر اللي بعد نقطة الإدراج بتتحرك ⇒ O(n).
- الـ
List<int>بيبدأ بـ capacity = 0، أولAddبيخليها 4 ثم 8 ثم 16… (تضاعف). لما بيتعدى الـ capacity بيعمل array جديد وينسخ — ده الـ O(n) النادر اللي بنحسبه amortized. - الـ
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.
Linked Lists
الـ Linked List كل عنصر فيها (node) بيحمل القيمة + مؤشر للي بعده (وفي الـ doubly linked كمان للي قبله). العناصر مش لازم تكون متجاورة في الذاكرة. ده بيدّيك إدراج وحذف O(1) لو عندك الـ node نفسه، لكن الوصول بالـ index O(n) لأنك لازم تمشي من البداية.
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 قبل ما تقلب المؤشر، وإلا ضيّعت باقي القائمة.
رغم إن Linked List نظرياً أفضل في الإدراج، الـ cache locality بتخلي الـ array أسرع بمراحل: عناصر الـ array متجاورة فبتتحمل في الـ CPU cache مع بعض، لكن الـ nodes منتشرة في الـ heap وكل Next ممكن يكون cache miss، إضافة لتكلفة allocation لكل node. في .NET بتستخدم LinkedList<T> فقط لو عندك الـ LinkedListNode وبتعمل إدراج/حذف كتير في النص، زي الـ LRU cache.
Stacks و Queues
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.
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الشرح وتتبع "{[(])}"
- كل قوس فتح بنعمله
Push. كل قوس قفل لازم يكون مطابق لآخر قوس فتح لسه مفتوح (اللي فوق الـ stack). - التتبع على
{[(])}: Push{، Push[، Push(. بعدها]: Pop ⇒ طلع(مش[⇒ false فوراً. - على
{[()]}: كل قفل بيطابق قمة الـ stack وفي الآخر الـ stack فاضي ⇒ true. بدون الفحص الأخيرstack.Count == 0كان "((" هيعدي غلط. - زمن O(n) ومساحة O(n) في الأسوأ. استخدمنا
TryDequeueبدلDequeueعشان نتجنب exception على queue فاضية.
الـ Call Stack اللي بتتخزن فيه الـ method calls هو stack فعلاً. لو recursion عميقة جداً بيحصل StackOverflowException وفي .NET ده مينفعش يتمسك بـ try/catch والـ process بيقفل. وفي الـ backend: الـ Channel<T> و Message Brokers هي queues متقدمة للـ producer/consumer.
Hash Tables و Dictionaries و Sets
الـ Hash Table هو أهم هيكل بيانات في الـ backend. بيدّيك بحث وإدراج وحذف في O(1) متوسط عن طريق إنك بتحول الـ key لرقم (hash) يحدد المكان اللي هتدور فيه مباشرة بدل ما تمشي على كل العناصر.
إزاي بيشتغل (Internal Mechanics)
- Hashing: الـ key بيتعمله
GetHashCode()فيطلعint. - Bucket: الـ hash بيتحول لـ index داخل مصفوفة الـ buckets (غالباً بـ modulo على حجم أولي).
- Collision: أكتر من key ممكن يوصلوا لنفس الـ bucket. الـ
Dictionaryفي .NET بيحلها بـ chaining: كل entry فيهاnextيشاور على entry تانية في نفس الـ bucket. البحث بيمشي على السلسلة ويقارن بـEquals. - Resize: لما العناصر تتكاثر بيتم تكبير الـ buckets (تقريباً الضعف) وإعادة توزيع كل العناصر (O(n) نادراً ⇒ amortized O(1)).
- لو الـ hash function سيئة وكل الـ keys وقعت في bucket واحد، البحث بيتحول لـ O(n).
لو a.Equals(b) لازم a.GetHashCode() == b.GetHashCode(). لو كسرت العقد ده الـ Dictionary مش هيلاقي الـ key اللي حطيته. ولو استخدمت object mutable كـ key وغيرت الحقول اللي دخلت في الـ hash بعد الإدراج، الـ entry هتضيع (موجودة بس مفيش طريق توصلها). استخدم record أو struct readonly أو string/int/Guid كـ keys.
// 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الشرح
- 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]. - Frequency:
GetValueOrDefaultبيرجّع 0 لو الـ key مش موجود فبنزود 1 من غير exception. ده pattern بتشوفه في كل مكان (word count, group by). - HashSet: بيمنع التكرار وبيدعم عمليات المجموعات:
UnionWithوIntersectWithوExceptWith. - 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 مش مضمون. متبنيش منطق يعتمد على ترتيب الإدراج.
Trees و Binary Search Trees
الـ Tree هيكل هرمي: root، وكل node ليها أبناء. الـ Binary Search Tree (BST) قاعدته: لكل node، كل القيم في الـ left subtree أصغر منها وكل القيم في الـ right subtree أكبر. ده بيخلي البحث زي binary search: كل خطوة بتتخلص من نص الشجرة.
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الشرح
Insertبتنزل يمين أو شمال حسب المقارنة لحد ما توصل لمكان فاضي (null) وتحط فيه node جديدة. الـ recursion بترجّع الـ node في كل مستوى عشان تربط الأبناء.Containsبتنفذ نفس المنطق iteratively: كل مقارنة بتتخلص من فرع كامل.InOrder(يسار، الجذر، يمين) بتطلع القيم مرتبة — دي خاصية الـ BST.- الأنواع الأخرى من الـ traversal: Pre-order (الجذر الأول، لنسخ الشجرة)، Post-order (الجذر الأخير، لحذف الشجرة)، و Level-order (BFS بـ queue).
لو أدخلت قيم مرتبة 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.
Heaps و Priority Queues
الـ Priority Queue هي queue بس اللي بيخرج منها أعلى أولوية مش الأقدم. بتتنفذ بـ Binary Heap: شجرة كاملة بتتخزن في array، وقاعدتها في الـ min-heap إن كل أب ≤ أبنائه، فالأصغر دايماً في الـ index 0.
| Operation | Cost | How |
|---|---|---|
| Peek (min) | O(1) | index 0 |
| Enqueue | O(log n) | أضف في آخر الـ array ثم sift up لحد ما الـ heap property ترجع |
| Dequeue (min) | O(log n) | شيل الجذر، حط آخر عنصر مكانه، ثم sift down |
| Build from n items | O(n) | heapify |
// 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الشرح
- الـ
PriorityQueue(من .NET 6) بتاخد element و priority منفصلين. الأولوية الأصغر بتخرج الأول (min-heap). لو عايز max-heap اعكس الأولوية أو مررComparerمقلوب. - الـ Top-K: بنحافظ على heap حجمه k فقط. أي عنصر جديد بندخله وبنشيل الأصغر لو عدينا k. فالباقي هو أكبر k عناصر. كل عملية O(log k) فالإجمالي
O(n log k)أحسن من ترتيب كل الـ n. - تحذير: الـ PriorityQueue مش stable: عناصر بنفس الأولوية مش مضمون ترتيب خروجها.
- استخدامات: Dijkstra، job schedulers، merging sorted streams، median بـ heaps اتنين.
Graphs و BFS و DFS
الـ 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.
// 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 وتتبعه
- الـ
queueبتخلي الزيارة بالمستويات: كل الجيران على بُعد خطوة قبل اللي على بُعد خطوتين. عشان كده أول مرة نوصل فيها لـgoalنبقى وصلناله بأقل عدد edges. parentبيخدم غرضين: visited set (عشان منزورش node مرتين وندخل في loop لانهائي في الـ cycles)، و تتبع المسار لإعادة بناء الطريق بالرجوع من الهدف للبداية.- التتبع من 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.
- الـ DFS بيستخدم stack (الـ call stack في النسخة recursive). الاتنين زمنهم
O(V+E)ومساحتهمO(V).
| BFS | DFS | |
|---|---|---|
| الهيكل المساعد | Queue | Stack / Recursion |
| بيناسب | أقصر مسار (unweighted)، levels، أقرب جار | الكشف عن cycles، topological sort، backtracking، connected components |
| الذاكرة | ممكن تكبر (عرض الـ graph) | عمق المسار (خطر stack overflow لو recursive) |
Dependency resolution (ترتيب بناء المشاريع في الـ solution، ترتيب الـ migrations، الـ DI circular dependency detection) كلها graph problems: الـ circular dependency اللي شفناها في درس DI هي cycle في directed graph بتتكشف بـ DFS.
Binary Search
لو الداتا مرتبة، بدل ما تدور واحد واحد (O(n)) بتقارن بالعنصر اللي في النص وبتتخلص من نص الاحتمالات كل مرة ⇒ O(log n). في مليون عنصر بتحتاج ~20 مقارنة بس.
// 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)الشرح
- الـ invariant: لو الهدف موجود، فهو دايماً جوه
[lo, hi]. كل خطوة بتصغّر النطاق من غير ما تفقد الهدف. mid = lo + (hi - lo) / 2يتجنب overflow لما lo+hi يعديint.MaxValue(bug مشهور استمر سنين في مكتبات كبيرة).- Lower bound بتستخدم نطاق نصف مفتوح
[lo, hi)؛ لماa[mid] < targetنتخطى mid، وغير كدهhi = mid(mid ممكن يكون هو الإجابة). - Binary search on answer: حتى لو مفيش array مرتب، لو الدالة «ممكنة؟» monotonic (لو سعة X تنفع فكل سعة أكبر تنفع) نقدر نبحث عن أقل قيمة ممكنة.
Array.BinarySearchبترجّع index العنصر لو موجود، وغير كده complement bitwise (~index) للمكان اللي ينفع تدخله فيه.
تطبيقها على بيانات مش مرتبة (نتيجة غلط من غير error)، lo < hi بدل lo <= hi (بيفوّت العنصر الأخير)، أو lo = mid بدل mid + 1 (infinite loop). الحل: فكّر في الـ invariant وجرب على حالات: array فاضية، عنصر واحد، الهدف في الأول/الآخر/غير موجود.
Sorting Algorithms
في الواقع هتستخدم Array.Sort أو OrderBy دايماً. لكن فهم الخوارزميات بيعلمك مفاهيم عامة: divide & conquer، stability، in-place، وتحليل الـ trade-offs.
| Algorithm | Best | Average | Worst | Space | Stable | ملاحظة |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | تعليمي فقط |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | ممتاز للداتا الصغيرة / شبه المرتبة |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | ثابت الأداء، خارجي (external sort) |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | سريع عملياً؛ pivot سيء = أسوأ حالة |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | أسوأ حالة مضمونة بدون ذاكرة |
Stable يعني العناصر المتساوية بتحافظ على ترتيبها الأصلي (مهم لما بترتب بمعيار ثانوي بعد أول). وكمان لحد Comparison sort مستحيل يبقى أسرع من O(n log n) في الأسوأ.
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
- Divide: نقسم المصفوفة نصين لحد ما نوصل لعنصر واحد (مرتب بديهياً). عمق الـ recursion =
log n. - Conquer/Merge: ندمج نصين مرتبين بـ مؤشرين
iوj: بنختار الأصغر من الرأسين. الدمج O(n) لكل مستوى ⇒ الإجماليO(n log n). الـ<=هي اللي بتخلي الخوارزمية stable. - الـ QuickSort:
Partitionبتحط الـ pivot في مكانه النهائي (كل الأصغر قبله والأكبر بعده)، ثم بنرتب الجزئين. لو الـ pivot دايماً أصغر/أكبر عنصر (مصفوفة مرتبة بالفعل مع Lomuto) بيتحول لـ O(n²). - في .NET:
Array.Sort/List.Sortبتستخدم Introsort (quicksort يتحول لـ heapsort لو العمق زاد، و insertion sort للأجزاء الصغيرة) فأسوأ حالة O(n log n) وهي غير stable. بينماOrderByفي LINQ stable.
Recursion
الـ Recursion إن الدالة تنادي نفسها على نسخة أصغر من نفس المشكلة. كل recursion صح لازمله: Base case (حالة بتقف عندها) و Recursive case (بتقرّب للـ base case). كل نداء بياخد stack frame جديد على الـ call stack.
// 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.FibSlow(5)بيناديFibSlow(3)مرتينFibSlow(2)تلات مرات… عدد النداءات بيتضاعف ⇒ O(2ⁿ).- الـ memoization بيخزن كل
fib(k)أول ما يتحسب، فكل قيمة بتتحسب مرة واحدة ⇒ O(n). - النسخة الـ iterative بتحتاج متغيرين بس، ومفيش stack growth.
recursion بعمق عشرات الآلاف (زي القايمة المرتبطة أو DFS على graph ضخم) ممكن تعمل StackOverflowException وده بيقفل الـ process في .NET. للعمق الكبير حوّلها لـ iterative بـ Stack<T> صريح. وكمان .NET مش بيضمن tail-call optimization في C#، فمتعتمدش عليها.
Two Pointers و Sliding Window
دي patterns بتحول حلول O(n²) البديهية لـ O(n) من غير هياكل بيانات إضافية. الفكرة: بدل ما تفحص كل الأزواج/المجالات، بتحرك مؤشرات بناءً على معلومة تخلّيك تستبعد احتمالات كتير.
Two Pointers
مؤشرين على array مرتب (من الطرفين غالباً) أو مؤشر بطيء وسريع. بتتحرك حسب النتيجة: لو المجموع كبير نقص الأيمن، لو صغير زوّد الأيسر.
Sliding Window
نافذة [left, right] بتتمدد من اليمين وبتتقلص من الشمال للحفاظ على شرط معين، فكل عنصر بيدخل ويخرج مرة واحدة ⇒ O(n).
// 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)الشرح
- HasPair: لأن الـ array مرتب: لو
a[l] + a[r]أصغر من الهدف، فـa[l]مع أي عنصر ≤a[r]هيفضل أصغر ⇒ نقدر نستبعدa[l]. نفس المنطق للعكس. ده بيبرّر تحريك المؤشر (فهو correctness argument مش تخمين). - RemoveDuplicates:
readبيمسح الـ array وwriteبيحدد أين نكتب القيمة الجديدة. القيمة بتتكتب بس لو مختلفة عن اللي قبلها. - LongestUnique:
lastSeenبيخزن آخر ظهور لكل حرف. لو الحرف ظهر داخل النافذة الحالية بننقلleftلبعده. على"abcabcbb": النافذةabc(3) ثم لما يجيaتاني left يروح لـ 1… - MaxWindowSum: بدل ما نجمع k عنصر في كل موقع (O(nk))، بنحدّث المجموع بإضافة العنصر الجديد وطرح القديم ⇒ O(n).
Greedy و Basic Dynamic Programming
Greedy
في كل خطوة بتاخد الاختيار الأفضل محلياً وماتبصش وراك. بتشتغل بس لو المشكلة ليها greedy-choice property (الاختيار المحلي الأمثل بيوصّل للحل الأمثل الكلي). لازم تثبت إنها صح، مش تفترض.
Dynamic Programming
للمشاكل اللي فيها subproblems متداخلة و optimal substructure: الحل الأمثل مبني من حلول أمثل لمشاكل أصغر. بنخزن حل كل subproblem مرة واحدة (memoization أو tabulation).
// 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الشرح
- Meetings (Greedy): الاختيار الأمثل: الاجتماع اللي بينتهي أبكر بيسيب أكبر وقت للباقي. إثبات الصحة: أي حل أمثل ممكن نستبدل أول اجتماع فيه بالأبكر انتهاءً من غير ما نقلل العدد.
- 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). - Climbing stairs:
ways(n) = ways(n-1) + ways(n-2)(فيبوناتشي). لاحظ إننا بنخزن آخر قيمتين بس: space optimization. - LCS: لو الحرفين متساويين نزوّد القطري، وغير كده ناخد أحسن من (تخطي حرف من a) أو (تخطي حرف من b). الجدول بيتملي صف صف.
- خطوات حل أي DP: (1) عرّف الـ state (إيه معنى
dp[i])، (2) اكتب الـ recurrence، (3) حدد الـ base cases، (4) حدد ترتيب الملء، (5) راجع إمكانية تقليل المساحة.
Algorithm Correctness
الخوارزمية الصح مش اللي «اشتغلت على 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)، قيم مكررة، مدخلات كبيرة جداً.
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([]));
}- Initialization: قبل الدورة الأولى
max = a[0]وهو أكبر عنصر فيa[0..0]✓. - Maintenance: لو الـ invariant صح قبل الدورة
iومقارنّاa[i]بـmaxفالـ max الجديد أكبر فيa[0..i]✓. - Termination: الـ loop بتقف لما
i = a.Lengthفالـ invariant بيقول إنmaxهو الأكبر في كل المصفوفة ✓. - لاحظ إن إهمال حالة «array فاضية» هو سبب exception غامض. حددنا السلوك صراحة. والاختبار
all negativeبيكشف الـ bug الكلاسيكيint max = 0.
الـ correctness بتتحول لـ: unit tests على الـ edge cases، property-based testing (مثلاً: ناتج الترتيب لازم يكون مرتب وبنفس العناصر)، ومقارنة الحل السريع بحل بسيط بطيء على مدخلات عشوائية (differential testing).
اختيار الـ Data Structure والـ Trade-offs
اختيار الهيكل هو أول قرار أداء بتاخده. القاعدة: ابدأ من العمليات اللي بتعملها أكتر، مش من الهيكل اللي حافظه. اسأل: إيه الـ operations الأساسية؟ محتاج ترتيب؟ كام عنصر؟ مين بيقرأ ومين بيكتب؟ بيتشارك بين threads؟
| .NET type | Access / Lookup | Add | Remove | Ordered? | Notes |
|---|---|---|---|---|---|
T[] | O(1) index | — | — | by index | حجم ثابت، أسرع حاجة |
List<T> | O(1) index / O(n) search | O(1) amortized (end) | O(n) | by index | الافتراضي لأغلب الحالات |
LinkedList<T> | O(n) | O(1) with node | O(1) with node | by links | cache-unfriendly |
Dictionary<K,V> | O(1) avg | O(1) avg | O(1) avg | no | الأساس في الـ lookup |
HashSet<T> | O(1) avg | O(1) avg | O(1) avg | no | uniqueness، set operations |
SortedDictionary<K,V> | O(log n) | O(log n) | O(log n) | sorted by key | red-black tree |
SortedSet<T> | O(log n) | O(log n) | O(log n) | sorted | range 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 / FIFO | Queue بيستخدم circular buffer |
PriorityQueue<E,P> | peek O(1) | O(log n) | O(log n) | by priority | min-heap، not stable |
أمثلة قرارات واقعية
| السيناريو | الاختيار | ليه |
|---|---|---|
| لوحة نتايج (leaderboard) بتتحدث وبتعرض الأفضل 10 | PriorityQueue أو 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²) |
الـ O(1) في Dictionary ليها تكلفة ذاكرة أعلى وثابت أكبر؛ على 10 عناصر قد يكون الـ List.Contains أسرع. قيس قبل ما تحسن (BenchmarkDotNet) واختار الأبسط الأوضح أولاً. والتعقيد النظري مش بيحسب cache misses ولا الـ allocations.
الأنماط الشائعة، Trie، Union-Find، وطريقة التدريب
الأنماط الـ 14 الشائعة للمشاكل
بدل ما تحفظ مئات الحلول، اتعلم تتعرف على الـ pattern من شكل المشكلة:
| # | Pattern | إيه اللي بيدل عليه | الأداة |
|---|---|---|---|
| 1 | Hash Map / Set | تكرار، عد، lookup سريع، two-sum | Dictionary, HashSet |
| 2 | Two Pointers | array مرتب، palindrome، pairs | مؤشرين |
| 3 | Sliding Window | أطول/أقصر subarray بشرط | left/right |
| 4 | Fast & Slow Pointers | cycles في linked list | مؤشر بسرعتين |
| 5 | Binary Search | مرتب، أو «أقل قيمة ممكنة» | lo/hi |
| 6 | BFS | أقصر مسار، levels | Queue |
| 7 | DFS / Backtracking | كل التراكيب، permutations، paths | recursion |
| 8 | Heap / Top-K | أكبر/أصغر K، merge streams | PriorityQueue |
| 9 | Intervals | دمج مجالات، جدولة | Sort + sweep |
| 10 | Stack (Monotonic) | next greater element، parsing | Stack |
| 11 | Prefix Sum | مجاميع مجالات متكررة | array تراكمي |
| 12 | Dynamic Programming | أحسن/عدد الطرق مع subproblems متكررة | dp table |
| 13 | Greedy | اختيار محلي مثبت | Sort + loop |
| 14 | Topological Sort / Graph | dependencies، ترتيب مهام | indegree + queue |
Trie و Union-Find (متقدم — بعدين)
الاتنين مش أولوية في الأول، لكن مهم تعرف الفكرة:
// 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;
}
}- Trie: كل node فيها أبناءها حسب الحرف. كلمة بتبقى مسار من الجذر، و
IsWordبتحدد إن المسار ده كلمة كاملة.StartsWithبتمشي بطول الـ prefix فقط (مش بعدد الكلمات المخزنة). المقايضة: ذاكرة أعلى. - 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) بعد يومين حلها تاني من الصفر من غير ما تبص. الاستمرارية بتغلب الكمية.
أخطاء شائعة في الـ Backend بسبب الـ DSA
| الكود | المشكلة | التصحيح |
|---|---|---|
foreach (var o in orders) { var c = customers.First(x => x.Id == o.CustomerId); } | O(n·m) — First بتعمل scan لكل order | var 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 داخل loop | O(n²) نسخ strings (immutable) | StringBuilder |
| Mutable key في Dictionary | entry بتضيع | keys immutable (record/string) |
Dictionary مشترك بين threads من غير lock | corruption / infinite loop نادر | ConcurrentDictionary أو lock |
تعديل collection أثناء foreach | InvalidOperationException (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 قبل وبعد التعديل.
Knowledge Check
أهم النقاط
- 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 بيمشي عميق في مسار ممكن يكون طويل.
قراءة كود
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).
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 لو النطاق معروف.
المراجع والقراءة الإضافية
الدرس بيشرح الفكرة نفسها؛ الروابط دي للتحقق والتعمق والرجوع لتفاصيل الـ API. (محتاجة إنترنت.)
خريطة التغطية: 25 عنصر من الـ Roadmap ومكان شرحه في الدرس
خلصت الدرس وحليت الأسئلة؟ علّم عليه عشان يتحسب في تقدّمك.