Introduction to DS&A

هنتعلم مع بعض إيه المسائل اللي بتيجي في الـ Interviews، إزاي نفكر فيها ونحلها، وإزاي نعمل Analysis للـ Complexity

أغلب الوقت هكون بتكلم من وجهة نظر الـ Concepts والـ Algorithms ومش ههتم أوي بالـ Implementation. نادراً لما هتلاقوني حاطط كود وبنتناقش فيه، بس لما أعمل كده هستخدم C++.

دورك من اللحظة دي بيتلخص في حاجتين مالهمش تالت:

1. تاخد اللي هنشرحه (زي الـ BFS أو الـ DFS أو الـ Graph Traversal) وتروح تشوف الـ Implementation بتاعه وتذاكره. تحاول تعمله بنفسك (وغالباً هتفشل في الأول)، وبعدين تشوفه وتذاكره.
2. الحل ثم الحل ثم الحل! أنا بشفق على الناس اللي بتسافر من كفر الشيخ وغيرها عشان تحضر الـ 3 ساعات، لأن كل اللي بنعمله ده بيمثل 20-30% بس من المجهود المطلوب عشان تعدي من الـ Interviews. الـ 70-80% الباقيين قايمين على إنك تحل كل يوم. لو حليت شهرين وبعدين قطعت 6 شهور، كأنك معملتش حاجة.

Course Content Overview

الكورس بتاعنا:

1. النهاردة: Introduction للـ C++، الـ STL، الـ Recursion، الـ Brute Force، وشوية Problem Solving Basics.
2. السيشن الجاية: الـ Complexity.
3. السيشن التالتة: الـ Sorting والـ Hashing.
4. السيشن الرابعة: الـ Trees.
5. السيشن الخامسة: الـ Graphs.
6. السيشن السادسة: الـ Dynamic Programming.
7. السيشن السابعة: الـ Problem Solving Techniques (زي الـ Sliding Window والـ Two Pointers).

---

C++ Basics & Data Types

هنبدا من الأول خالص بالـ Data Types الأساسية، واللي هما: int, float, double, long, short, char, bool, void.

Pointer

تخيل إن الـ Memory دي عبارة عن Grid او دولاب، وكل مكان بنخزن فيه بنسميه Cell (أو مربع صغير) او رف في الدولاب، وكل Cell ليها حجم (نفترض إنها 1 Byte). عشان تخزن حاجة كـ Compiler، محتاج تعرف الـ Address بتاع المكان (رقم الـ Cell) والـ Data اللي هتتخزن فيه، وبعدين بشوية Assembly Code بيتعمل Save/Load للـ Data دي.

الـ Pointer في C++ هو Variable عادي جداً، بس الـ Type بتاعه إنه بيشيل الـ Address بتاع الميموري دي. لو عندنا:

// Initialize x with 0
int x = 0; 

الـ Variable ده الـ Type بتاعه int والقيمة زيرو. لو عايز أجيب الـ Address بتاع الـ x بستخدم علامة الـ Alias &x. القيمة اللي بتطلع بتكون رقم Hexadecimal (زي 0x001...) وده رقم الـ Cell.

مينفعش أكتب:

// This will cause an error
int pointer = &x; 

لأن الـ Address نوعه مش Integer، نوعه “Pointer to Integer”. عشان كده بنعرفه بالشكل ده:

// Pointer to integer
int* pointer = &x; 

هل هو بياخد أول Address ولا آخر Address؟ الإجابة إن الـ Integer مثلاً بيتخزن في كذا Cell (بناءً على السايز بتاعه لو 4 Bytes أو لو long long بياخد مساحة أكبر)، الـ Compiler هو اللي بيعرف يـ Resolve الـ Cells دي بالظبط باستخدام الميتا داتا. وبالمناسبة، كلمة new بنستخدمها عشان نحجز مكان في الـ Heap، وهنتكلم عن الـ Heap والـ Stack كمان شوية.

Array

الـ Arrays في C++ عبارة عن Sequence of Data. لو عرفت Array كده:

// Dynamically allocate array
int* array = new int[size]; 

الـ Array ملوش Data Type مخصوص في C++، هو في الحقيقة Pointer to Integer بيشاور على أول مكان (أول Element) في الـ Array. وبما إن الـ Elements بتاعة الـ Array بتكون Contiguous (ورا بعض في الميموري)، فإحنا مش محتاجين نحتفظ بعناوين الـ 10 أو الـ 100 Element كلهم، كفاية نعرف عنوان أول واحد، ولو عايز الـ Element الخامس، بجمع 5 على أول عنوان.

لما بنكتب array[index]، الـ Compiler بيترجمها لـ:

// Resolves to pointer arithmetic
*(array + index); 

بمعنى: هات أول عنوان واجمع عليه الـ Index، واللي هيطلع ده بوينتر، حط قبله علامة الـ Asterisk * (واللي بتعمل حاجة اسمها Dereference) عشان تجيب القيمة (Value) اللي الـ Pointer ده بيشاور عليها. ونادراً ما هنحتاج نتعامل مع الـ Pointers بشكل مباشر كده.

---

Function Parameters Passing

عندنا 4 طرق عشان نمرر بيهم Parameters للـ Function:

1. Pass by Value: بتاخد نسخة (Copy) من الداتا وتحطها في Variable جديد وتبعته للـ Function. لو غيرت قيمته جوه، القيمة الأصلية بره عمرها ما هتتغير.

   • الميزة: القيمة الأصلية محفوظة.
   • العيب: بيستهلك ميموري كتير وكمان وقت ($O(N)$ Time)، تخيل لو بتبعت Array كبير جداً، هتضيع وقت في نسخ كل Element وكمان هتستهلك ميموري إضافية.

2. Pass by Reference: بنستخدم الـ Reference Variable (بعلامة & زي int& x). الـ Variable ده بيشترك مع الـ Variable الأصلي في الـ Symbol Table بيشاوروا على نفس العنوان. مفيش حاجة اسمها إنك تبعت الـ Variable نفسه في C++، إنت بتبعت ريفرنس ليه.

   • الميزة: مفيش أي استهلاك للوقت أو الميموري.
   • العيب: لو غيرت أي حاجة جوه الـ Function، هتتغير بره في القيمة الأصلية.

3. Pass by Pointer: بدل ما تبعت Reference، إنت بتبعت الـ Address بتاع الـ Variable (زي int* x). ولما تيجي تنادي الـ Function بتبعت &x. جوه الـ Function بتعمل Dereference عشان تغير الداتا. هو بيعمل نفس وظيفة الـ Reference بالظبط بس الميكانيزم والـ Syntax مختلف.

4. Pass by Constant Reference: زي const int& x. دي الطريقة اللي هنستخدمها كتير جداً مع الـ Vectors والـ Maps. إنت بتبعته كـ Reference عشان توفر تايم وميموري، بس بتحط const عشان تمنع الـ Compiler إنه يسمحلك بتغييره جوه الـ Function، عشان متغلطش وتغير فيه ويسمع بره.

---

I-O Streams and Namespaces

عشان ناخد Input أو نطبع Output بنستخدم cin و cout، ودول موجودين في Library اسمها <iostream>. ولازم نستخدم:

using namespace std;

الـ Namespace هو Logical Grouping لشويه Functions أو Classes ليهم علاقة ببعض. فإنت بتقول لـ C++ تجيب الـ Implementation بتاع الـ cin والـ cout من الـ Namespace اللي اسمه std. مشكلة ده إن ممكن يحصل Conflict لو عندك أكتر من Namespace فيهم نفس الأسامي، بس ده مش هيحصل في الاسكوب بتاعنا. لو محصلش using هتضطر تكتب std::cin.

كمان في حاجة اسمها الـ Cascading في الـ cin:

// Read multiple inputs
cin >> a >> b >> c; 

الـ Compiler بيترجم دي لـ كذا cin ورا بعض.

---

Standard Template Library (STL)

الـ C++ عملت ثورة ووفرت Standard Template Library (STL)، دي مكتبة فيها شوية Data Structures جاهزة (Containers) زي: Vector, Stack, Queue, Deque, Set, Map وهتسهل علينا حياتنا جداً ومش هنضطر نبني كل حاجة من الصفر. تاني بقولك، اكتب باللغة اللي تريحك.

Iterator

الـ Iterators زي الـ Pointers بالظبط بس مخصصة للـ STL Containers. بنعرفها عشان نعمل Iterate على الـ Elements. ليه مبنستخدمش الـ Index العادي؟ لأن مش كل الـ Data Structures بتكون Linear أو Contiguous ورا بعض في الميموري (زي الـ Linked List, Trees, Graphs, أو الـ Maps).

كل Container (زي الـ Vector) جواه Methods بتساعدنا:

• الـ .begin(): بيشاور على أول Element.
• الـ .end(): بيشاور على المكان اللي بعد آخر Element.
• الـ .rbegin(): بيشاور على آخر Element (للـ Reverse).
• الـ .rend(): بيشاور على المكان اللي قبل أول Element.

ولما بنعمل Loop بنقول:

// Loop until iterator reaches the end
for(auto it = v.begin(); it != v.end(); it++) { ... }

الـ it++ بتنط للـ Element اللي بعده.

C#

في C++ كنا بنستخدم Iterators عشان نعمل traverse على الـ STL Containers زي vector و map.
في C# الفكرة قريبة جدًا، بس بدل ما نستخدم .begin() و .end() إحنا عندنا:

• Cs IEnumerable
• Cs IEnumerator
• و الأشهر والأسهل: foreach

في C# مفيش حاجة اسمها .begin() و .end() صريحة، لكن أي Collection زي List, Dictionary, LinkedList بتimplement IEnumerable، وبالتالي نقدر نعمل عليها Iteration بأكتر من طريقة.

ده أقرب حاجة لفكرة الـ Iterator في C++

List<int> numbers = new List<int> { 10, 20, 30, 40 };
 
// Get the enumerator (similar to begin())
IEnumerator<int> it = numbers.GetEnumerator();
 
// MoveNext() moves to the next element (similar to it++)
while (it.MoveNext())
{
	// Current gives the current element
	Console.WriteLine(it.Current);
}

• الـ GetEnumerator() شبه begin()
• الـ MoveNext() شبه it++
• الـ Current شبه *it
• مفيش end() صريحة، لأن MoveNext() بترجع false لما نوصل للآخر

---

تاني طريقة وهي foreach

دي الطريقة اللي بتستخدم 99% من الوقت

List<int> numbers = new List<int> { 10, 20, 30, 40 };
 
// foreach internally uses an iterator
foreach (int item in numbers)
{
	Console.WriteLine(item);
}

الـ foreach جوه بيستخدم IEnumerator أوتوماتيك،
فهو نفس فكرة الـ Iterator بس بشكل أنضف وأسهل.

---

Reverse Iteration (Equivalent to rbegin / rend)

في C++ كان عندنا rbegin() و rend()
في C# نستخدم Reverse() من LINQ

List<int> numbers = new List<int> { 10, 20, 30, 40 };
 
// Reverse iteration using LINQ
foreach (int item in numbers.Reverse())
{
	Console.WriteLine(item);
}

الـ Reverse() بترجع IEnumerable معكوس
وبالتالي نقدر نعمل عليه Iteration عادي جدًا.

ليه مش دايمًا نستخدم index؟

علشان:

• مش كل الـ Data Structures بتدعم indexing (زي LinkedList)
• بعض الـ Collections مش Contiguous في memory
• الـ Iterators بتخلينا نكتب code generic يشتغل مع أي Collection

Pair & Vector

بدل ما الـ Variable يشيل داتا واحدة، الـ pair بيخليه يشيل قيمتين مع بعض.
يعني بدل ما تعمل متغيرين مرتبطين ببعض، تقدر تحطهم جوه Object واحد مرتبطين logically.

#include <iostream>
#include <utility>
using namespace std;
 
int main() {
    // Declare a pair of int and string
    pair<int, string> p;
 
    // Assign values
    p.first = 10;
    p.second = "Mahmoud";
 
    // Another way to initialize
    pair<int, int> p2 = make_pair(5, 7);
 
    cout << p.first << " " << p.second << endl;
    cout << p2.first + p2.second << endl;
 
    return 0;
}

• الـ first بتمثل أول قيمة
• الـ second بتمثل تاني قيمة
• نقدر نستخدم make_pair() عشان نعمل Initialize بسرعة

الفكرة كلها إن الـ pair بيجمع قيمتين مختلفتين (ممكن يبقوا different types) في Object واحد.

---

الـ vector ده Dynamic Array بتاعنا وهيسهل حياتنا. ميزته إنك مش محتاج تحدد السايز بتاعه، بس طبعاً لو حددت السايز من الأول لو إنت عارفه، ده هيحسن الـ Performance وهيوفر عليك وقت الـ Resizing اللي بيحصل في الباك جراوند.

بنضيف Elements فيه بـ push_back() وبندخل عليه بالـ Square Brackets [] عادي جداً. عشان نجيب آخر Element بنقول v[v.size() - 1].

ممكن نعرف الـ Vector بكذا طريقة:

// Initialize size with default values
vector<int> v(10); 
// Size 10, all values are 3
vector<int> v(10, 3); 

ولو عندك Array عادي وعايز تنقله لـ Vector (عشان مثلاً تستخدم v.sort() لأن الـ Array العادي ملوش بيلت إن Method للسورت)، ممكن تعمله كده:

// Copy from array to vector
vector<int> v(arr, arr + 5); 

C#

الـ Equivalent ليها في C# هو الـ Tuple أو الأفضل منه الـ ValueTuple.

مثال في C# باستخدام ValueTuple

using System;
 
class Program
{
    static void Main()
    {
        // Declare and initialize a tuple
        (int, string) p = (10, "Mahmoud");
 
        // Access values
        Console.WriteLine(p.Item1);
        Console.WriteLine(p.Item2);
 
        // Named tuple (cleaner)
        (int id, string name) person = (5, "Ali");
 
        Console.WriteLine(person.id);
        Console.WriteLine(person.name);
    }
}

• الـ Item1 شبه first
• الـ Item2 شبه second
• نقدر نديهم أسماء عشان الكود يبقى أوضح

---

في C# الـ Equivalent للـ Vector هو الـ List<T> او بنسيمها Generic List.

تعريف List في C#

using System;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        // Empty list
        List<int> v = new List<int>();
 
        // Initialize with capacity (improves performance)
        List<int> v2 = new List<int>(10);
 
        // Initialize with default values (size 10, all zeros)
        List<int> v3 = new List<int>(new int[10]);
 
        // Initialize with same value repeated (like vector(10, 3))
        List<int> v4 = new List<int>();
        for (int i = 0; i < 10; i++)
            v4.Add(3);
    }
}

---

بنضيف Elements فيه بـ Add() (بدل push_back())،
وبندخل عليه بالـ Square Brackets [] عادي جداً.

List<int> v = new List<int>();
 
// Add elements (similar to push_back)
v.Add(10);
v.Add(20);
 
// Access using index
Console.WriteLine(v[0]);
 
// Get last element
Console.WriteLine(v[v.Count - 1]);

• الـ Add() شبه push_back()
• الـ Count شبه size()
• الـ v[v.Count - 1] نفس فكرة v[v.size() - 1]

---

ولو عندك Array عادي وعايز تحوله لـ List:

int[] arr = { 1, 2, 3, 4, 5 };
 
// Copy from array to List
List<int> v = new List<int>(arr);

كده نقلنا الداتا من Array لـ List،
وبقينا نقدر نستخدم Methods زي Sort():

v.Sort(); // Built-in sort

الفكرة العامة إن:

• الـ pair ↔ ValueTuple
• الـ vector ↔ List<T>

والـ Concept واحد:
الـ Container ديناميك بيكبر معاك، وبيوفرلك Built-in Methods تسهل عليك التعامل مع الداتا.

Set & Map

• الـ Set: هو Container أي داتا جواه بتكون Sorted و Unique (مفيهاش تكرار). من تحت الـ Hood، هي عبارة عن Binary Search Tree (غالباً AVL أو Red-Black). مش هتعرف تستخدم معاها Index، لازم Iterators (أو الـ for-each اللي اشتغلت في C++ من كام سنة).
• الـ Multiset: زي الـ Set سورتد بس بتسمح بالـ Duplicates.
• الـ Unordered Set: دي Unique بس مش Sorted (بتستخدم Hashing).
• الـ Map: زي الـ Set بس بتشيل Key و Value. الكيز بتكون Sorted و Unique.
• الـ Multimap: بتسمح بـ Duplicates في الكيز.
• الـ Unordered Map: دي الـ Hash Map الحقيقية، مش سورتد بس سريعة جداً. هنستخدمها كتير أوي في الـ Dynamic Programming عشان نسجل الـ States، وساعتها عشان ندور على كي معين هنقول map.find(key) != map.end() عشان نعرف الكي موجود ولا لأ.

الـ Set

الـ Set بيخزن Elements تكون Sorted و Unique، ومفيش Indexing، والـ Traversal بيكون بالـ Iterator أو for-each.

#include <iostream>
#include <set>
using namespace std;
 
int main() {
    set<int> s;
 
    // Insert elements
    s.insert(5);
    s.insert(1);
    s.insert(5); // duplicate, won't be inserted
 
    // Iterate using for-each
    for (int x : s) {
        cout << x << " ";
    }
 
    // Search
    if (s.find(1) != s.end()) {
        cout << "\nFound";
    }
 
    return 0;
}

---

الـ Multiset

زي الـ Set بس بيسمح بالـ Duplicates.

#include <iostream>
#include <set>
using namespace std;
 
int main() {
    multiset<int> ms;
 
    ms.insert(5);
    ms.insert(5);
    ms.insert(1);
 
    for (int x : ms) {
        cout << x << " ";
    }
 
    return 0;
}

---

الـ Unordered Set

هي Unique بس مش Sorted، بيعتمد على Hashing.

#include <iostream>
#include <unordered_set>
using namespace std;
 
int main() {
    unordered_set<int> us;
 
    us.insert(10);
    us.insert(2);
    us.insert(10);
 
    for (int x : us) {
        cout << x << " ";
    }
 
    return 0;
}

---

الـ Map

بيخزن Key-Value pairs، والـ Keys Sorted و Unique.

#include <iostream>
#include <map>
using namespace std;
 
int main() {
    map<string, int> mp;
 
    mp["Ali"] = 10;
    mp["Omar"] = 20;
 
    for (auto p : mp) {
        cout << p.first << " -> " << p.second << endl;
    }
 
    return 0;
}

---

الـ Multimap

بيسمح بـ Duplicates في الـ Keys.

#include <iostream>
#include <map>
using namespace std;
 
int main() {
    multimap<string, int> mm;
 
    mm.insert({"Ali", 10});
    mm.insert({"Ali", 20});
 
    for (auto p : mm) {
        cout << p.first << " -> " << p.second << endl;
    }
 
    return 0;
}

---

الـ Unordered Map

بيعتمد على Hashing، Lookup سريع.

#include <iostream>
#include <unordered_map>
using namespace std;
 
int main() {
    unordered_map<string, int> ump;
 
    ump["Ali"] = 100;
    ump["Omar"] = 200;
 
    if (ump.find("Ali") != ump.end()) {
        cout << "Found Ali\n";
    }
 
    return 0;
}

C#

SortedSet ⇒ Set

بيخزن Elements Sorted و Unique، ومفيش Indexing مباشر.

using System;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        SortedSet<int> s = new SortedSet<int>();
 
        // Add elements
        s.Add(5);
        s.Add(1);
        s.Add(5); // duplicate ignored
 
        foreach (int x in s)
        {
            Console.WriteLine(x);
        }
 
        // Search
        if (s.Contains(1))
        {
            Console.WriteLine("Found");
        }
    }
}

---

Multiset ⇒using Dictionary (No direct equivalent)

مفيش Multiset جاهز، فبنستخدم Dictionary<T,int> نخزن فيه العنصر وعدد تكراره.

using System;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        Dictionary<int, int> multiset = new Dictionary<int, int>();
 
        int value = 5;
 
        if (!multiset.ContainsKey(value))
            multiset[value] = 0;
 
        multiset[value]++;
 
        foreach (var pair in multiset)
        {
            Console.WriteLine($"{pair.Key} count = {pair.Value}");
        }
    }
}

---

HashSet ⇒ Unordered Set

هي Unique ومش Sorted.

using System;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        HashSet<int> hs = new HashSet<int>();
 
        hs.Add(10);
        hs.Add(2);
        hs.Add(10);
 
        foreach (int x in hs)
        {
            Console.WriteLine(x);
        }
    }
}

---

SortedDictionary ⇒ Map

عبارة Key-Value pairs، والـ Keys Sorted و Unique.

using System;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        SortedDictionary<string, int> mp = new SortedDictionary<string, int>();
 
        mp["Ali"] = 10;
        mp["Omar"] = 20;
 
        foreach (var pair in mp)
        {
            Console.WriteLine($"{pair.Key} -> {pair.Value}");
        }
    }
}

---

Multimap ⇒ Dictionary<TKey, List> no direct equivalent

مفيش Container مباشر، فبنستخدم List جوا Dictionary.

using System;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        Dictionary<string, List<int>> multimap = new Dictionary<string, List<int>>();
 
        string key = "Ali";
 
        if (!multimap.ContainsKey(key))
            multimap[key] = new List<int>();
 
        multimap[key].Add(10);
        multimap[key].Add(20);
 
        foreach (var pair in multimap)
        {
            foreach (var value in pair.Value)
            {
                Console.WriteLine($"{pair.Key} -> {value}");
            }
        }
    }
}

---

Dictionary ⇒ Unordered Map

بيعتمد على Hashing و Lookup سريع.

using System;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        Dictionary<string, int> ump = new Dictionary<string, int>();
 
        ump["Ali"] = 100;
        ump["Omar"] = 200;
 
        if (ump.ContainsKey("Ali"))
        {
            Console.WriteLine("Found Ali");
        }
    }
}

STL Algorithms

في بيلت إن Functions مهمة جدًا في الـ STL:

• الـ sort(v.begin(), v.end()): بتعمل Sorting للـ Range كله، وبتشتغل في متوسط حالة بـ O(N log N).
• الـ binary_search: لازم تشتغل على Container يكون Sorted الأول. فكرتها إنها بتقسم الـ Search Space نصين كل مرة، فكل Step بتلغي نص الاحتمالات، وعلشان كده الـ Complexity بتاعتها O(log N).
• الـ lower_bound: بترجع Iterator على أول Element أكبر من أو يساوي القيمة اللي بتدور عليها.
• الـ upper_bound: بترجع Iterator على أول Element أكبر strictly من القيمة.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    vector<int> v = {5, 1, 4, 2, 3};
 
    // Sort the vector
    sort(v.begin(), v.end());
 
    // Binary search (returns true/false)
    if (binary_search(v.begin(), v.end(), 3)) {
        cout << "Found 3\n";
    }
 
    // lower_bound
    auto lb = lower_bound(v.begin(), v.end(), 3);
    cout << "lower_bound: " << *lb << endl;
 
    // upper_bound
    auto ub = upper_bound(v.begin(), v.end(), 3);
    cout << "upper_bound: " << *ub << endl;
 
    return 0;
}

الفرق المهم:

• الـ binary_search بيرجع bool.
• الـ lower_bound و upper_bound بيرجعوا Iterator.
• تقدر تستخدم الفرق بينهم عشان تجيب عدد التكرارات:
  count = upper_bound - lower_bound.

---

C#

في C# الـ Equivalent موجود في List<T> و Array، وكمان في LINQ.

• الـ Sort(): موجودة جوه List<T> و Array.Sort()، وبتشتغل بـ O(N log N).
• الـ BinarySearch(): موجودة في List<T> و Array، ولازم الداتا تكون Sorted الأول، وبتشتغل بـ O(log N).
• مفيش lower_bound و upper_bound Built-in بنفس الاسم، لكن تقدر تستخدم BinarySearch() وترتب النتيجة عشان توصل لنفس الفكرة.

using System;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        List<int> v = new List<int> { 5, 1, 4, 2, 3 };
 
        // Sort the list
        v.Sort();
 
        // Binary search
        int index = v.BinarySearch(3);
 
        if (index >= 0)
        {
            Console.WriteLine("Found 3 at index " + index);
        }
    }
}

مهم تعرف إن:

• الـ BinarySearch() بيرجع Index لو لقى العنصر.
• لو ملقهوش بيرجع رقم سالب (negative insertion index).
• مفيش Iterator في C#، فإنت بتتعامل بالـ Index.

---

في C++ كنا بنستخدم الـ lower_bound و upper_bound جاهزين.
في C# مفيش نفس الـ API بالاسم، فمهم تبقى عارف تعملهم بإيدك، وده بيتسأل كتير في الانترفيوز.

الفكرة الأساسية:

• الـ lower_bound: أول Index العنصر فيه >= target
• الـ upper_bound: أول Index العنصر فيه > target

والاتنين لازم يشتغلوا على Array أو List تكون Sorted.

---

الـ lower_bound

// Returns first index where value >= target
static int LowerBound(List<int> arr, int target)
{
    int left = 0;
    int right = arr.Count; // notice: not Count - 1
 
    while (left < right)
    {
        int mid = left + (right - left) / 2;
 
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
 
    return left;
}

إحنا هنا بنضيق الـ Search Space لحد ما نوصل لأول مكان ينفع يتحط فيه الـ target من غير ما يكسر الترتيب.
لو العنصر مش موجود، بيرجعلك مكان إدخاله الصح.

---

الـ upper_bound

// Returns first index where value > target
static int UpperBound(List<int> arr, int target)
{
    int left = 0;
    int right = arr.Count;
 
    while (left < right)
    {
        int mid = left + (right - left) / 2;
 
        if (arr[mid] <= target)
            left = mid + 1;
        else
            right = mid;
    }
 
    return left;
}

• في LowerBound الشرط:
  arr[mid] < target
• في UpperBound الشرط:
  arr[mid] <= target

وده الفرق اللي بيحدد هل هتقف عند أول مساوي ولا أول أكبر.

---

using System;
using System.Collections.Generic;
 
class Program
{
    static int LowerBound(List<int> arr, int target)
    {
        int left = 0;
        int right = arr.Count;
 
        while (left < right)
        {
            int mid = left + (right - left) / 2;
 
            if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
 
        return left;
    }
 
    static int UpperBound(List<int> arr, int target)
    {
        int left = 0;
        int right = arr.Count;
 
        while (left < right)
        {
            int mid = left + (right - left) / 2;
 
            if (arr[mid] <= target)
                left = mid + 1;
            else
                right = mid;
        }
 
        return left;
    }
 
    static void Main()
    {
        List<int> v = new List<int> { 1, 2, 2, 2, 4, 5 };
 
        int lb = LowerBound(v, 2);
        int ub = UpperBound(v, 2);
 
        Console.WriteLine("LowerBound index: " + lb);
        Console.WriteLine("UpperBound index: " + ub);
        Console.WriteLine("Count of 2 = " + (ub - lb));
    }
}

• الاتنين O(log N)
• نفس فكرة الـ Binary Search
• شغالين على Sorted Array بس

---

Data Structures Representation

Tree

الـ Tree عبارة عن Node، كل Node شايلة الداتا وبوينترز للـ Children.
لو Binary Tree بيبقى عندنا left و right.
لو Generic Tree بنستخدم vector من الـ Nodes بدل Array عادية.

Binary Tree Implementation

#include <iostream>
using namespace std;
 
struct Node {
    int data;
    Node* left;
    Node* right;
 
    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};
 
int main() {
    Node* root = new Node(1);
 
    root->left = new Node(2);
    root->right = new Node(3);
 
    cout << root->left->data << endl;
 
    return 0;
}

---

Generic Tree Implementation

#include <iostream>
#include <vector>
using namespace std;
 
struct Node {
    int data;
    vector<Node*> children;
 
    Node(int value) {
        data = value;
    }
};
 
int main() {
    Node* root = new Node(1);
 
    root->children.push_back(new Node(2));
    root->children.push_back(new Node(3));
 
    cout << root->children[0]->data << endl;
 
    return 0;
}

---

Graph

عندنا طريقتين لتمثيل الـ Graph.

Adjacency List

كل Node ليها List من الـ Neighbors.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n = 5;
    vector<vector<int>> adj(n);
 
    // Add edge between 0 and 1
    adj[0].push_back(1);
    adj[1].push_back(0);
 
    for (int neighbor : adj[0]) {
        cout << neighbor << " ";
    }
 
    return 0;
}

---

Adjacency Matrix

الـ 2D Array بتمثل وجود Edge.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n = 5;
    vector<vector<int>> matrix(n, vector<int>(n, 0));
 
    // Add edge between 0 and 1
    matrix[0][1] = 1;
    matrix[1][0] = 1;
 
    if (matrix[0][1] == 1) {
        cout << "Edge exists";
    }
 
    return 0;
}

---

• الـ Matrix:
  • Space = O(N²)
  • Check edge = O(1)
• الـ List:
  • Space = O(N + E)
  • Check edge = O(degree)

---

C#

Trees

في C# بدل البوينترز بنستخدم References عادي.

Binary Tree

using System;
 
class Node
{
    public int Data;
    public Node Left;
    public Node Right;
 
    public Node(int value)
    {
        Data = value;
    }
}
 
class Program
{
    static void Main()
    {
        Node root = new Node(1);
        root.Left = new Node(2);
        root.Right = new Node(3);
 
        Console.WriteLine(root.Left.Data);
    }
}

---

Generic Tree

using System;
using System.Collections.Generic;
 
class Node
{
    public int Data;
    public List<Node> Children = new List<Node>();
 
    public Node(int value)
    {
        Data = value;
    }
}
 
class Program
{
    static void Main()
    {
        Node root = new Node(1);
 
        root.Children.Add(new Node(2));
        root.Children.Add(new Node(3));
 
        Console.WriteLine(root.Children[0].Data);
    }
}

---

Graphs

Adjacency List

using System;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        int n = 5;
        List<int>[] adj = new List<int>[n];
 
        for (int i = 0; i < n; i++)
            adj[i] = new List<int>();
 
        adj[0].Add(1);
        adj[1].Add(0);
 
        foreach (int neighbor in adj[0])
        {
            Console.WriteLine(neighbor);
        }
    }
}

---

Adjacency Matrix

using System;
 
class Program
{
    static void Main()
    {
        int n = 5;
        int[,] matrix = new int[n, n];
 
        matrix[0, 1] = 1;
        matrix[1, 0] = 1;
 
        if (matrix[0, 1] == 1)
        {
            Console.WriteLine("Edge exists");
        }
    }
}

---

Stack vs. Heap Memory

Stack

الـ Stack مساحة الميموري اللي بتستخدم لتخزين الـ Local Variables والـ Function Calls.
مساحته Limited وصغيرة مقارنة بالـ Heap، ومفيش حاجة اسمها Resize.

• التخزين فيه بيكون Automatic.
• أول ما الـ Scope يخلص، الميموري بتتفضي لوحدها.
• بيخزن:
  • الـ Primitive Variables (زي int, double).
  • الـ References نفسها (مش الـ Objects).
  • الـ Function Call Frames في حالة الـ Recursion.

مثال C++:

void func() {
    int x = 10; // stored in Stack
}

مثال C#:

void Func()
{
    int x = 10; // stored in Stack
}

كل Call للـ Function بيعمل Stack Frame جديد.

---

Heap

الـ Heap مساحة الميموري اللي بنستخدمها في الـ Dynamic Allocation وقت الـ Run Time.

• مساحته أكبر بكتير.
• التخزين فيه Manual في C++ (لازم تعمل delete).
• في C# بيكون Automatic عن طريق الـ Garbage Collector.
• بيخزن الـ Objects والـ Dynamic Data Structures.

مثال C++:

int* p = new int(5); // allocated in Heap
delete p;            // must free manually

مثال C#:

int[] arr = new int[5]; // array stored in Heap
// GC will free it automatically

---

نقطة مهمة في الانترفيو

الـ vector في C++:

• الـ Object نفسه (الحجم، الكاباسيتي، البوينتر) بيتخزن في الـ Stack لو متعرف Local.
• لكن الـ Elements نفسها بتتحجز في الـ Heap.

مثال:

vector<int> v(100);

• الـ v نفسه في الـ Stack.
• الـ 100 عنصر في الـ Heap.

نفس الفكرة في C# مع List<T>:

List<int> list = new List<int>(100);

• الـ Reference في الـ Stack.
• الـ Internal Array في الـ Heap.

---

غلطة مشهورة في الانترفيو (Recursion)

لو كتبت حل بـ Recursion:

int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
}

في ناس تقول Space Complexity = O(1) عشان مفيش Array جديد.

ده غلط.

ليه؟

لأن كل Recursive Call بيتحط في الـ Stack كـ Stack Frame.
لو عندك N Calls، يبقى عندك N Frames.

فـ:

• Time Complexity = O(N)
• الـ Space Complexity = O(N) بسبب عمق الـ Recursion

في C# نفس الفكرة:

static int Sum(int n)
{
    if (n == 0) return 0;
    return n + Sum(n - 1);
}

كل Call بتتزود في الـ Call Stack.

---

Summary

Feature	Stack	Heap
Size	Limited	Large
Management	Automatic	Manual (C++) / GC (C#)
Allocation Time	Compile Time (mostly)	Run Time
Used For	Local variables, Call stack	Objects, Dynamic structures
Resize	No	Yes

• الـ Stack: مساحته Limited جداً وأقل من الـ Heap، مفيش حاجة اسمها Resize ليه. بيتخزن فيه الحاجات الـ Static اللي بتتحجز في الـ Compile Time. وبيكون Automatic يعني الـ Compiler عارف إمتى يحجز وإمتى يفضي مجرد ما الـ Scope بتاع الـ Variable يخلص.
• الـ Heap: بنعمل فيه Dynamic Allocation في الـ Run Time، ولازم تفضيه بنفسك، ولو مفضتوش مش هيفضى غير لما البرنامج كله يخلص والـ OS ينضف وراك. لو الكود بتاعك كبير وعمال تحجز ميموري ومبتفضيش، الـ Heap هتتملي.

ملحوظة مهمة: الـ Vector الـ Header بتاعه (اسمه والسايز) بيتحط في الـ Stack، بس الـ Elements نفسها بتتحط في الـ Heap. فلو سألوك في الانترفيو عن الـ Space Complexity ممكن تفصلهم تقوله الستاك كذا والهيب كذا.

غلطة مشهورة في الانترفيو: حد يكتب حل بـ Recursion، ولما يتسأل عن الـ Space Complexity يقول $O(1)$ بحجة إنه معملش Array جديد! ده غلط، لأن إنت عملت N Recursive Calls، وكل كول بتتحط في الـ Stack، فالـ Space Complexity بتاعتك بتكون $O(N)$ بناءً على عمق الـ Recursion.

---

Common Mistakes & Time Limits

Integer Overflow

السايز بتاع الـ Integer في أغلب البروسيسورز هو 32 Bits (بيشيل لحد $2^{31}-1$). لو جيت تضرب رقمين كل واحد 50,000، هتحصل مشكلة الـ Overflow والناتج هيلف (Wraparound) ويجيبلك أرقام بالسالب. عشان تحلها:

// Avoid integer overflow
long long res = (long long)a * b;

لازم الـ Operation نفسها تحصل كـ long long مش الـ Variable النهائي بس، عشان لو اتضربوا كـ int هيحصل Overflow قبل ما يتسجلوا.

Time Limit Exceeded (TLE)

أغلب الـ Processors بترن حوالي $10^8$ Instruction في الثانية. والـ Online Judges (زي LeetCode) بتدي تايم ليمت من ثانية لثانيتين. فلو المسألة الكونسرتينز بتاعتها $10^5$، والحل بتاعك $O(N^2)$، ده معناه $10^{10}$ عمليات، وده أكبر بكتير من $10^8$، فأكيد هيجيلك TLE. ساعتها هتعرف إن حلك مش هينفع ولازم تفكر في حل أسرع زي $O(N\log N)$ أو $O(N)$.

Undefined Behavior

لو عملت Access لـ array[-1]، الـ Compiler هيـ Dereference الميموري اللي قبل أول Element في الـ Array! دي ميموري إنت مش مسؤول عنها وفيها Garbage Values. ده بيسموه Undefined Behavior. نفس الكلام لو معملتش Initialize لـ Variable.

Output Formatting

المسألة بتديلك Input وبتطلب Output بصيغة معينة. متطبعش “The answer of the problem is…“. اطبع الرقم أو الحاجة المطلوبة بس عشان تعدي من المسألة. شغل “Please enter the number” ده بتاع سنة أولى كلية مبنعملوش هنا.

---

Problem Solving & Interview Strategies

Trust the Constraints

المسألة بتديك Constraints، مثلاً $X$ من صفر لـ 10,000. متجيش إنت تكتب في أول سطر if (x < 0) return;. ليه الـ Trust Issues دي؟ طالما قالك مفيش أقل من زيرو يبقى مفيش. الـ Valdiations الزيادة دي بتعمل Overcomplicating للكود، وبتصعب عليك الـ Debugging جداً، والانترفيور هيزهق منك والوقت هيخلص. Stick to the requirements!

Don’t Make Assumptions

متفترضش حاجة مش مكتوبة. محدش جابلك سيرة إن الـ Array سورتد يبقى مش سورتد. كل كلمة في الـ Problem Description مكتوبة لسبب. لو قالك مفيش أرقام Negative، يبقى ممكن يكون فيه زيرو. لو قالك Non-decreasing، يبقى ممكن يكون فيه Duplicates. متفترضش بناءً على الـ Sample Input إن كل التستات زيه.

Testing your Code

بنعمل تست عشان نختبر الـ:

• الـ Correctness: بيطلع الإجابة المتوقعة.
• الـ Completeness: كل الـ Paths بتطلع إجابة.
• الـ Limits: مش بـ Crash لو دخلتله Empty Array أو الماكسيمم بتاع الرينج. (ودي اسمها الـ Minimum/Maximum test cases بجانب الـ Random/System tests).

The Interview Scenario

دخلت الانترفيو وأخدت المسألة، هتعمل إيه؟

1. اقرأ المسألة في سرك وحاول تستوعبها. متديش لنفسك أكتر من دقيقتين صمت.
2. لو جالك حل، قوله.
3. لو مجالكش حل، ابدأ اتكلم واكسر الصمت، قوله “المسألة بتقول كذا وأنا فهمت كذا، هل ده صح؟”
4. لو لسه مفيش حل، الـ Safest Side هو الـ Brute Force. أضعف الإيمان إنك تعرف تجيبه.

وممكن يقولك ماتكتبهوش، بس ميزة الـ Brute Force إنه بيفتحلك سكك وأبواب تقدر تجيب منها Optimizations، بتشوف إيه الخطوات الـ Redundant (المكررة) وتبدأ تحسنها.

---

Recursion

الـ Recursion ملوش حل سحري، هو عبارة عن Function بتنادي نفسها، وليها Base Condition (عشان أخرج منه) و State و State Transition. عشان تبقى كويس فيه لازم تحل كتير لحد ما يتكون عندك مهارة الـ Pattern Recognition، وتبقى قادر تربط المسألة الجديدة بمسائل حليتها قبل كده وتضيق مساحة البحث في دماغك. أغلب مسائل الـ Trees, Graphs (DFS), الـ Combinations، والـ DP قايمة على الـ Recursion.

Problem Example: Climbing Stairs

لو عندك سلم طوله $N$، وفي كل خطوة مسموحلك تطلع يا سلمة يا سلمتين، في كام طريقة توصل بيهم من زيرو لـ $N$؟ لو $N=3$، عندك 3 طرق (1+1+1، 1+2، 2+1). لو $N=4$، عندك 5 طرق. (مش $N+1$، اللي قال كده ده تسرع وهتاخد عليه Rejection في نص دماغك!).

الحل: عند كل خطوة، إنت عندك احتمالين (Two Calls): يا تطلع سلمة، يا تطلع سلمتين. عشان نوصل للسلمة الـ $N$، عدد الطرق هو مجموع عدد الطرق اللي وصلتني للسلمة اللي قبلي ($N-1$) + عدد الطرق اللي وصلتني للسلمة اللي قبل قبلي ($N-2$). وده بالظبط نفس منطق الـ Fibonacci.

graph TD
    A[4] --> B[3]
    A --> C[2]
    B --> D[2]
    B --> E[1]
    C --> F[1]
    C --> G[0]
    D --> H[1]
    D --> I[0]

الـ Recursion Tree دي بتوضح المسارات، وكل ما بنوصل لصفر بنرجع 1، وأي حاجة غير صالحة بترجع صفر ونبدأ نجمع وإحنا طالعين.

الـ Complexity هنا: بما إن عند كل خطوة في احتمالين، وطول السلم $N$، فالـ Time Complexity هي $O(2^N)$ (مش $O(N^2)$!).

طرق إرجاع النتيجة من الـ Recursion:

1. تجمع النتيجة في Variable وإنت نازل وتبعته معاك كـ Parameter.
2. تستخدم Global Variable (أو Pass by Reference) تجمع فيه ولما تخلص يكون شايل الإجابة والـ Function تكون void.
3. الـ Function نفسها تعمل Return وتبقى بتعمل Sum وإنت طالع لفوق في الـ Tree.

---

Brute Force & Optimization

الـ Brute Force هو الحل الـ Naive اللي بيـ Enumerate أو بيجرب كل الـ Search Space وكل الاحتمالات بغباء وبعدين يتأكد إيه ينفع وإيه لأ.

عيوبه: بطيء جداً، بيستهلك تايم وميموري وبيخليك تحس باليأس. مميزاته:

1. حل مضمون وسهل و Complete.
2. بنحتاجه عشان نعمل Validation للـ Algorithms الجديدة اللي بنكتبها (نقارن الإجابات ببعض).
3. بيفتح عينك للـ Optimizations ويوضحلك إنت بتعمل إيه ملوش لازمة فتبدأ تحسنه.

مثال للتوضيح: عايزين نجيب أكبر مجموع لرقمين (Max Sum) في Array.

• الحل البرووت فورس: هنجرب كل رقمين مع بعض (All Pairs) ونشوف المجموع، وده بياخد $O(N^2)$. بس هل منطقي أجمع أرقام صغيرة وأنا عندي أرقام بـ 10,000 في الـ Array؟
• التحسين الأول: عشان نتجاهل الأرقام الصغيرة، هندور على الماكسيمم، وبعدين نعمل Loop تانية ندور على تاني أكبر رقم. كده الـ Complexity بقت $O(2N)$.
• التحسين التاني: ليه نلف مرتين؟ نعمل Loop واحدة، ونحتفظ بمتغيرين (Max 1 و Max 2)، وطول ما إحنا ماشيين نقارن بيهم ونحدثهم. كده حلينا المسألة في $O(N)$ عن طريق إننا حللنا الـ Brute force ولقينا Optimization.

---

Corrections & Enhancements

• الـ Correction: الـ int في معظم الأنظمة الحديثة حجمه 4 Bytes، وبالتالي بيحجز 4 خلايا (Cells) متتالية في الـ Memory وليس خلية واحدة.
• الـ Advanced Topics: في مسألة الـ Climbing Stairs، الحل الـ Recursive البسيط بيؤدي إلى Time Complexity $O(2^N)$ بسبب الـ Overlapping Subproblems (تكرار حساب نفس القيم عدة مرات في شجرة الاستدعاء). الطريقة المتقدمة والفعالة لحل هذه المشكلة هي استخدام الـ Dynamic Programming (Memoization) عن طريق حفظ النواتج التي تم حسابها في مصفوفة (Array) لتجنب إعادة حسابها، مما يقلل الـ Time Complexity إلى $O(N)$.