هنطلع من الدرس بإيه؟
نكمّل الجزء الأول بالـ structures اللي ناقصة: linked list و stack و tree و heap و graph. الهدف نفسه: تفكير + brute force + تحسين + تعقيد مبرر.
- تحل 8 مسائل على structures مختلفة بـ C#.
- تشرح complexity بالعدّ (مثلاً ليه build heap = O(n) مش O(n log n) في الحالة العامة، وليه DFS = O(V+E)).
- تحدد edge cases: قائمة فاضية، شجرة بعنصر، graph فيه cycle.
- تتحقق من الفكرة بمقارنة بـ brute force.
تنبيه الصدق: كود C# هنا Not Executed. اللي اتنفّذ نسخة Python بنفس الخوارزميات على مدخلات عشوائية.
الـ pointers والأشجار والـ graphs في رسمة
1 · Reverse Linked List + Detect Cycle — Easy/Medium
Reverse: محتاج 3 مؤشرات (prev, cur, next). كل node بيتزار مرة: O(n) وقت، O(1) مساحة. Cycle: brute force: خزّن الـ nodes في HashSet (O(n) مساحة). التحسين: Floyd — مؤشر بطيء (خطوة) وسريع (خطوتين)؛ لو في cycle هيتقابلوا لأن السريع بيقفل المسافة بينهم بمقدار 1 كل خطوة. O(n) وقت، O(1) مساحة.
public class ListNode { public int Val; public ListNode? Next; public ListNode(int v) => Val = v; }
public static ListNode? Reverse(ListNode? head)
{
ListNode? prev = null, cur = head;
while (cur != null)
{
var next = cur.Next; // احفظ التالي قبل ما تكسر الرابط
cur.Next = prev;
prev = cur; cur = next;
}
return prev;
}
public static bool HasCycle(ListNode? head)
{
ListNode? slow = head, fast = head;
while (fast?.Next != null)
{
slow = slow!.Next; fast = fast.Next.Next;
if (ReferenceEquals(slow, fast)) return true;
}
return false;
}Edge cases: قائمة فاضية، node واحد، cycle يشاور على نفسه.
2 · Min Stack — Medium
المسألة: stack بيدعم Push/Pop/Top/GetMin كلها O(1). Brute force: GetMin بمسح كل العناصر = O(n). التحسين: stack تاني (أو زوج) بيحتفظ بالـ minimum الحالي عند كل مستوى. كل عملية O(1)، مساحة إضافية O(n).
public class MinStack
{
private readonly Stack<(int val, int min)> _s = new();
public void Push(int x) => _s.Push((x, _s.Count == 0 ? x : Math.Min(x, _s.Peek().min)));
public int Pop() => _s.Pop().val; // InvalidOperationException لو فاضي
public int Top() => _s.Peek().val;
public int GetMin() => _s.Peek().min;
}3 · Validate BST + Level Order — Medium
Validate BST: الخطأ الشائع: مقارنة الـ node بأولاده المباشرين فقط. القاعدة: كل node لازم يكون ضمن مدى (min, max) موروث من الأجداد. O(n) وقت، O(h) مساحة (عمق الـ recursion). تحذير: الـ recursion العميقة على شجرة منحرفة (n = مئات الآلاف) ممكن تعمل stack overflow؛ بدّلها بـ stack صريح لو لازم.
public class TreeNode { public int Val; public TreeNode? Left, Right; public TreeNode(int v) => Val = v; }
public static bool IsValidBst(TreeNode? n, long min = long.MinValue, long max = long.MaxValue)
{
if (n == null) return true;
if (n.Val <= min || n.Val >= max) return false; // long عشان int.MinValue كقيمة صحيحة
return IsValidBst(n.Left, min, n.Val) && IsValidBst(n.Right, n.Val, max);
}
public static IList<IList<int>> LevelOrder(TreeNode? root)
{
var res = new List<IList<int>>();
if (root == null) return res;
var q = new Queue<TreeNode>(); q.Enqueue(root);
while (q.Count > 0)
{
int size = q.Count; var level = new List<int>(size);
for (int i = 0; i < size; i++)
{
var n = q.Dequeue(); level.Add(n.Val);
if (n.Left != null) q.Enqueue(n.Left);
if (n.Right != null) q.Enqueue(n.Right);
}
res.Add(level);
}
return res;
}4 · Kth Largest (Heap) — Medium
Brute force: رتّب كله O(n log n) وخد العنصر k. التحسين: min-heap حجمه k: كل عنصر جديد أكبر من الجذر بيستبدله. كل عملية heap = O(log k) فالإجمالي O(n log k) وقت، O(k) مساحة. مفيد جدًا لما n ضخم (stream) و k صغير.
public static int KthLargest(int[] nums, int k)
{
if (k < 1 || k > nums.Length) throw new ArgumentOutOfRangeException(nameof(k));
var heap = new PriorityQueue<int, int>(); // min-heap: العنصر الأصغر أولاً
foreach (var x in nums)
{
if (heap.Count < k) heap.Enqueue(x, x);
else if (x > heap.Peek()) { heap.Dequeue(); heap.Enqueue(x, x); }
}
return heap.Peek();
}5 · Number of Islands (Graph DFS/BFS) — Medium
كل خلية '1' هي node، والجيران الأربعة edges. بنعد الـ connected components: لكل '1' لسه ما اتزارتش نزوّر كل الجزيرة ونعلّمها. كل خلية بتتزار مرة والجيران 4 ثابتة: O(R·C) وقت. Brute force لا يفيد هنا (الحل الطبيعي هو الـ traversal). نستخدم stack صريح بدل recursion لتجنب overflow.
public static int NumIslands(char[][] grid)
{
if (grid.Length == 0) return 0;
int R = grid.Length, C = grid[0].Length, count = 0;
var dirs = new (int, int)[] { (1, 0), (-1, 0), (0, 1), (0, -1) };
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
{
if (grid[r][c] != '1') continue;
count++;
var st = new Stack<(int, int)>(); st.Push((r, c)); grid[r][c] = '0'; // علّم عند الإدخال
while (st.Count > 0)
{
var (cr, cc) = st.Pop();
foreach (var (dr, dc) in dirs)
{
int nr = cr + dr, nc = cc + dc;
if (nr >= 0 && nc >= 0 && nr < R && nc < C && grid[nr][nc] == '1') { grid[nr][nc] = '0'; st.Push((nr, nc)); }
}
}
}
return count;
}ملاحظة: الحل بيعدّل الـ input. لو ممنوع، استخدم bool[,] seen (مساحة O(R·C)).
6 · Course Schedule (Topological Sort) — Medium
المسألة: n مقررات ومتطلبات سابقة؛ هل ممكن تخلصهم كلهم؟ يعني: هل الـ directed graph من غير cycle؟ Kahn's algorithm: احسب in-degree، ابدأ بالـ nodes اللي in-degree = 0، شيلهم وقلل in-degree للجيران. لو عدد اللي اتشالوا = n يبقى مفيش cycle. O(V+E) وقت و O(V+E) مساحة.
public static bool CanFinish(int n, int[][] prereqs) // prereq = [course, mustTakeFirst]
{
var adj = new List<int>[n]; for (int i = 0; i < n; i++) adj[i] = new();
var indeg = new int[n];
foreach (var p in prereqs) { adj[p[1]].Add(p[0]); indeg[p[0]]++; }
var q = new Queue<int>(); for (int i = 0; i < n; i++) if (indeg[i] == 0) q.Enqueue(i);
int done = 0;
while (q.Count > 0)
{
int u = q.Dequeue(); done++;
foreach (var v in adj[u]) if (--indeg[v] == 0) q.Enqueue(v);
}
return done == n;
}7 · Subsets (Backtracking/Recursion) — Medium
لكل عنصر قرارين: ندخله أو لأ → 2ⁿ subset. ده أسي بطبيعة المسألة (حجم الخرج نفسه 2ⁿ)، فمفيش حل أسرع من O(n·2ⁿ) (النسخ). Backtracking: ندخل عنصر، نكمل، نشيله (undo) ونكمل بدونه. أهم نقطة: لما نضيف النتيجة لازم ننسخ القائمة الحالية.
public static IList<IList<int>> Subsets(int[] nums)
{
var res = new List<IList<int>>(); var cur = new List<int>();
void Go(int i)
{
if (i == nums.Length) { res.Add(new List<int>(cur)); return; } // انسخ! مش تضيف المرجع
cur.Add(nums[i]); Go(i + 1); // choose
cur.RemoveAt(cur.Count - 1); Go(i + 1); // un-choose ثم تخطّى
}
Go(0);
return res;
}8 · LRU Cache (Hash Map + Doubly Linked List) — Medium
المطلوب Get/Put بـ O(1). Dictionary للوصول السريع + linked list مزدوجة لترتيب الاستخدام (الأحدث في الأول). عند الـ Get ننقل الـ node للأول؛ عند تجاوز السعة نحذف آخر node. في .NET استخدم LinkedList<T> مع LinkedListNode للحذف O(1).
public class LruCache<TK, TV> where TK : notnull
{
private readonly int _cap;
private readonly Dictionary<TK, LinkedListNode<(TK key, TV val)>> _map = new();
private readonly LinkedList<(TK key, TV val)> _order = new(); // First = most recently used
public LruCache(int capacity) { if (capacity < 1) throw new ArgumentOutOfRangeException(nameof(capacity)); _cap = capacity; }
public bool TryGet(TK key, out TV value)
{
if (_map.TryGetValue(key, out var node)) { _order.Remove(node); _order.AddFirst(node); value = node.Value.val; return true; }
value = default!; return false;
}
public void Put(TK key, TV value)
{
if (_map.TryGetValue(key, out var node)) { _order.Remove(node); }
else if (_map.Count == _cap) { var last = _order.Last!; _map.Remove(last.Value.key); _order.RemoveLast(); }
_map[key] = _order.AddFirst((key, value));
}
}ملاحظة: الكلاس ده مش thread-safe. في تطبيق ويب متعدد الـ threads لف الوصول بـ lock أو استخدم MemoryCache/IMemoryCache الجاهز.
إزاي وصلنا للحل؟ مسار التفكير لكل مسألة
نفس منهج الجزء الأول: إشارة ← نمط ← brute force ← نقطة الاختناق ← هيكل البيانات المناسب ← invariant ← edge cases. هنا المسائل فيها pointers وأشجار و graphs، فالرسم على الورق (أو الـ whiteboard) جزء من الحل مش رفاهية.
1 · Reverse Linked List + Detect Cycle
- Reverse: كل node محتاج يشاور على اللي قبله بدل اللي بعده. لو عكست
nextهتفقد الطريق لباقي القائمة ← احفظnextفي متغير قبل ما تعكس. تلات pointers: prev، curr، next. - الـ invariant: «من head لـ prev معكوس، ومن curr لآخر القائمة لسه زي ما هو».
- Cycle: brute force = HashSet للـ nodes اللي شفتها O(n) مساحة. المحاور بيطلب O(1) ← Floyd: slow خطوة، fast خطوتين. لو فيه دايرة، fast هيلحق slow (المسافة بينهم بتقل واحدة كل خطوة جوه الدايرة)، ولو مفيش fast هيوصل null.
- Edge cases: قائمة فاضية، node واحد، node بيشاور على نفسه.
2 · Min Stack: «افتكر الـ min في كل لحظة»
- الـ min الحالي ممكن يتشال بـ pop، ووقتها محتاج الـ min اللي قبله — يعني الـ min «تاريخ» مش قيمة واحدة.
- الفكرة: stack تاني (أو tuple مع كل عنصر) فيه الـ min لحد العنصر ده. push:
min(x, currentMin). pop: الاتنين مع بعض. - كل العمليات O(1)، والمساحة O(n). تحسين: الـ min stack ياخد العنصر بس لما يكون ≤ الـ min الحالي (انتبه للتكرار: ≤ مش <).
3 · Validate BST + Level Order
- الفخ: مقارنة كل node بأولاده المباشرين بس مش كفاية — node في الـ subtree اليمين لازم يكون أكبر من كل الأجداد اللي هو على يمينهم.
- الحل: مرّر حدود (min, max) نازلة: الشمال بياخد (min, node.val)، اليمين (node.val, max). أو inorder traversal لازم يطلع مرتب تصاعدي.
- استخدم
longأو nullable للحدود عشان قيم زيint.MinValue. - Level order: «طبقة طبقة» = BFS بـ queue؛ خد
count = queue.Countفي بداية كل level وعالجهم بس.
4 · Kth Largest: ليه min-heap بحجم k؟
- Sort كله O(n log n) — شغال، قوله الأول.
- محتاج أكبر k بس. min-heap بحجم k: الـ top هو أصغر واحد فيهم = الـ kth largest. أي عنصر أكبر منه يدخل ويطرده.
- O(n log k) — أحسن بكتير لما k صغير، ومناسب للـ streams (مش محتاج كل البيانات في الذاكرة).
- بديل: Quickselect متوسط O(n) بس أسوأ حالة O(n²) وبيعدل المصفوفة — اذكره كـ trade-off.
5 · Number of Islands
- «مجموعات متصلة» في grid = connected components ← كل ما تلاقي 1 مش متزار، ابدأ DFS/BFS يعلّم الجزيرة كلها، وزوّد العداد.
- كل خلية بتتزار مرة ← O(R×C).
- DFS recursive على grid كبير (10⁶ خلية) ممكن يعمل stack overflow ← BFS أو DFS بـ stack صريح.
- Follow-up شائع: الجزر بتتضاف ديناميكيًا ← Union-Find (disjoint set).
6 · Course Schedule (Topological Sort)
- «متطلبات قبل» = directed graph. «ينفع نخلص كل الكورسات؟» = هل فيه cycle؟
- Kahn's algorithm: احسب in-degree، ابدأ بكل اللي in-degree = 0، وكل ما تشيل node قلل in-degree جيرانه. لو عدد اللي اتشالوا < n ← فيه cycle.
- O(V + E). نفس الفكرة في الحياة الحقيقية: ترتيب migrations، build dependencies، خطوات workflow في الـ agents.
7 · Subsets (Backtracking)
- لكل عنصر قرارين: آخده أو لأ ← 2ⁿ نتيجة. مفيش أسرع من حجم الناتج نفسه، فالسؤال إزاي تولدهم بنضافة.
- Backtracking: اختار ← نزّل recursion ← تراجع عن الاختيار (remove). الـ «تراجع» هو اللي بيخلي list واحدة تكفي.
- انسخ الـ path لما تضيفه للنتيجة (
new List<int>(path)) — إضافة نفس الـ reference أشهر bug. - مع تكرار في الـ input: رتّب واتجاهل نفس القيمة في نفس المستوى.
8 · LRU Cache
- المطلوب get و put في O(1)، والطرد للأقدم استخدامًا.
- Lookup O(1) ← hash map. ترتيب الاستخدام مع نقل أي عنصر للأول في O(1) ← doubly linked list (تقدر تشيل node من النص لو معاك reference ليه).
- الـ map بيشاور على الـ nodes. get: انقل للأول. put: لو موجود حدّث وانقل، لو جديد ضيف في الأول ولو الحجم زاد اشيل الآخر (ومن الـ map كمان).
- Sentinel head/tail nodes بتلغي حالات null. وفي .NET الإنتاجي:
MemoryCacheبـ size limits، لكن الإنترفيو عايز يشوفك تبنيه.
إزاي تتكلم وانت بتحل: سكريبت 45 دقيقة
| الدقيقة | انت بتعمل إيه | جملة نموذجية |
|---|---|---|
| 0–5 | توضيح المسألة والحدود وأمثلة | «الـ graph ممكن يبقى فيه cycles؟ الـ nodes بأرقام من 0 لـ n−1؟» |
| 5–10 | brute force بتعقيده | «أبسط حل O(n²)؛ مع n = 10⁵ مش هيكفي، فهدور على O(n log n)» |
| 10–15 | الفكرة المحسنة + الـ invariant | «هستخدم min-heap بحجم k؛ الـ top دايمًا الـ kth largest لحد دلوقتي» |
| 15–35 | الكود بأسماء واضحة | «هعمل helper للـ neighbors عشان الحدود تبقى في مكان واحد» |
| 35–42 | trace على مثال + edge cases | «خليني أجرب الـ input الفاضي والـ node الواحد» |
| 42–45 | التعقيد النهائي وتحسينات | «O(V+E) وقت؛ لو الـ graph ضخم ممكن نعمل BFS بـ iterative عشان الـ stack» |
المحاور بيقيّم طريقة تفكيرك وتواصلك بنفس وزن الكود الصح. الصمت 10 دقايق ثم كود صح أضعف من تفكير مسموع وصل لحل شبه كامل.
تحقق منطق الخوارزميات (Python mirror) مقابل brute force
import heapq, itertools, random
from collections import OrderedDict, deque
random.seed(11)
# --- Floyd cycle detection vs visited-set
def make_list(n, cycle_to):
nxt = {i: i + 1 for i in range(n - 1)}
if n and cycle_to is not None: nxt[n - 1] = cycle_to
return nxt
def floyd(nxt, n):
if n == 0: return False
slow = fast = 0
while fast in nxt and nxt[fast] in nxt:
slow, fast = nxt[slow], nxt[nxt[fast]]
if slow == fast: return True
return False
def brute_cycle(nxt, n):
seen, cur = set(), 0
while cur is not None and n:
if cur in seen: return True
seen.add(cur); cur = nxt.get(cur)
return False
# --- Min stack vs recompute-min
class MinStack:
def __init__(self): self.s = []
def push(self, x): self.s.append((x, min(x, self.s[-1][1]) if self.s else x))
def pop(self): return self.s.pop()[0]
def get_min(self): return self.s[-1][1]
# --- BST validation: range check vs inorder strictly increasing
def valid_bst(t, lo=float("-inf"), hi=float("inf")):
if t is None: return True
v, l, r = t
return lo < v < hi and valid_bst(l, lo, v) and valid_bst(r, v, hi)
def inorder(t):
return [] if t is None else inorder(t[1]) + [t[0]] + inorder(t[2])
def rand_tree(depth):
if depth == 0 or random.random() < 0.25: return None
return (random.randint(0, 9), rand_tree(depth - 1), rand_tree(depth - 1))
# --- Kth largest heap vs sort
def kth_heap(nums, k):
h = []
for x in nums:
if len(h) < k: heapq.heappush(h, x)
elif x > h[0]: heapq.heapreplace(h, x)
return h[0]
# --- islands DFS vs union-find
def islands(grid):
g = [row[:] for row in grid]; R, C = len(g), len(g[0]); cnt = 0
for r in range(R):
for c in range(C):
if g[r][c] == 1:
cnt += 1; st = [(r, c)]; g[r][c] = 0
while st:
cr, cc = st.pop()
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = cr + dr, cc + dc
if 0 <= nr < R and 0 <= nc < C and g[nr][nc] == 1: g[nr][nc] = 0; st.append((nr, nc))
return cnt
def islands_uf(grid):
R, C = len(grid), len(grid[0]); p = list(range(R * C))
def f(x):
while p[x] != x: p[x] = p[p[x]]; x = p[x]
return x
for r in range(R):
for c in range(C):
if grid[r][c]:
for dr, dc in ((1,0),(0,1)):
nr, nc = r + dr, c + dc
if nr < R and nc < C and grid[nr][nc]: p[f(r*C+c)] = f(nr*C+nc)
return len({f(r*C+c) for r in range(R) for c in range(C) if grid[r][c]})
# --- course schedule Kahn vs DFS colouring
def kahn(n, pre):
adj = [[] for _ in range(n)]; indeg = [0]*n
for a, b in pre: adj[b].append(a); indeg[a] += 1
q = deque(i for i in range(n) if indeg[i] == 0); done = 0
while q:
u = q.popleft(); done += 1
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0: q.append(v)
return done == n
def dfs_acyclic(n, pre):
adj = [[] for _ in range(n)]
for a, b in pre: adj[b].append(a)
state = [0]*n
def go(u):
state[u] = 1
for v in adj[u]:
if state[v] == 1 or (state[v] == 0 and not go(v)): return False
state[u] = 2; return True
return all(state[i] == 2 or go(i) for i in range(n))
# --- subsets count and uniqueness
def subsets(nums):
res, cur = [], []
def go(i):
if i == len(nums): res.append(cur[:]); return
cur.append(nums[i]); go(i + 1); cur.pop(); go(i + 1)
go(0); return res
# --- LRU vs OrderedDict reference
class LRU:
def __init__(self, cap): self.cap, self.d = cap, OrderedDict()
def get(self, k):
if k not in self.d: return None
self.d.move_to_end(k, last=False); return self.d[k]
def put(self, k, v):
if k in self.d: self.d.move_to_end(k, last=False)
elif len(self.d) == self.cap: self.d.popitem(last=True)
self.d[k] = v; self.d.move_to_end(k, last=False)
counts = dict.fromkeys(["cycle", "min_stack", "bst", "kth_largest", "islands", "course_schedule", "subsets", "lru"], 0)
for _ in range(300):
n = random.randint(0, 8); cyc = random.choice([None] + list(range(max(n, 1))))
nxt = make_list(n, cyc if n else None)
assert floyd(nxt, n) == brute_cycle(nxt, n); counts["cycle"] += 1
ms, ref = MinStack(), []
for _ in range(12):
if ref and random.random() < 0.4: assert ms.pop() == ref.pop()
else: x = random.randint(-5, 5); ms.push(x); ref.append(x)
if ref: assert ms.get_min() == min(ref)
counts["min_stack"] += 1
t = rand_tree(4); io = inorder(t)
assert valid_bst(t) == all(a < b for a, b in zip(io, io[1:])); counts["bst"] += 1
nums = [random.randint(-9, 9) for _ in range(random.randint(1, 10))]; k = random.randint(1, len(nums))
assert kth_heap(nums, k) == sorted(nums, reverse=True)[k - 1]; counts["kth_largest"] += 1
g = [[random.randint(0, 1) for _ in range(5)] for _ in range(5)]
assert islands(g) == islands_uf(g); counts["islands"] += 1
nc = random.randint(1, 6); pre = [(random.randrange(nc), random.randrange(nc)) for _ in range(random.randint(0, 7))]
assert kahn(nc, pre) == dfs_acyclic(nc, pre); counts["course_schedule"] += 1
s = subsets(list(range(random.randint(0, 6))))
assert len(s) == 2 ** len({x for sub in s for x in sub} | set()) or True
m = random.randint(0, 6); s = subsets(list(range(m)))
assert len(s) == 2 ** m and len({tuple(x) for x in s}) == 2 ** m; counts["subsets"] += 1
lru, ref = LRU(3), OrderedDict()
for _ in range(20):
key = random.randint(0, 5)
if random.random() < 0.5:
got = lru.get(key)
if key in ref: ref.move_to_end(key, last=False)
assert got == ref.get(key)
else:
lru.put(key, key * 10)
if key in ref: ref.move_to_end(key, last=False)
elif len(ref) == 3: ref.popitem(last=True)
ref[key] = key * 10; ref.move_to_end(key, last=False)
counts["lru"] += 1
print("all cross-checks passed:")
for k, v in counts.items(): print(f" {k:16s} {v} random cases")all cross-checks passed:
cycle 300 random cases
min_stack 300 random cases
bst 300 random cases
kth_largest 300 random cases
islands 300 random cases
course_schedule 300 random cases
subsets 300 random cases
lru 300 random casesملاحظة: اختبار الـ LRU هنا بيقارن النسخة المكتوبة يدويًا بنفس المنطق على OrderedDict (reference ثاني بنفس الفكرة)، يعني بيثبت اتساق الـ implementation مش صحة الفكرة من مصدر مستقل.
أخطاء شائعة
- نسيان حفظ
nextقبل عكس الرابط. - مقارنة BST بالأبناء المباشرين فقط بدل المدى.
- إضافة نفس مرجع القائمة للنتيجة في backtracking بدل نسخة.
- تعليم visited وقت الـ pop بدل الـ push فتتكرر عناصر في الـ stack/queue.
- recursion عميقة بدون وعي بـ stack overflow.
- ادّعاء O(1) لـ LRU بدون Dictionary + node references.
خمس تمارين محلولة
1 (Easy): Merge two sorted linked lists
الحل: node وهمي (dummy) + مؤشر tail؛ قارن رأسي القائمتين واربط الأصغر وحرّك. في الآخر اربط الباقي. O(n+m) وقت، O(1) مساحة. الـ dummy بيلغي حالة خاصة للـ head.
2 (Easy): Max depth of a binary tree — recursion مقابل BFS
الحل: recursion: 1 + max(depth(left), depth(right))، O(n) وقت، O(h) مساحة. BFS: عدد المستويات في level-order. اختار BFS لو الشجرة عميقة جدًا (تجنب overflow).
3 (Intermediate): Top K frequent words باستخدام heap — اشرح التعقيد
الحل: عدّ بـ Dictionary O(n)، بعدين min-heap حجمه k على (التكرار، الكلمة): O(u log k) حيث u عدد الكلمات المميزة. مقارنة بالترتيب الكامل O(u log u). مهم: حدد قاعدة كسر التعادل (alphabetical) صراحة.
4 (Intermediate): Clone Graph — إزاي تتجنب loop لا نهائي؟
الحل: Dictionary من الـ node الأصلي للنسخة. قبل ما تنسخ node شوف لو اتنسخ؛ ده بيكسر الـ cycles. DFS أو BFS، O(V+E).
5 (Challenging): Word Ladder (أقصر سلسلة) — اختار الخوارزمية وبرّر
الحل: الكلمات nodes، وبينهم edge لو بيختلفوا في حرف واحد؛ كل edge تكلفتها 1 فـ BFS بيضمن الأقصر. التحسين: لتوليد الجيران استخدم patterns زي h*t في Dictionary بدل مقارنة كل زوج (O(N²·L)) → O(N·L²). BFS ثنائي الاتجاه بيقلل المساحة المستكشفة عمليًا.
Mini Project: مكتبة Collections مع اختبارات
اعمل class library Structures فيها MinStack و LruCache و TrieNode، ومشروع xUnit. لكل structure: اختبارات حدية، واختبار عشوائي بـ seed ثابت مقابل نسخة reference (زي List/Dictionary). معيار النجاح: dotnet test أخضر، وتعليقات complexity مبررة، وبنشمارك بسيط (Stopwatch) يوضح فرق LRU الـ O(1) عن نسخة O(n).
أسئلة إنترفيو
ليه Floyd cycle detection بيلاقي الـ cycle؟
ليه build heap من مصفوفة O(n) مش O(n log n)؟
DFS مقابل BFS في graph؟
إزاي تنفذ LRU بـ O(1)؟
إيه عيب recursion في الـ production؟
(أصعب) Topological sort: إيه اللي بيحصل لو في cycle؟
المراجع والقراءة الإضافية
الدرس بيشرح الفكرة نفسها؛ الروابط دي للتحقق والتعمق والرجوع لتفاصيل الـ API. (محتاجة إنترنت.)
خلصت الدرس وحليت الأسئلة؟ علّم عليه عشان يتحسب في تقدّمك.