هنطلع من الدرس بإيه؟
الهدف إنك تتعلم طريقة تفكير مش حفظ حلول: تفهم المسألة، تكتب brute force صحيح، تحدد الجزء المتكرر اللي بيضيّع وقت، وتختار data structure أو pattern يحذفه، وبعدين تشرح الـ Big O بالسبب.
- تحل 8 مسائل من patterns مختلفة بـ C#.
- تحسب time و space complexity بالعد مش بالحفظ.
- تحدد edge cases قبل ما تكتب الكود.
- تتأكد من صحة الحل بمقارنته بـ brute force على مدخلات عشوائية.
المتطلبات: Data Structures & Algorithms (النظرية). الدرس ده هو الجانب التطبيقي.
المنهج: 5 خطوات قبل أي كود
- افهم: إيه المدخلات والمخرجات؟ هل فيه تكرار؟ سالب؟ فاضي؟
- أمثلة: جرّب مثال صغير على الورق.
- Brute force: اكتب أبسط حل صحيح وحدد تعقيده.
- التحسين: فين العمل المتكرر؟ هل data structure تحذفه؟
- تحقق: edge cases ومقارنة بالـ brute force.
Big O بالعد: لو عندك loop من 1 لـ n وجواه loop من 1 لـ n → n×n عملية = O(n²). لو الـ loop بتقسم المدى على 2 كل مرة → عدد الدورات = log₂ n (لأن 2^k = n). لو بتخزن n عنصر في hash table → space O(n). الأرقام مش «سحر»: كل واحد جاي من عدّ العمليات.
الأنماط في رسمة: Two pointers و Sliding window و BFS
الرسمة دي ملخص بصري للأنماط اللي هتتكرر في المسائل الجاية. لما تقرأ مسألة، اسأل نفسك: أنهي شكل فيهم بيوصف حركة البحث؟
1 · Two Sum (Hash Table) — Easy
المسألة: مصفوفة nums وهدف target؛ رجّع index عنصرين مجموعهم = target (يفترض وجود حل واحد). Brute force: جرّب كل زوج: n(n−1)/2 مقارنة = O(n²) وقت، O(1) مساحة. التحسين: لكل عنصر x، المطلوب target−x. لو خزّنت العناصر اللي عدّيت عليها في Dictionary (قيمة → index)، البحث عن المكمّل بيبقى O(1) متوسط: مرور واحد = O(n) وقت، O(n) مساحة (نبادل مساحة بوقت).
public static int[] TwoSum(int[] nums, int target)
{
var seen = new Dictionary<int, int>(); // value -> index
for (int i = 0; i < nums.Length; i++)
{
int need = target - nums[i];
if (seen.TryGetValue(need, out int j)) return new[] { j, i };
seen[nums[i]] = i; // بنضيف بعد الفحص: عشان ما نستخدمش نفس العنصر مرتين
}
return Array.Empty<int>(); // مفيش حل
}Edge cases: تكرار القيم ([3,3] و target 6: بنضيف بعد الفحص فبيشتغل)، سالب، مصفوفة فاضية. Trace لـ [2,7,11,15] و target 9: i=0 need=7 (مش موجود) نخزن 2→0؛ i=1 need=2 موجود عند 0 → [0,1].
2 · Valid Parentheses (Stack) — Easy
المسألة: نص فيه ()[]{}؛ هل الأقواس متوازنة ومقفولة بالترتيب الصح؟ الملاحظة: آخر قوس اتفتح لازم يكون أول واحد يتقفل (LIFO) → Stack. Brute force: امسح الأزواج المتجاورة () [] {} بشكل متكرر لحد ما النص ما يتغيرش: كل مسح O(n) وممكن n/2 مرة = O(n²). التحسين: مرور واحد: O(n) وقت، O(n) مساحة (أسوأ حالة كلها أقواس فتح).
public static bool IsValid(string s)
{
var stack = new Stack<char>();
foreach (char c in s)
{
if (c is '(' or '[' or '{') stack.Push(c);
else
{
if (stack.Count == 0) return false; // قفل من غير فتح
char open = stack.Pop();
if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
}
}
return stack.Count == 0; // لازم ما يفضلش أقواس مفتوحة
}Edge cases: نص فاضي (true)، "(" (false بسبب الـ Count)، ")(" (false).
3 · Binary Search — Easy
المسألة: مصفوفة مرتبة وقيمة؛ رجّع الـ index أو −1. Brute force: مسح خطي O(n). التحسين: قارن بالمنتصف وارمِ نصف المدى: بعد k خطوة المدى n/2^k، ويقف لما يوصل 1 → k ≈ log₂ n، فـ O(log n) وقت و O(1) مساحة. مثال: n = 1,000,000 → حوالي 20 مقارنة.
public static int Search(int[] a, int target)
{
int lo = 0, hi = a.Length - 1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2; // مش (lo+hi)/2 عشان تتجنب overflow
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1; else hi = mid - 1;
}
return -1;
}Edge cases: مصفوفة فاضية (الـ loop ما بتشتغلش)، عنصر واحد، الهدف أصغر/أكبر من كل العناصر. الخطأ الشائع: lo < hi بدل <= فتفوّت عنصر.
4 · Container With Most Water (Two Pointers) — Medium
المسألة: أعمدة بارتفاعات h؛ اختار عمودين بحيث المساحة بينهم (العرض × الأقصر) أكبر ما يمكن. Brute force: كل زوج = O(n²). التحسين: ابدأ بأوسع زوج (أول وآخر عمود). المساحة محكومة بالأقصر؛ تحريك الأطول لجوه بيقلل العرض ومش هيزود الارتفاع (لسه محكوم بالأقصر) فمفيش فايدة. لازم نحرّك المؤشر على الأقصر أملاً في عمود أطول. كل خطوة بتتخلص من عمود → n−1 خطوة: O(n) وقت، O(1) مساحة.
public static int MaxArea(int[] h)
{
int l = 0, r = h.Length - 1, best = 0;
while (l < r)
{
best = Math.Max(best, (r - l) * Math.Min(h[l], h[r]));
if (h[l] < h[r]) l++; else r--; // حرّك الأقصر
}
return best;
}5 · Longest Substring Without Repeating (Sliding Window) — Medium
المسألة: أطول substring من غير حروف متكررة. Brute force: كل substring وفحص التكرار: O(n³) (أو O(n²) لو بنوقف عند أول تكرار). التحسين: نافذة [left, right] بنوسّعها يمين، ولو الحرف الجديد موجود جوه النافذة بنخلي left يعدي آخر ظهور له. كل مؤشر بيمشي للأمام بس: O(n) وقت، O(min(n, k)) مساحة (k حجم الـ alphabet).
public static int LengthOfLongestSubstring(string s)
{
var last = new Dictionary<char, int>(); // char -> آخر index
int left = 0, best = 0;
for (int right = 0; right < s.Length; right++)
{
if (last.TryGetValue(s[right], out int prev) && prev >= left) left = prev + 1;
last[s[right]] = right;
best = Math.Max(best, right - left + 1);
}
return best;
}الشرط prev >= left مهم: ممكن الحرف يكون ظهر قبل بداية النافذة الحالية فمايتحسبش تكرار.
6 · Shortest Path in a Grid (BFS) — Medium
المسألة: شبكة 0/1 (1 = حاجز)؛ أقصر مسار من (0,0) لآخر خلية بحركات 4 اتجاهات. ليه BFS؟ لأن كل حركة تكلفتها 1، فالـ BFS بيزور الخلايا بترتيب المسافة، وأول مرة بيوصل للهدف تبقى هي الأقصر. DFS مش بيضمن الأقصر. Brute force: استكشاف كل المسارات الممكنة (أسي). BFS: كل خلية تتزار مرة واحدة × 4 جيران: O(R·C) وقت، O(R·C) مساحة للـ queue و visited.
public static int ShortestPath(int[][] g)
{
int R = g.Length, C = g[0].Length;
if (g[0][0] == 1 || g[R - 1][C - 1] == 1) return -1;
var q = new Queue<(int r, int c, int d)>();
var seen = new bool[R, C];
q.Enqueue((0, 0, 1)); seen[0, 0] = true; // المسافة = عدد الخلايا في المسار
int[] dr = { 1, -1, 0, 0 }, dc = { 0, 0, 1, -1 };
while (q.Count > 0)
{
var (r, c, d) = q.Dequeue();
if (r == R - 1 && c == C - 1) return d;
for (int k = 0; k < 4; k++)
{
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= R || nc >= C || g[nr][nc] == 1 || seen[nr, nc]) continue;
seen[nr, nc] = true; // علّم وقت الـ enqueue مش الـ dequeue عشان ما تتكررش
q.Enqueue((nr, nc, d + 1));
}
}
return -1;
}Edge cases: شبكة 1×1 (المسافة 1)، البداية أو النهاية حاجز، مفيش مسار.
7 · Coin Change (Basic DP) — Medium
المسألة: أقل عدد عملات لتكوين مبلغ amount (أو −1). Greedy بيفشل: للعملات {1,3,4} والمبلغ 6، الـ greedy يختار 4+1+1 (3 عملات) لكن الأفضل 3+3 (2). Brute force: recursion بتجرب كل عملة لكل مبلغ فرعي → أسي لأن نفس المبلغ الفرعي بيتحسب مرات كتير. DP: dp[a] = أقل عدد عملات للمبلغ a. dp[a] = 1 + min(dp[a − coin]) على كل العملات. عدد الحالات = amount، وكل حالة بتجرب k عملة: O(amount × k) وقت، O(amount) مساحة.
public static int CoinChange(int[] coins, int amount)
{
var dp = new int[amount + 1];
Array.Fill(dp, amount + 1); // "لانهاية" أكبر من أي إجابة ممكنة
dp[0] = 0;
for (int a = 1; a <= amount; a++)
foreach (int c in coins)
if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
return dp[amount] > amount ? -1 : dp[amount];
}8 · Merge Intervals (Sorting) — Medium
المسألة: دمج الفترات المتداخلة. Brute force: قارن كل فترة بكل فترة وكرر لحد الثبات: O(n²) أو أسوأ. التحسين: رتّب بالبداية (O(n log n))، وبعدين مرور واحد: لو بداية الفترة الحالية ≤ نهاية آخر فترة مدموجة ندمجهم، وإلا نبدأ فترة جديدة. الوقت الكلي محكوم بالترتيب O(n log n)، والمساحة O(n) للنتيجة.
public static int[][] Merge(int[][] intervals)
{
if (intervals.Length == 0) return Array.Empty<int[]>();
var sorted = intervals.OrderBy(i => i[0]).ToArray();
var result = new List<int[]>{ new[] { sorted[0][0], sorted[0][1] } };
foreach (var cur in sorted.Skip(1))
{
var last = result[^1];
if (cur[0] <= last[1]) last[1] = Math.Max(last[1], cur[1]); // تداخل (أو تلامس)
else result.Add(new[] { cur[0], cur[1] });
}
return result.ToArray();
}إزاي وصلنا للحل؟ مسار التفكير لكل مسألة
الحفظ مش هيفيدك في الإنترفيو: المسألة هتيجي بشكل مختلف. اللي بينفع هو إنك تعرف الإشارات في نص المسألة اللي بتوديك لنمط معين، وتعرف تمشي من الـ brute force للحل المحسّن بخطوات منطقية. لكل مسألة من الثمانية فوق، ده المسار اللي المفروض تقوله بصوت عالي.
| الإشارة في المسألة | النمط اللي بتفكر فيه أول حاجة |
|---|---|
| «زوج/مكمّل/شفته قبل كده؟» | Hash map (قيمة → index أو عدد) |
| أقواس، «آخر حاجة اتفتحت»، undo | Stack |
| مصفوفة مرتبة، «أصغر قيمة تحقق شرط» | Binary search (على الـ index أو على الإجابة) |
| مصفوفة، طرفين، «أقصى/أقل مسافة أو مساحة» | Two pointers |
| «أطول/أقصر substring/subarray متصل بشرط» | Sliding window |
| «أقل عدد خطوات» على grid/graph بدون أوزان | BFS |
| «عدد طرق/أقل تكلفة» + اختيارات بتتكرر | Dynamic programming |
| فترات (start, end)، تداخل | Sort بالبداية ثم مرور واحد |
1 · Two Sum: من «جرّب كل الأزواج» لـ «افتكر اللي شفته»
- Brute force وتكلفته: زوجين متداخلين = O(n²). مع n = 10⁵ ده 5×10⁹ عملية — مرفوض.
- إيه اللي بيتكرر؟ لكل عنصر بنسأل نفس السؤال: «هل المكمّل موجود قبلي؟». السؤال «موجود؟» = lookup.
- أسرع lookup: hash set/map = O(1) متوسط. ومحتاجين الـ index مش القيمة بس ← map.
- الـ invariant: قبل ما نعالج i، الـ map فيها كل العناصر من 0 لـ i−1. عشان كده بنفحص قبل ما نضيف (ما نستخدمش العنصر مع نفسه).
- بديل يستاهل يتقال: لو المصفوفة مرتبة أو مسموح نرتب ونرجّع القيم مش الـ indices، two pointers بـ O(n log n) و O(1) مساحة إضافية.
2 · Valid Parentheses: «آخر واحد اتفتح لازم أول واحد يتقفل»
- جرّب بإيدك على
([)]: العد لوحده (عدد الفتح = عدد القفل) بيقول صح، وده غلط. يبقى الترتيب مهم. - «آخر مفتوح أول مقفول» = LIFO = stack.
- القواعد: فتح ← push. قفل ← لازم الـ stack مش فاضي والـ top هو المقابل، وإلا false. في الآخر الـ stack لازم يبقى فاضي.
- Edge cases تقولها قبل ما المحاور يسأل: نص فاضي (true)، أول حرف قفل، فتح بس من غير قفل.
- التعقيد: O(n) وقت، O(n) مساحة في أسوأ حالة (كله فتح).
3 · Binary Search: الـ invariant قبل الكود
- «مرتبة» = إشارة قوية. كل مقارنة بتشيل نص الاحتمالات ← O(log n).
- أغلب الأخطاء في الحدود. اختار شكل واحد والتزم بيه:
[lo, hi]مقفولة من الناحيتين ←while (lo <= hi)، وhi = mid − 1/lo = mid + 1. - الـ invariant: «لو الهدف موجود، فهو جوه [lo, hi]». كل خطوة لازم تحافظ عليه.
mid = lo + (hi − lo) / 2يتجنب overflow في لغات بـ int ثابت الحجم.- التعميم المهم: «أصغر x يحقق شرط monotonic» (أقل سعة شاحنة تشحن في D أيام) = binary search على الإجابة نفسها مش على مصفوفة.
4 · Container With Most Water: ليه نحرّك المؤشر الأقصر؟
- Brute force: كل زوج O(n²). المساحة = min(h[i], h[j]) × (j − i).
- ابدأ بأوسع عرض: i = 0، j = n−1. أي حركة هتقلل العرض، فالأمل الوحيد إن الارتفاع الأصغر يزيد.
- الإثبات بالكلام: لو h[i] < h[j]، أي container بيستخدم i مع أي j' < j هيبقى عرضه أقل وارتفاعه ≤ h[i] — يعني مش ممكن يغلب الحالي. فـ i «خلص» ونقدر نرميه بأمان. ده اللي بيبرر الـ greedy.
- كل خطوة بترمي عنصر واحد ← O(n).
- المحاور غالبًا بيسأل «ليه مش بنحرك الأطول؟» — الإثبات فوق هو الإجابة.
5 · Longest Substring Without Repeating: نافذة بتتمد وتنكمش
- «substring متصل» + «أطول بشرط» = sliding window.
- Brute force: كل substring O(n²) وفحص التكرار O(n) ← O(n³).
- النافذة [left, right] فيها حروف مش متكررة (الـ invariant). مد right؛ لو الحرف الجديد موجود في النافذة، حرّك left لبعد آخر ظهور ليه.
- map من الحرف لآخر index بيخلي القفزة O(1) بدل ما نحرك left واحدة واحدة. انتبه:
left = max(left, last[c] + 1)— آخر ظهور ممكن يكون قبل النافذة الحالية. - كل index بيدخل ويخرج مرة ← O(n). المساحة O(حجم الأبجدية).
6 · Shortest Path in a Grid: ليه BFS مش DFS؟
- «أقل عدد خطوات» وكل خطوة بنفس التكلفة ← BFS بيزور الخلايا بترتيب المسافة: أول مرة توصل للهدف = أقصر مسار.
- DFS ممكن يلاقي مسار طويل الأول، ولازم يستكشف كله عشان يتأكد ← أبطأ وأصعب.
- علّم الخلية visited لما تدخلها الـ queue مش لما تطلعها — وإلا نفس الخلية تتضاف كذا مرة.
- لو الخطوات بأوزان مختلفة ← Dijkstra (priority queue). لو أوزان 0/1 بس ← 0-1 BFS بـ deque.
- O(R×C) وقت ومساحة.
7 · Coin Change: من recursion لـ DP
- عرّف المسألة الصغيرة:
f(a)= أقل عدد عملات لعمل المبلغ a. - العلاقة:
f(a) = 1 + min(f(a − c))لكل عملة c ≤ a، وf(0) = 0. - Recursion مباشر بيحسب نفس f(a) آلاف المرات (subproblems متداخلة) ← memoization أو جدول من 0 لـ amount.
- ليه greedy (أكبر عملة الأول) غلط؟ عملات {1, 3, 4} ومبلغ 6: greedy = 4+1+1 (3 عملات)، الأمثل 3+3 (2). مثال مضاد واحد كفاية تقوله.
- O(amount × عدد العملات) وقت، O(amount) مساحة. التفاصيل والأنماط الأوسع في درس Dynamic Programming.
8 · Merge Intervals: الترتيب بيحوّل المسألة لمرور واحد
- من غير ترتيب، كل interval محتاج يتقارن بالكل ← O(n²).
- بعد الترتيب بالبداية، أي interval ممكن يتداخل مع آخر واحد في النتيجة بس — مش مع اللي قبله.
- القاعدة: لو
start ≤ last.end←last.end = max(last.end, end)، وإلا ضيف جديد. الـ max مهم:[1,10]ثم[2,3]. - O(n log n) بسبب الترتيب. اسأل: هل الحدود المتلامسة (
[1,2]و[2,3]) تعتبر تداخل؟ سؤال توضيح بيكسبك نقط.
اقرأ الـ constraints: هي بتقولك التعقيد المطلوب
| n تقريبًا | التعقيد المقبول (≈10⁸ عملية/ثانية) | غالبًا |
|---|---|---|
| ≤ 20 | O(2ⁿ)، O(n!) | backtracking، كل الـ subsets |
| ≤ 500 | O(n³) | DP على فترات، Floyd–Warshall |
| ≤ 5,000 | O(n²) | DP ثنائي الأبعاد، كل الأزواج |
| ≤ 10⁵ – 10⁶ | O(n log n) أو O(n) | sorting، heap، two pointers، hashing، segment tree |
| ≥ 10⁹ | O(log n) أو O(1) | binary search على الإجابة، رياضة |
دي أول حاجة تعملها قبل ما تفكر في الحل: لو n = 10⁵ وفكرتك O(n²)، ابحث عن حاجة أحسن قبل ما تكتب. الشرح الأعمق للـ Big-O والـ amortized analysis في Range Queries & Complexity.
تحقق من منطق الخوارزميات: brute force مقابل المحسّن
مفيش .NET SDK في بيئة بناء الموسوعة، فحلول C# فوق Not Executed. اللي اتنفّذ فعلاً هو نسخة Python بنفس الخوارزميات ومقارنتها بالـ brute force على آلاف المدخلات العشوائية. ده بيثبت صحة الفكرة (مش كود C# نفسه): لو طلعت اختلاف في حلك بـ C#، قارنه بالمنطق ده.
import random
from collections import deque
def two_sum_fast(a, t):
seen = {}
for i, x in enumerate(a):
if t - x in seen: return (seen[t - x], i)
seen[x] = i
def two_sum_brute(a, t):
return next(((i, j) for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] + a[j] == t), None)
def max_area_fast(h):
l, r, best = 0, len(h) - 1, 0
while l < r:
best = max(best, (r - l) * min(h[l], h[r]))
if h[l] < h[r]: l += 1
else: r -= 1
return best
def max_area_brute(h):
return max((j - i) * min(h[i], h[j]) for i in range(len(h)) for j in range(i + 1, len(h)))
def longest_fast(s):
last, left, best = {}, 0, 0
for r, ch in enumerate(s):
if ch in last and last[ch] >= left: left = last[ch] + 1
last[ch] = r; best = max(best, r - left + 1)
return best
def longest_brute(s):
return max((j - i for i in range(len(s) + 1) for j in range(i, len(s) + 1) if len(set(s[i:j])) == j - i), default=0)
def coin_fast(coins, amt):
dp = [amt + 1] * (amt + 1); dp[0] = 0
for a in range(1, amt + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]: dp[a] = dp[a - c] + 1
return -1 if dp[amt] > amt else dp[amt]
def coin_brute(coins, amt):
best = [None]
def go(rem, used):
if rem == 0: best[0] = used if best[0] is None else min(best[0], used); return
for c in coins:
if c <= rem and (best[0] is None or used + 1 < best[0]): go(rem - c, used + 1)
go(amt, 0); return -1 if best[0] is None else best[0]
def merge_fast(iv):
out = []
for s, e in sorted(iv):
if out and s <= out[-1][1]: out[-1][1] = max(out[-1][1], e)
else: out.append([s, e])
return out
def merge_brute(iv):
pts = set()
for s, e in iv: pts.update(range(s * 2, e * 2 + 1)) # نقط بنص وحدة عشان التلامس
res, cur = [], None
for p in sorted(pts):
if cur and p == cur[1] + 1: cur[1] = p
elif cur is None or p > cur[1] + 1:
if cur: res.append(cur)
cur = [p, p]
if cur: res.append(cur)
return [[a // 2, b // 2] for a, b in res]
def bfs(g):
R, C = len(g), len(g[0])
if g[0][0] or g[R-1][C-1]: return -1
q, seen = deque([(0, 0, 1)]), {(0, 0)}
while q:
r, c, d = q.popleft()
if (r, c) == (R-1, C-1): return d
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
n = (r+dr, c+dc)
if 0 <= n[0] < R and 0 <= n[1] < C and not g[n[0]][n[1]] and n not in seen:
seen.add(n); q.append((n[0], n[1], d+1))
return -1
def dfs_all_paths_min(g): # brute force: كل المسارات البسيطة
R, C = len(g), len(g[0]); best = [-1]
def go(r, c, vis, d):
if (r, c) == (R-1, C-1):
best[0] = d if best[0] == -1 else min(best[0], d); return
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r+dr, c+dc
if 0 <= nr < R and 0 <= nc < C and not g[nr][nc] and (nr, nc) not in vis:
go(nr, nc, vis | {(nr, nc)}, d+1)
if g[0][0] or g[R-1][C-1]: return -1
go(0, 0, {(0, 0)}, 1); return best[0]
random.seed(7)
checks = {"two_sum": 0, "max_area": 0, "longest_unique": 0, "coin_change": 0, "merge_intervals": 0, "grid_bfs": 0}
for _ in range(400):
a = [random.randint(-5, 9) for _ in range(random.randint(2, 9))]; t = random.randint(-5, 15)
f, b = two_sum_fast(a, t), two_sum_brute(a, t)
assert (f is None) == (b is None) and (f is None or a[f[0]] + a[f[1]] == t); checks["two_sum"] += 1
h = [random.randint(0, 9) for _ in range(random.randint(2, 10))]
assert max_area_fast(h) == max_area_brute(h); checks["max_area"] += 1
s = "".join(random.choice("abcd") for _ in range(random.randint(0, 9)))
assert longest_fast(s) == longest_brute(s); checks["longest_unique"] += 1
coins = random.sample([1, 2, 3, 4, 5, 7], random.randint(1, 3)); amt = random.randint(0, 14)
assert coin_fast(coins, amt) == coin_brute(coins, amt); checks["coin_change"] += 1
iv = [[x, x + random.randint(0, 4)] for x in [random.randint(0, 12) for _ in range(random.randint(0, 6))]]
assert merge_fast(iv) == merge_brute(iv); checks["merge_intervals"] += 1
g = [[1 if random.random() < 0.3 else 0 for _ in range(4)] for _ in range(4)]
assert bfs(g) == dfs_all_paths_min(g); checks["grid_bfs"] += 1
print("all cross-checks passed (fast == brute force):")
for k, v in checks.items(): print(f" {k:16s} {v} random cases")
print("greedy counter-example: coins [1,3,4], amount 6 ->", coin_fast([1, 3, 4], 6), "coins (greedy would use 3)")all cross-checks passed (fast == brute force):
two_sum 400 random cases
max_area 400 random cases
longest_unique 400 random cases
coin_change 400 random cases
merge_intervals 400 random cases
grid_bfs 400 random cases
greedy counter-example: coins [1,3,4], amount 6 -> 2 coins (greedy would use 3)أخطاء شائعة
- كتابة الحل المحسّن قبل ما يكون عندك brute force صحيح تقارن بيه.
- تحريك المؤشر الغلط في two pointers (لازم الأقصر).
- تعليم
visitedوقت الـ dequeue في BFS فتدخل نفس الخلية الـ queue أكتر من مرة. - استخدام greedy لمسائل العملات بدون إثبات.
- نسيان الحالات الحدية: فاضي، عنصر واحد، تكرار، سالب.
- ذكر Big O من غير تبرير: «O(n)» لوحدها مش إجابة.
خمس تمارين إضافية محلولة
1 (Easy): Contains Duplicate — حدد الحل والتعقيد
الحل: brute force: قارن كل زوج O(n²). الأفضل: HashSet<int>؛ لو Add رجّع false يبقى تكرار. O(n) وقت، O(n) مساحة. بديل بدون مساحة إضافية: رتّب O(n log n) وقارن المتجاورين.
2 (Easy): اعكس linked list — اشرح الـ pointers
الحل: محتاج 3 مؤشرات: prev=null, cur=head؛ في كل خطوة: احفظ next=cur.next، اعكس cur.next=prev، حرّك prev=cur; cur=next. O(n) وقت و O(1) مساحة. الخطأ الشائع إنك تنسى تحفظ next قبل ما تكسر الرابط.
3 (Intermediate): أقصى مجموع subarray (Kadane)
الحل: cur = max(x, cur + x) و best = max(best, cur). التفكير: لو المجموع التراكمي بقى سالب، البدء من جديد أحسن. O(n) وقت و O(1) مساحة. Edge: كل العناصر سالبة → الإجابة أكبر عنصر (ابدأ بـ best = a[0] مش 0).
4 (Intermediate): Level-order traversal لشجرة
الحل: BFS بـ Queue: في كل مستوى خد q.Count الحالي واعمل dequeue لعددهم وضيف أولادهم. O(n) وقت، O(w) مساحة (w أكبر عرض). الشجرة الفاضية ترجّع قائمة فاضية.
5 (Challenging): Top K Frequent Elements — قارن بين طريقتين
الحل: (1) عدّ بـ Dictionary O(n) ثم رتّب الـ keys بالتكرار O(u log u) (u عدد القيم المميزة). (2) عدّ ثم Min-Heap حجمه k: كل عنصر O(log k) فالإجمالي O(n + u log k)، أحسن لما k صغير. (3) bucket sort: مصفوفة بكتس حسب التكرار (التكرار ≤ n) فتبقى O(n). الاختيار حسب k و n؛ اشرح الـ trade-off في الإنترفيو.
Mini Project: مكتبة اختبارات خوارزميات
اعمل solution C# فيها class library Algos ومشروع xUnit. نفّذ المسائل الثمانية، واكتب لكل واحدة: اختبارات للـ edge cases، واختبار property-based بسيط يقارن الحل المحسّن بالـ brute force على 1000 مدخل عشوائي (Random بـ seed ثابت). معيار النجاح: dotnet test أخضر، وكل class فيه تعليق بالـ Time/Space complexity ومبرراتهم.
أسئلة إنترفيو
ليه HashMap بيحسّن Two Sum؟ وإيه التكلفة؟
إمتى BFS ومتى DFS؟
ليه lo + (hi - lo) / 2؟
إيه الفرق بين Greedy و DP؟
ليه sliding window O(n) رغم وجود loop جوه loop أحيانًا؟
(أصعب) اشرح ليه Merge Intervals O(n log n) مش O(n)
المراجع والقراءة الإضافية
الدرس بيشرح الفكرة نفسها؛ الروابط دي للتحقق والتعمق والرجوع لتفاصيل الـ API. (محتاجة إنترنت.)
التوثيق الرسمي — Official documentation
خلصت الدرس وحليت الأسئلة؟ علّم عليه عشان يتحسب في تقدّمك.