DSA pattern to'plami — intervyu shablonlari

LeetCode-uslubidagi algoritm masalalarining 90%i bir necha takrorlanuvchi shablonga tushadi. Shablonni tanisang — masala oson bo'ladi. Bu 3-QISMning intervyuga yo'naltirilgan davomi.

Qanday foydalanish

• Har shablon: qachon ishlatiladi + g'oya + namuna kod skeleti + misol masalalar.
• Masalani o'qiganda "qaysi shablon?" deb so'ra. Belgilarni tani (saralangan? juftlik? eng katta/kichik oyna?).
• Yechim kodi to'liq emas — skelet beriladi, qolganini o'zing yoz.

1. Two Pointers (ikki ko'rsatkich)

Qachon: saralangan massiv, juftlik topish, palindrom, ikki uchdan yaqinlashish. G'oya: ikki indeks (boshi/oxiri yoki sekin/tez) bir-biriga qarab harakatlanadi.

function twoSum(sorted, target) {
  let l = 0, r = sorted.length - 1;
  while (l < r) {
    const sum = sorted[l] + sorted[r];
    if (sum === target) return [l, r];
    if (sum < target) l++;      // kichik — chapni surib oshir
    else r--;                   // katta — o'ngni surib kamaytir
  }
}

Misollar: ikki son yig'indisi (saralangan), palindrom tekshirish, suv idishi (container), 3Sum.

2. Sliding Window (siljuvchi oyna)

Qachon: ketma-ket qism (subarray/substring), "eng uzun/qisqa/maksimal" shart bilan. G'oya: oyna (l..r) ni kengaytir/qisqart, shartni saqla.

function maxSumSubarray(arr, k) {
  let sum = 0, max = 0;
  for (let r = 0; r < arr.length; r++) {
    sum += arr[r];
    if (r >= k - 1) {          // oyna to'ldi
      max = Math.max(max, sum);
      sum -= arr[r - k + 1];   // chap chetni chiqar
    }
  }
  return max;
}

Misollar: k uzunlikdagi maksimal yig'indi, takrorsiz eng uzun substring, minimal oyna.

3. Hash Map (chastota/qidiruv)

Qachon: "bormi?", sanash, juftlik, guruhlash — O(1) qidiruv. G'oya: ko'rilganni Map/Set'da saqlab, tez tekshir.

function twoSumUnsorted(arr, target) {
  const seen = new Map();
  for (let i = 0; i < arr.length; i++) {
    const need = target - arr[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(arr[i], i);
  }
}

Misollar: ikki son (saralanmagan), anagram, takror topish, eng ko'p uchragan element.

4. Fast & Slow Pointers (Floyd)

Qachon: bog'langan ro'yxat (linked list), tsikl topish, o'rta element. G'oya: sekin 1 qadam, tez 2 qadam — uchrashsa tsikl bor.

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;  // uchrashdi — tsikl
  }
  return false;
}

Misollar: tsikl bormi, o'rta tugun, ro'yxat oxiridan k-element.

5. Binary Search (ikkilik qidiruv)

Qachon: saralangan, "topish/chegara", javob diapazoni monoton. G'oya: har qadamda yarmini tashla — O(log n).

function search(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;       // o'rta (bit siljitish)
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Misollar: element topish, birinchi/oxirgi pozitsiya, aylantirilgan massivda qidiruv, "javobni qidirish".

6. BFS (kenglik bo'yicha)

Qachon: eng qisqa yo'l, qatlam-qatlam, daraxt/graf level. G'oya: queue bilan qatlam-qatlam.

function bfs(start, graph) {
  const queue = [start], seen = new Set([start]);
  while (queue.length) {
    const node = queue.shift();
    for (const next of graph[node]) {
      if (!seen.has(next)) { seen.add(next); queue.push(next); }
    }
  }
}

Misollar: eng qisqa yo'l (tortilmagan graf), level order, orollar soni, so'z zanjiri.

7. DFS / Backtracking

Qachon: barcha yo'l/kombinatsiya, daraxt chuqurligi, "barcha variant". G'oya: rekursiya bilan chuqurga ket, qaytib boshqa yo'lni sina.

function permutations(nums, path = [], result = []) {
  if (path.length === nums.length) { result.push([...path]); return; }
  for (const n of nums) {
    if (path.includes(n)) continue;
    path.push(n);                    // tanla
    permutations(nums, path, result);
    path.pop();                      // bekor qil (backtrack)
  }
  return result;
}

Misollar: o'rin almashtirishlar, kombinatsiyalar, Sudoku, N-vazir, qavslar.

8. Dynamic Programming (dinamik dasturlash)

Qachon: "eng katta/kichik/necha usul", qism-masalalar takrorlanadi. G'oya: qism-masala natijasini saqla (memoizatsiya/jadval).

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (n in memo) return memo[n];     // keshdan
  return memo[n] = fib(n-1, memo) + fib(n-2, memo);
}

Misollar: Fibonachchi, tanga maydalash, eng uzun umumiy ketma-ketlik, knapsack, pog'onalar.

9. Heap / Priority Queue

Qachon: "eng katta/kichik K ta", oqimda median, eng yaqin K. G'oya: heap top'da eng katta/kichik — O(log n) qo'shish/olish. Misollar: top K element, K-chi eng katta, oqim medianasi, birlashtirilgan K ro'yxat.

10. Tez tanish jadvali

Mashq rejasi

1. Har shablondan 3 ta masala yech (LeetCode Easy Medium).
2. Masalani o'qib, avval shablonni ayt, keyin yoz.
3. Vaqtni o'lcha — 20–30 daqiqada yecholmasang, yechimni o'rgan, keyin xotiradan qayta yoz.
4. Big-O'ni har doim ayt (vaqt + xotira).

Bog'liq: 3-QISM, Mashqlar M3 · Bosh sahifa: README.