Data Structures و Algorithms

#Big-O: النمو مش عدد الثوانيBig-O describes growth, not seconds

لما orders تزيد عشر مرات، هل المعالجة هتزيد عشر مرات ولا مية؟ Big-O بيوصف حدّ نمو الوقت أو المساحة مع حجم الـ input، مع تجاهل الثوابت والحدود الأقل. لازم تقول بتتكلم عن worst case ولا expected ولا amortized؛ الرمز لوحده مش معناه worst case تلقائياً.

// n orders, m customers; customer IDs are unique.
var byId = customers.ToDictionary(c => c.Id); // (1) expected O(m)
foreach (var order in orders) // (2) expected O(n) overall
{
    if (byId.TryGetValue(order.CustomerId, out var customer))
        Console.WriteLine(customer.Name);
}

الخطوات المتتابعة بتتجمع، والمتداخلة بتتحسب حسب عدد تكرارها؛ مش أي loop جوه loop يبقى O(n²). List.Add ممكن O(n) وقت resize، لكنه O(1) amortized على سلسلة إضافات. Amortized تحليل لسلسلة عمليات، مش افتراض input عشوائي. قيس الأداء الفعلي كمان؛ cache locality وتكلفة I/O والثوابت ممكن يفرقوا.

#Arrays و List و LinkedListArrays, List and LinkedList

Array حجمها ثابت، وList<T> بتستخدم array بتكبر عند الحاجة. العناصر متجاورة، لكن لو T reference type، المتجاور هو references مش بالضرورة الـ objects نفسها.

var order = new LinkedList<int>(); // .NET LinkedList is doubly linked.
var node = order.AddLast(42); // (1)
order.AddBefore(node, 17); // (2)
order.Remove(node); // (3)

ابدأ غالباً بـ List. LinkedList مفيدة لو بتوصل للـ nodes مباشرة وبتحركها كتير، زي Dictionary مع doubly linked list في LRU.

#Stack و Queue و PriorityQueueStack, Queue and PriorityQueue

اختار ترتيب الخدمة قبل الأداة. Stack هي LIFO زي كومة أطباق: آخر داخل أول خارج. Queue هي FIFO زي طابور طلبات. PriorityQueue بتختار حسب priority مش وقت الوصول.

var undo = new Stack<string>();
undo.Push("edit");
string action = undo.Pop(); // (1)

var waiting = new Queue<int>();
waiting.Enqueue(42);
int next = waiting.Dequeue(); // (2)

var jobs = new PriorityQueue<string, int>(); // .NET 6+
jobs.Enqueue("routine", 5);
jobs.Enqueue("urgent", 1);
string first = jobs.Dequeue(); // (3) urgent

PriorityQueue في .NET مبنية على array-backed quaternary min-heap؛ فكرة heap العامة مش شرط binary. Collections دي مش durable message brokers ولا thread-safe queues تلقائياً. للـ async producer-consumer قيّم Channel.

#Hash tables: الـ hash مش إثبات مساواةHash tables: a hash is not equality

علشان تدور على product بسرعة، hash بيحدد bucket وبعده equality بتحدد الـ key الحقيقي. Collision طبيعي: keys مختلفة ممكن تقع في نفس bucket أو يكون ليها نفس hash. Lookup متوقع O(1) لما hashing وتوزيع الداتا مناسبين؛ worst case O(n)، وتكلفة hash نفسها ممكن تعتمد على طول key.

1. احسب hash بالـ comparer.
2. حوّله لرقم bucket مناسب؛ التنفيذ الحقيقي بيتعامل مع العلامة وحدود الأرقام.
3. افحص candidates بالـ hash والـ equality.
4. لما الـ table تحتاج تكبر، اعمل resize وإعادة توزيع.

Chaining بيربط العناصر المتصادمة؛ Dictionary في .NET بيستخدم entries array وروابط indexes. Open addressing بيدوّر على slot تانية باستخدام probing. Load factor هو عدد العناصر بالنسبة للخانات؛ الزيادة ممكن تزود التصادم وتستدعي resize.

public override int GetHashCode() => 1;

public override int GetHashCode() => HashCode.Combine(StoreId, Sku);

المثال methods داخل key type عنده Equals متوافق. الأسهل value key زي record ProductKey(int StoreId, string Sku). Equal keys لازم نفس hash، لكن نفس hash مش معناه equal. ماتعدّلش حقول key المؤثرة في equality بعد الإدخال. ماتحفظش GetHashCode كمعرّف دائم أو partition بين processes؛ ممكن يختلف بين التشغيلات. للـ string comparison اختار comparer مناسب للـ contract، مش culture افتراضية بالغلط.

#Trees و BST و Heap و Trie و B-treeTrees, BSTs, heaps, tries and B-trees

Tree مناسبة لhierarchy، لكن نوعها بيحدد العملية السريعة. BST بتحافظ على الأصغر شمال والأكبر يمين؛ البحث O(h)، يعني O(log n) لو balanced، وO(n) لو بقت سلسلة. AVL وRed-black بيحافظوا على التوازن؛ SortedDictionary وSortedSet يستخدموا red-black trees.

public sealed class TreeNode(int value)
{
    public int Value = value;
    public TreeNode? Left, Right;
}
bool Contains(TreeNode? node, int target)
{
    while (node is not null)
    {
        if (node.Value == target) return true;
        node = target < node.Value ? node.Left : node.Right; // (1)
    }
    return false;
}
int MaxDepth(TreeNode? node) => node is null ? 0
    : 1 + Math.Max(MaxDepth(node.Left), MaxDepth(node.Right)); // (2)

Heap ممتازة لاستخراج الأصغر باستمرار، لكن البحث عن قيمة عشوائية O(n). Trie ممكن تستهلك memory كبيرة؛ sorted array مع prefix range أحياناً أبسط. B-tree مش binary tree، ومش كل database index من النوع ده.

#Graphs و BFS و DFSGraphs, BFS and DFS

Graph بتمثل vertices وروابط edges: مستخدمين وعلاقات، أو dependencies، أو شبكة طرق. حدد directed ولا undirected، وweighted ولا unweighted. Adjacency list بتاخد O(V + E) space؛ matrix بتاخد O(V²) لكنها بتفحص وجود edge في O(1).

var graph = new Dictionary<int, List<int>>
{
    [1] = [2, 3], [2] = [4], [3] = [4], [4] = []
};
List<int> Bfs(int start)
{
    var seen = new HashSet<int> { start }; // (1)
    var queue = new Queue<int>([start]);
    var order = new List<int>();
    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        order.Add(node);
        foreach (int next in graph[node])
            if (seen.Add(next)) queue.Enqueue(next); // (2)
    }
    return order;
}
void Dfs(int node, HashSet<int> seen, List<int> order)
{
    if (!seen.Add(node)) return; // (3)
    order.Add(node);
    foreach (int next in graph[node]) Dfs(next, seen, order);
}

visited لوحده مش كفاية لكشف cycle في directed graph: محتاج recursion-stack state أو topological sort. في undirected graph تجاهل edge الرجوع للأب، مع مراعاة multi-edges لو موجودة.

#Dijkstra و topological sortDijkstra and topological ordering

في الرسم البياني، vertex عقدة مثل مدينة وedge طريق بينها وبين مدينة أخرى. BFS (بحث بعرض الطبقات) يناسب الطرق المتساوية؛ DFS (بحث يتعمق في مسار قبل الرجوع) يحل أسئلة وصول وترابط. هنا نحتاج وزنًا لكل edge مثل تكلفة الطريق. Dijkstra يستخدم relaxation: نحسب تكلفة الوصول عبر الطريق الجديد، ونحدّث أفضل تكلفة محفوظة لو كانت أقل. topological sort يستخدم indegree، أي عدد المتطلبات الداخلة للعقدة، ويبدأ بالعقد التي لا تملك متطلبات.

مثال: لو عايز أقل تكلفة توصيل بين مدن، BFS يفترض إن كل طريق تكلفته واحدة. Dijkstra يحفظ أفضل مسافة معروفة لكل مدينة، ويختار الأقل من طابور أولوية؛ لو لقى طريق أرخص يحدّث المسافة ويضيفها للطابور. ده صحيح مع أوزان غير سالبة فقط، لأن طريقًا جديدًا ماينفعش يخلي مدينة اتثبتت سابقًا أرخص. الـ min-heap طابور يخرج أصغر أولوية أولًا.

Topological sort يحل مسألة مختلفة: ترتيب مهام بحيث كل prerequisite (مهمة لازم تسبق غيرها) تيجي قبل اللي تعتمد عليها. ده ممكن فقط في DAG، أي directed graph مفيهوش cycle. الكود التالي يفترض معرفات vertices صحيحة، وأوزان صحيحة غير سالبة، ويمثل الرسم بقوائم جيران.

// Vertices: 0..n-1. Weights are non-negative ints.
long[] Dijkstra(List<(int To, int Weight)>[] graph, int start)
{
    var distance = new long[graph.Length];
    Array.Fill(distance, long.MaxValue);
    distance[start] = 0;
    var heap = new PriorityQueue<int, long>();
    heap.Enqueue(start, 0);
    while (heap.TryDequeue(out int node, out long cost))
    {
        if (cost != distance[node]) continue; // (1)
        foreach (var (to, weight) in graph[node])
        {
            if (weight < 0) throw new ArgumentException("Negative weight");
            long candidate = checked(cost + weight);
            if (candidate >= distance[to]) continue;
            distance[to] = candidate; // (2)
            heap.Enqueue(to, candidate);
        }
    }
    return distance;
}

int[] TopologicalSort(List<int>[] graph)
{
    var degree = new int[graph.Length];
    foreach (var edges in graph)
        foreach (int to in edges) degree[to]++;
    var ready = new Queue<int>();
    for (int i = 0; i < degree.Length; i++)
        if (degree[i] == 0) ready.Enqueue(i); // (3)
    var result = new List<int>();
    while (ready.TryDequeue(out int node))
    {
        result.Add(node);
        foreach (int to in graph[node])
            if (--degree[to] == 0) ready.Enqueue(to);
    }
    if (result.Count != graph.Length) // (4)
        throw new InvalidOperationException("Directed cycle");
    return result.ToArray();
}

افترض valid vertex IDs واختبر self-loops وdisconnected graphs. للأوزان السالبة قيّم Bellman-Ford بدل Dijkstra. ترتيب topological مش لازم يبقى وحيد.

#Binary search و lower boundBinary search and lower bound

لما الداتا مرتبة أو شرطك monotonic، تقدر تستبعد نص search space كل مرة. زي البحث في قاموس. مش لازم تكون بتدور على قيمة موجودة؛ ممكن تدور على أول قيمة تحقق شرط، زي أقل capacity تخلص orders قبل موعد معين.

int BinarySearch(int[] sorted, int target)
{
    int lo = 0, hi = sorted.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2; // (1)
        if (sorted[mid] == target) return mid;
        if (sorted[mid] < target) lo = mid + 1; // (2)
        else hi = mid - 1;
    }
    return -1;
}
int LowerBound(int[] sorted, int target)
{
    int lo = 0, hi = sorted.Length; // (3) half-open interval
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (sorted[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

O(log n) وقت وO(1) مساحة على array. Array.BinarySearch وList.BinarySearch موجودين، والنتيجة السالبة فيها bitwise complement لموضع الإدخال. لو بتعمل sort علشان search واحدة بس، تكلفة O(n log n) ممكن تكون أسوأ من scan O(n).

#Sorting: quick و merge والمقارنةSorting: quicksort, mergesort and trade-offs

Sorting بيخلي البحث والتجميع وinterval processing أسهل، لكن اختار حسب stability والـ memory والـ worst case. Quicksort بيقسم حوالين pivot؛ mergesort بيرتب نصين ويدمجهم.

void QuickSort(int[] values, int lo, int hi)
{
    if (lo >= hi) return;
    int pivot = Partition(values, lo, hi); // (1)
    QuickSort(values, lo, pivot - 1);
    QuickSort(values, pivot + 1, hi);
}
int Partition(int[] values, int lo, int hi)
{
    int pivot = values[hi], write = lo;
    for (int read = lo; read < hi; read++)
        if (values[read] < pivot)
        {
            (values[write], values[read]) = (values[read], values[write]);
            write++;
        }
    (values[write], values[hi]) = (values[hi], values[write]);
    return write;
}

int[] MergeSort(int[] values)
{
    if (values.Length <= 1) return values;
    int mid = values.Length / 2;
    return Merge(MergeSort(values[..mid]), MergeSort(values[mid..])); // (2)
}
int[] Merge(int[] left, int[] right)
{
    var result = new int[left.Length + right.Length];
    int i = 0, j = 0, k = 0;
    while (i < left.Length && j < right.Length)
        result[k++] = left[i] <= right[j] ? left[i++] : right[j++]; // (3)
    while (i < left.Length) result[k++] = left[i++];
    while (j < right.Length) result[k++] = right[j++];
    return result;
}

k حجم key range في counting أو radix base في radix، وd عدد digits. Stability معناها الحفاظ على ترتيب العناصر المتساوية في key. Random pivot يقلل احتمال worst case، وthree-way partition يفيد duplicates؛ ولا واحد ضمان worst-case O(n log n). Array.Sort يستخدم introsort ومش stable؛ LINQ OrderBy stable. في التطبيق استخدم library sort غالباً. للبيانات الأكبر من RAM استخدم external merge sort على runs.

#Recursion و divide and conquer و DP و greedyRecursion, divide and conquer, DP and greedy

Recursion وسيلة للتعبير عن مشكلة أصغر، ولازم base case وتقدم نحوه. Divide and conquer بيقسّم لأجزاء مستقلة ويجمعها. DP بيستفيد من subproblems متكررة، وoptimal substructure في مسائل التحسين؛ counting problems كمان تستخدم DP. Greedy بيختار محلياً من غير رجوع، ومحتاج proof يناسب المشكلة.

// Inputs for these Fibonacci examples: 0..92, fitting in long.
long FibNaive(int n) => n < 2 ? n : FibNaive(n - 1) + FibNaive(n - 2);
long FibMemo(int n, Dictionary<int, long> memo)
{
    if (n < 2) return n;
    if (memo.TryGetValue(n, out long value)) return value; // (1)
    return memo[n] = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);
}
long Fib(int n)
{
    if (n < 2) return n;
    long previous = 0, current = 1;
    for (int i = 2; i <= n; i++)
        (previous, current) = (current, previous + current); // (2)
    return current;
}
// Positive coin values, non-negative amount, feasible array size.
int CoinChange(int[] coins, int amount)
{
    var best = new int[amount + 1];
    Array.Fill(best, int.MaxValue);
    best[0] = 0;
    for (int value = 1; value <= amount; value++)
        foreach (int coin in coins)
            if (coin <= value && best[value - coin] != int.MaxValue)
                best[value] = Math.Min(best[value], best[value - coin] + 1); // (3)
    return best[amount] == int.MaxValue ? -1 : best[amount];
}

عملات 1 و3 و4 ومبلغ 6: greedy يختار 4 و1 و1، لكن الأفضل 3 و3. ماتستنتجش greedy من كام مثال. Deep recursion ممكن تعمل stack overflow؛ explicit stack أو bottom-up أفضل لما العمق كبير.

#خريطة patterns: ابدأ من شكل السؤالA problem-solving pattern map

Pattern بيديك hypothesis مش إجابة جاهزة. اكتب invariant أو recurrence، واختبر constraints قبل اختيار الحل.