تُرجِمت هذه الدروس تلقائيًا إلى العربية ولم تخضع بعد لمراجعة بشرية. إذا بدت أي صياغة غريبة، فالنسخة الإنجليزية هي المرجع.
إليك سرًا لن يتقاضاه كبار المدربين في المقابلات مقابل 500 دولار لتتعلمه: ما يقرب من 90٪ من مشكلات مقابلات البرمجة تدور حول سبع هياكل بيانات فقط. إذا فهمت بعمق متى ولماذا يجب عليك الوصول إلى كل هدف، فقد ربحت بالفعل نصف المعركة. النصف الآخر هو الممارسة، ولكن بدون النماذج العقلية الصحيحة، فإن الممارسة هي مجرد الحفظ. يمنحك هذا الدرس الخريطة بحيث تبدو كل مشكلة تواجهها وكأنها منطقة مألوفة.
كل مقابلة فنية تستمد من نفس البئر. فيما يلي الهياكل التي ستواجهها، مرتبة حسب التردد:
| بنية البيانات | تردد المقابلة | العمليات الأساسية | عندما يتوقع القائمون على المقابلات ذلك | |---|---|---|---| | ** المصفوفات / السلاسل ** | ★★★★★ | الوصول إلى O(1)، البحث عن O(n)، إدراج O(n) | تقريبا كل مشكلة تبدأ هنا | | ** خرائط / مجموعات التجزئة ** | ★★★★★ | أدخل O(1)، ابحث عن O(1)، احذف O(1) | "تحسين هذا من O(n²) إلى O(n)" | | القوائم المرتبطة | ★★★★☆ | إدراج O(1)، حذف O(1)، الوصول إلى O(n) | معالجة المؤشر، كشف الدورة | | ** الأكوام وقوائم الانتظار ** | ★★★★☆ | ادفع/فرقعة O(1)، أدخل/فصل O(1) | إعراب، BFS، التراجع عن العمليات | | الأشجار (ثنائية، BST) | ★★★★☆ | ابحث عن O(log n)، أدخل O(log n) | البيانات الهرمية، العمليات المصنفة | | الرسوم البيانية | ★★★☆☆ | يعتمد على التمثيل | علاقات، دروب، تواصل | | أكوام | ★★★☆☆ | أدخل O(log n)، واستخرج الحد الأدنى O(log n) | "ابحث عن أكبر/أصغر k" |
المصفوفات هي نقطة البداية لكل مشكلة في المقابلة تقريبًا. الفكرة الأساسية هي أن معظم مشكلات المصفوفات لا تتعلق بالمصفوفات حقًا، بل تتعلق بالتعرف على أنماط مثل مؤشرين، أو نافذة منزلقة، أو مجموعات البادئات.
# Two Sum — the most classic interview problem
# "Given an array and target, find two numbers that add to target"
def two_sum(nums, target):
seen = {} # Hash map to store complement
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# Time: O(n), Space: O(n) — trading space for time
لاحظ كيف أن مشكلة "المصفوفة" هذه هي في الحقيقة مشكلة خريطة تجزئة. يتكرر هذا النمط باستمرار: تستخدم القوة الغاشمة حلقات متداخلة فوق مصفوفة، ويقدم الحل الأمثل خريطة تجزئة.
إذا كنت عالقًا في أي مشكلة وكانت القوة الغاشمة هي O(n²)، فاسأل نفسك: "هل يمكن لخريطة التجزئة تقليل هذا إلى O(n)؟" الجواب هو نعم بشكل مدهش في كثير من الأحيان.
تتألق خرائط التجزئة عندما تحتاج إلى:
سجّل الدخول للانضمام إلى النقاش
// Group Anagrams — a classic hash map problem
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
تختبر مشكلات القائمة المرتبطة قدرتك على التعامل مع المؤشرات دون فقدان مسار العقد. التقنيات الثلاث التي تحتاجها هي:
# Detect a cycle in a linked list (Floyd's Algorithm)
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
تعد الأكوام (LIFO) وقوائم الانتظار (FIFO) من الهياكل الأكثر بساطة، ولكنها تفتح فئات كاملة من المشكلات:
# Valid Parentheses — classic stack problem
def is_valid(s: str) -> bool:
stack = []
matching = {')': '(', '}': '{', ']': '['}
for char in s:
if char in matching:
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0
تشتمل مشكلات الشجرة عادةً على التكرار وواحد من أوامر الاجتياز الثلاثة (بالترتيب، والترتيب المسبق، والترتيب اللاحق). النموذج العقلي الذي يجب تطويره هو: "ما الذي أحتاجه من الشجرة الفرعية اليسرى، والشجرة الفرعية اليمنى، وكيف يمكنني دمجهما في العقدة الحالية؟"
# Maximum depth of a binary tree — the template for tree recursion
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
تضيف مشاكل BST (شجرة البحث الثنائية) خاصية مهمة واحدة: يؤدي الاجتياز بالترتيب إلى إنتاج عناصر مرتبة. إذا رأيت "مرتبة" و"شجرة" في نفس المشكلة، فكر في BST على الفور.
تبدو مشاكل الرسم البياني مخيفة ولكن معظمها يتحول إلى BFS أو DFS بمجرد إنشاء قائمة الجوار. المهارات الأساسية هي:
# BFS shortest path in an unweighted graph
from collections import deque
def shortest_path(graph, start, end):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, distance = queue.popleft()
if node == end:
return distance
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append((neighbour, distance + 1))
return -1 # Not reachable
عندما تقول المشكلة "ابحث عن K الأكبر" أو "K الأقرب" أو "دمج قوائم K المصنفة"، فمن المؤكد تقريبًا أن الكومة (قائمة انتظار الأولوية) هي الإجابة. في بايثون، heapq يوفر كومة صغيرة؛ بالنسبة إلى الحد الأقصى للكومة، قم بإلغاء القيم.
import heapq
# Find the K largest elements in an array
def k_largest(nums, k):
return heapq.nlargest(k, nums) # Uses a min-heap of size k internally
تحتاج إلى العثور على الوسيط لتدفق الأرقام في O(log n) لكل عملية إدراج. ما هي مجموعة بنية البيانات الأكثر ملاءمة؟
| الهيكل | الوصول | بحث | أدخل | حذف | الفضاء | |---|---|---|---|---|---| | صفيف | يا(1) | يا(ن) | يا(ن) | يا(ن) | يا(ن) | | خريطة التجزئة | - | س(1)* | س(1)* | س(1)* | يا(ن) | | قائمة مرتبطة | يا(ن) | يا(ن) | يا(1) | يا(1) | يا(ن) | | المكدس/قائمة الانتظار | يا(ن) | يا(ن) | يا(1) | يا(1) | يا(ن) | | BST (متوازن) | يا(سجل ن) | يا(سجل ن) | يا(سجل ن) | يا(سجل ن) | يا(ن) | | كومة | - | يا(ن) | يا(سجل ن) | يا(سجل ن) | يا(ن) |
* حالة متوسطة؛ أسوأ الحالات هي O(n) بسبب تصادمات التجزئة.
قم بتطوير قائمة المراجعة العقلية هذه عند قراءة المشكلة: