أنماط مقابلات هياكل البيانات والخوارزميات: التي تتكرّر فعلًا

جولة التقييم الإلكترونيّ تكافئ التعرّف، لا الكمّ. معظم المسائل المتوسّطة عددٌ صغير من الأنماط بأزياء مختلفة — وحين تستطيع تسمية النمط من شكل المسألة، يصير الحلّ مكتوبًا بنسبة 80%. هذه الورقة هي طبقة الأنماط: لكلٍّ العلامة التي تشير إليه، وقالبٌ قابل لإعادة الاستخدام بلغة JavaScript، ومسائل تمثيلية، والتعقيد. أتقِن هذه العشرة وستتعرّف على معظم ما ترميه جولة تقييم Airbnb. تُكمِّل مسائل البرمجة بـ JavaScript المرتكزة على التطبيق، وميكانيكا اللغة في أساسيات JavaScript.

النموذج الذهني: لا تطحن 500 مسألة — تعلّم ~10 أنماط وحُلّ حفنةً من كلٍّ حتى تصير العلامة تلقائيّة. حين تقرأ مسألةً جديدة، مهمّتك الأولى ليست حلّها؛ بل السؤال «أيّ نمطٍ هذا؟». العلامة عادةً في شكل المدخل (مُرتَّب؟ نافذة؟ شجرة؟) وما المطلوب (زوج؟ أقصر مسار؟ الأمثل؟).

المؤشّران (Two Pointers)#

العلامة: مصفوفة مُرتَّبة (أو يمكن ترتيبها)، وتبحث عن زوجٍ أو ثلاثيّ أو تقسيم. وكذلك للتعديل الموضعيّ من الطرفين.

// زوجٌ مجموعه هدفٌ في مصفوفةٍ مُرتَّبة
function twoSumSorted(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const sum = nums[lo] + nums[hi];
    if (sum === target) return [lo, hi];
    if (sum < target) lo++;   // نحتاج أكبر ← حرّك المؤشّر الأيسر لأعلى
    else hi--;                // نحتاج أصغر ← حرّك المؤشّر الأيمن لأسفل
  }
  return [-1, -1];
}

تمثيليّة: Two Sum II، و3Sum، وContainer With Most Water، وValid Palindrome. التعقيد: O(n) (زائد O(n log n) إن رتّبت أولًا)، ومساحة O(1).

النافذة المنزلقة (Sliding Window)#

العلامة: مصفوفةٌ جزئية أو سلسلةٌ جزئية متّصلة، وتريد أطول/أقصر/أفضل نافذةٍ تحقّق شرطًا. إن رأيت «سلسلة جزئية» أو «مصفوفة جزئية» بقيدٍ، فاقصد هنا.

// أطول سلسلة جزئية بلا أحرفٍ مكرّرة
function longestUnique(s) {
  const seen = new Map();
  let start = 0, best = 0;
  for (let end = 0; end < s.length; end++) {
    const c = s[end];
    if (seen.has(c) && seen.get(c) >= start) {
      start = seen.get(c) + 1;   // قلّص النافذة بعد المكرّر
    }
    seen.set(c, end);
    best = Math.max(best, end - start + 1);
  }
  return best;
}

تمثيليّة: Longest Substring Without Repeating، وMinimum Window Substring، وMax Sum Subarray of Size K. التعقيد: O(n) — كل عنصرٍ يدخل النافذة ويخرج مرّةً واحدة.

التجزئة والتكرار (Hashing & Frequency)#

العلامة: «هل رأيتُ هذا من قبل؟»، أو عدّ التكرارات، أو التجميع، أو تحويل مسحٍ O(n²) إلى O(n) بجدول بحث. أشيع الأنماط جميعًا.

// تجميع الجناسات بتوقيع أحرفها المُرتَّبة
function groupAnagrams(words) {
  const groups = new Map();
  for (const w of words) {
    const key = [...w].sort().join("");   // توقيعٌ قانونيّ
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(w);
  }
  return [...groups.values()];
}

تمثيليّة: Two Sum (غير مُرتَّب)، وGroup Anagrams، وTop K Frequent، وSubarray Sum Equals K. التعقيد: غالبًا O(n) زمنًا وO(n) مساحة.

البحث الثنائيّ (Binary Search)#

العلامة: مدخلٌ مُرتَّب، أو «جِد أصغر/أكبر قيمةٍ تحقّق X» مصاغةً كشرطٍ رتيب. وكذلك مسائل «فضاء البحث» حيث يقع الجواب في مدًى عدديّ تبحث فيه ثنائيًّا.

function binarySearch(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);   // يتجنّب الفيضان، ويقرّب لأسفل
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

تمثيليّة: Binary Search، وSearch in Rotated Sorted Array، وKoko Eating Bananas، وMedian of Two Sorted Arrays. التعقيد: O(log n).

BFS — البحث بالعرض أولًا#

العلامة: أقصر مسار / أقلّ خطوات في رسمٍ أو شبكةٍ غير موزونة، أو اجتيازٌ مستوًى بمستوى لشجرة. يستخدم BFS طابورًا.

// طول أقصر مسارٍ في شبكة (أربع جهات)
function shortestPath(grid, start, end) {
  const rows = grid.length, cols = grid[0].length;
  const queue = [[...start, 0]];               // [صفّ، عمود، مسافة]
  const seen = new Set([start.join(",")]);
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (queue.length) {
    const [r, c, d] = queue.shift();
    if (r === end[0] && c === end[1]) return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc, key = nr + "," + nc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
          grid[nr][nc] === 0 && !seen.has(key)) {
        seen.add(key);
        queue.push([nr, nc, d + 1]);
      }
    }
  }
  return -1;
}

تمثيليّة: Number of Islands، وRotting Oranges، وWord Ladder، وBinary Tree Level Order Traversal. التعقيد: O(V + E) (أو O(صفوف·أعمدة) للشبكة).

DFS والتراجع (Backtracking)#

العلامة: استكشاف كل المسارات/التوليفات/التباديل، أو اجتياز شجرةٍ/رسمٍ حيث تذهب عميقًا قبل العرض. التراجع = DFS يتراجع عن خيارٍ بعد استكشافه.

// كل المجموعات الجزئية (مجموعة القوّة) بالتراجع
function subsets(nums) {
  const result = [];
  function backtrack(start, path) {
    result.push([...path]);            // سجّل كل عقدة، لا الأوراق فقط
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);              // اختر
      backtrack(i + 1, path);          // استكشف
      path.pop();                      // ألغِ الاختيار (تراجع)
    }
  }
  backtrack(0, []);
  return result;
}

تمثيليّة: Subsets، وPermutations، وCombination Sum، وWord Search، وGenerate Parentheses، وN-Queens. التعقيد: أُسّيّ بطبيعته — O(2ⁿ) أو O(n!) — والمقصد الشمول.

المكدّس الرتيب (Monotonic Stack)#

العلامة: «العنصر الأكبر/الأصغر التالي»، أو تحتاج أقرب حدٍّ على جهة. مكدّسٌ مُبقًى تصاعديًّا أو تنازليًّا يجيب هذه في مرورٍ واحد.

// العنصر الأكبر التالي يمينًا لكل عنصر (فهارس)
function nextGreater(nums) {
  const res = new Array(nums.length).fill(-1);
  const stack = [];                    // يحمل فهارس، بقيمٍ تنازليّة
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      res[stack.pop()] = nums[i];      // الحاليّ يحلّ كل ما هو أصغر
    }
    stack.push(i);
  }
  return res;
}

تمثيليّة: Next Greater Element، وDaily Temperatures، وLargest Rectangle in Histogram، وTrapping Rain Water. التعقيد: O(n) — كل فهرسٍ يُدفَع ويُسحَب مرّةً.

أكبر K بكومة (Top-K with a Heap)#

العلامة: «أكبر/أصغر/أكثر تكرارًا K»، أو وسيطٌ جارٍ. كومةٌ بحجم K تعطي O(n log k) بدل ترتيب كل شيء. لا كومة أصليّة في JavaScript، فاعرف واحدةً بسيطة أو حاكِها.

// أكبر K بكومةٍ صغرى بحجم k (بكومةٍ ثنائيّة صغيرة)
function kLargest(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) {
    heap.push(n);
    if (heap.size() > k) heap.pop();   // أبقِ أكبر k فقط
  }
  return heap.toArray();               // الكومة تحمل الآن أكبر k
}
// في المقابلة، اذكر أن JS تفتقر لكومةٍ أصليّة، وإمّا
// تصنع واحدة (~15 سطرًا)، أو رتّب بـ O(n log n) إن كان n صغيرًا.

تمثيليّة: Kth Largest Element، وTop K Frequent، وMerge K Sorted Lists، وFind Median from Data Stream. التعقيد: O(n log k).

الفترات (Intervals)#

العلامة: المدخل قائمة أزواج [start, end] وأنت تدمج أو تُدرِج أو تكشف التداخل. غالبًا رتّب بالبداية أولًا.

function mergeIntervals(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);   // تداخل ← مدّد
    } else {
      merged.push(intervals[i]);                       // فجوة ← فترةٌ جديدة
    }
  }
  return merged;
}

تمثيليّة: Merge Intervals، وInsert Interval، وNon-overlapping Intervals، وMeeting Rooms. التعقيد: O(n log n) للترتيب.

البرمجة الديناميكية (أحادية البُعد)#

العلامة: عُدّ الطرق، أو جِد الأصغر/الأكبر، حيث يُبنى جواب n على أجوبة n أصغر، والعَوْدية الساذجة تعيد حساب المسائل الجزئية نفسها. ابدأ بالعلاقة التكراريّة، ثم خزّنها.

// صعود الدرج: طرق بلوغ الدرجة n بخطوةٍ أو خطوتين
function climbStairs(n) {
  let a = 1, b = 1;                    // dp[i] = dp[i-1] + dp[i-2]
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];              // دحرِج النافذة؛ مساحة O(1)
  }
  return b;
}

تمثيليّة: Climbing Stairs، وHouse Robber، وCoin Change، وLongest Increasing Subsequence، وWord Break. التعقيد: O(n) إلى O(n²) حسب العلاقة؛ وغالبًا مساحة O(1)–O(n) بعد الدحرجة.

الأخطاء الشائعة#

• القفز إلى الكود قبل تسمية النمط — صنّف أولًا دائمًا. العلامة في شكل المدخل والمطلوب.
• طحن الكمّ على الأنماط — 300 مسألةٍ عشوائية تُعلّم أقلّ من 60 مختارةً لتغطية كل نمطٍ مرّتين.
• نسيان أن JS بلا كومةٍ أو خريطةٍ مُرتَّبة أصليّة — قُلها بصوتٍ مسموع واصنع أو التفّ حولها.
• خطأ الواحد في البحث الثنائيّ — ثبّت ثابتك (lo <= hi مقابل lo < hi) وهل تُرجِع lo أم mid، وأبقِه متّسقًا.
• عدم ذكر التعقيد — أعطِ الزمن والمساحة دون طلبٍ دائمًا؛ نصف ما يُقيَّم.
• تجاهل الحالات الحدّيّة — مدخلٌ فارغ، عنصرٌ واحد، كلّ مكرّرات، مُرتَّبٌ سلفًا، هدفٌ غائب. اختبرها قبل أن تقول «انتهيت».

تمارين#

سَمِّ النمط قبل الحلّ — تلك هي المهارة المُدرَّبة.

تمرين 1 — سَمِّ النمط#

«بمصفوفة أعداد، أعِد طول أطول مصفوفةٍ جزئية مجموعها لا يتجاوز K». أيّ نمطٍ، ولماذا؟

تمرين 2 — اختر الأداة الصحيحة#

«جِد أكثر K عنصرًا تكرارًا في مصفوفة». ترتيبٌ، أم كومة، أم دلاء — أيّها، وما المقايضة؟

تمرين 3 — الشبكة = رسم#

«عُدّ الجزر في شبكةٍ من يابسةٍ وماء». أيّ نمطٍ، وBFS أم DFS؟

النموذج الذهني الذي تحتفظ به#

جولة التقييم تعرّفٌ على الأنماط تحت ضغط الوقت، لا عددَ مسائل خام. احمِل هذه الأنماط العشرة وعلاماتها: المؤشّران (مُرتَّب، جِد زوجًا)، والنافذة المنزلقة (نافذةٌ متّصلة بقيد)، والتجزئة (رُئِي من قبل / عدّ)، والبحث الثنائيّ (مُرتَّب أو جوابٌ رتيب)، وBFS (أقصر مسار، طابور)، وDFS/التراجع (استكشف كل المسارات، ألغِ الخيارات)، والمكدّس الرتيب (الأكبر/الأصغر التالي)، وكومة أكبر K (أكبر/أكثر تكرارًا K)، والفترات (رتّب بالبداية ثم ادمج)، وDP أحادية البُعد (ابنِ على مسائل جزئية أصغر). لأيّ مسألةٍ جديدة: صنّف بشكل المدخل والمطلوب، أسقِط القالب، كيّف، ثم اذكر التعقيد واختبر الحدود. التعرّف هو اللعبة كلها — درّبه، وتكفّ جولة التقييم عن كونها اختبار ذاكرة وتصير تمرين مطابقة.