Algoritmlar va ma'lumot tuzilmalari (DSA) — texnik intervyu

Full-stack dasturchi uchun chuqur intervyu tayyorgarligi. Nazariy savollar (Ta'rif Mexanizm Kod tez-tez uchraydigan xato follow-up) va amaliy kodlash masalalari (yondashuv yechim Big-O optimizatsiya) birga.

Qanday foydalanish

• Har bir savolni o'qib, avval o'zingiz javob berishga urinib ko'ring, so'ng yechimni oching.
• Amaliy masalada birinchi yondashuvni ovoz chiqarib ayting — intervyuda fikrlash jarayoni yakuniy koddan muhimroq baholanadi.
• Darajalar: Junior · Middle · Senior.
• Kod JavaScriptda, lekin g'oyalar tildan mustaqil. Atamalar (ingliz) atayin saqlangan — intervyu shu tilda ketadi.

Intervyu — muammoni bo'laklarga ajratib, ovoz chiqarib fikrlay olish san'ati. Yodlamang: naqshni (pattern) tushuning, keyin uni yangi masalaga moslang.

Mundarija

1. Big-O va murakkablik tahlili
2. Massiv va Linked List
3. Hash Table
4. Stack va Queue
5. Tree, BST, AVL
6. Heap / Priority Queue
7. Graph, BFS, DFS
8. Trie
9. Saralash (Sorting)
10. Qidiruv va Recursion
11. Dynamic Programming va Greedy
12. Intervyu patternlari va klassik masalalar
13. Eng ko'p uchraydigan 15 masala

1. Big-O va murakkablik tahlili

S: Big-O notation nima va nima uchun kerak? (Junior)

Ta'rif: Big-O — algoritmning o'sish tezligini kirish hajmi n ortganda yuqoridan cheklovchi funksiya bilan ifodalaydi. U aniq soniya emas, masshtablanishni o'lchaydi.

Mexanizm: Big-O eng yomon holatdagi (worst case) yuqori chegarani beradi. Konstantalar va past darajali hadlar tashlab yuboriladi: 3n² + 5n + 10 O(n²), chunki n katta bo'lganda n² hukmronlik qiladi.

// O(1) — kirish hajmiga bog'liq emas
function birinchisi(arr) {
  return arr[0];
}

// O(n) — har element bo'ylab bir marta
function yigindi(arr) {
  let s = 0;
  for (const x of arr) s += x; // n marta
  return s;
}

// O(n²) — ichma-ich sikl
function juftlar(arr) {
  const res = [];
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      res.push([arr[i], arr[j]]);
  return res;
}

Xato: Konstantani "muhim" deb saqlab qolish (O(2n) deb yozish) yoki eng yomon holat bilan o'rtacha holatni chalkashtirish. Big-O — asimptotik, konstantasiz.

Follow-up: O(log n) qayerdan chiqadi? — Har qadamda masala hajmi ikkiga bo'linganda (binary search, balansli daraxt). O(n log n) — har elementni logarifmik ish bilan qayta ishlaganda (merge sort).

S: Time complexity va space complexity farqi nimada? Misol bilan. (Middle)

Ta'rif: Time — bajariladigan amallar soni nga qarab qanday o'sishi. Space — kirishdan tashqari qo'shimcha xotira (auxiliary space) qanday o'sishi.

Mexanizm: Ko'pincha ular o'rtasida savdo (trade-off) bor: xotira sarflab vaqtni tejash mumkin (masalan hash table bilan O(n²) ni O(n) ga tushirish).

// Time O(n), Space O(1) — joyida (in-place) yig'indi
function jamla(arr) {
  let s = 0;
  for (const x of arr) s += x;
  return s; // qo'shimcha xotira konstanta
}

// Time O(n), Space O(n) — natija uchun yangi massiv
function ikkilantir(arr) {
  return arr.map((x) => x * 2); // n o'lchamli yangi massiv
}

Xato: Recursion'da call stackni space sifatida hisobga olmaslik. n marta chuqurlashadigan rekursiya O(n) space sarflaydi (stack frame'lar).

Follow-up: In-place algoritm nima? — Kirishni o'zgartirib, O(1) qo'shimcha xotira ishlatadigan algoritm (masalan quicksort, reverse in-place).

S: Amortized time complexity nima? (Middle)

Ta'rif: Amortized — ketma-ket amallar ustidan o'rtacha narx; ba'zi amal qimmat bo'lsa ham, uzoq muddatda arzon.

Mexanizm: Dinamik massivga push — odatda O(1), lekin sig'im to'lganda hajm ikkilanadi va barcha elementlar ko'chiriladi (O(n)). Ikkilantirish siyrak bo'lgani uchun n ta push o'rtacha O(1) bo'ladi — amortized O(1).

// Dinamik massiv o'sishi (soddalashtirilgan model)
class DynArray {
  constructor() { this.data = new Array(1); this.len = 0; this.cap = 1; }
  push(x) {
    if (this.len === this.cap) {      // to'ldi  ikkilantir (kamdan-kam)
      this.cap *= 2;
      const bigger = new Array(this.cap);
      for (let i = 0; i < this.len; i++) bigger[i] = this.data[i];
      this.data = bigger;
    }
    this.data[this.len++] = x;         // odatda O(1)
  }
}

Xato: Amortized O(1) ni "har doim O(1)" deb tushunish. Bitta alohida push O(n) bo'lishi mumkin — faqat o'rtacha O(1).

Follow-up: Nega hajmni +1 emas, ×2 qilib o'stiriladi? — +1 bo'lsa har push O(n) bo'lib, jami O(n²) bo'ladi. ×2 — jami O(n).

S: Quyidagi kod murakkabligini aniqlang va tushuntiring. (Senior)

function f(n) {
  for (let i = 1; i < n; i *= 2) {   // A
    for (let j = 0; j < n; j++) {    // B
      // O(1) ish
    }
  }
}

J: Tashqi sikl i ni ikkilantiradi log₂(n) marta aylanadi. Ichki sikl har safar n marta. Jami: O(n log n).

Mexanizm: Sikllarni ko'paytiring: log n × n. Additive emas, nested bo'lgani uchun multiplicative.

Xato: Ikkala siklni ham n deb, O(n²) deyish. Tashqi sikl geometrik o'sadi — log n.

Follow-up: Agar ichki sikl j < i bo'lsa? — U holda jami 1 + 2 + 4 + ... + n/2 ≈ n, ya'ni O(n).

2. Massiv va Linked List

S: Array va Linked List farqi? Qachon qaysi biri? (Junior)

Ta'rif: Array — xotirada ketma-ket joylashgan elementlar, indeks orqali kirish. Linked List — har biri keyingisiga ko'rsatkich (pointer) saqlaydigan tugunlar (node) zanjiri.

Mexanizm:

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}
// 1 -> 2 -> 3
const head = new ListNode(1, new ListNode(2, new ListNode(3)));

Xato: Linked List'da "tez qidiruv" deb o'ylash. Qidiruv O(n) — indeks yo'q, boshdan yurish kerak. Kesh (cache) do'stligi ham arrayda yaxshiroq.

Follow-up: Nega array indeks kirishi O(1)? — Element manzili bosh + indeks × element_hajmi formula bilan bir amalda hisoblanadi.

Masala: Linked List'ni teskari aylantiring (Reverse Linked List)

Yondashuv: Uch ko'rsatkich saqlaymiz: prev, curr, next. Har qadamda curr.next ni prev ga qaratamiz, keyin uchalasini bir qadam suramiz. Ro'yxatni bir marta aylanamiz.

Yechim:

function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr !== null) {
    const next = curr.next; // keyingisini saqlab qol
    curr.next = prev;       // yo'nalishni teskari qil
    prev = curr;            // prev ni sur
    curr = next;            // curr ni sur
  }
  return prev; // yangi bosh
}

Vaqt/Xotira: Time O(n) — har tugun bir marta. Space O(1) — faqat uch o'zgaruvchi.

Optimizatsiya: Rekursiv variant ham mavjud, lekin u O(n) call stack sarflaydi — iterativ yechim xotira jihatidan afzal.

Masala: Ikki saralangan massivni birlashtiring (Merge Sorted Arrays)

Yondashuv: Ikkala massiv ham saralangani uchun ikki ko'rsatkich (two pointers) ishlatamiz. Har qadamda kichikroq boshini natijaga qo'shamiz. Solishtirish O(m+n).

Yechim:

function mergeSorted(a, b) {
  const res = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) res.push(a[i++]);
    else res.push(b[j++]);
  }
  // qoldiqlarni qo'sh
  while (i < a.length) res.push(a[i++]);
  while (j < b.length) res.push(b[j++]);
  return res;
}
// mergeSorted([1,3,5], [2,4,6]) -> [1,2,3,4,5,6]

Vaqt/Xotira: Time O(m+n), Space O(m+n) natija uchun.

Optimizatsiya: LeetCode "Merge Sorted Array" variantida a da bo'sh joy bor va in-place O(1) space talab qilinadi — u holda oxiridan boshiga to'ldiriladi (katta elementni orqaga qo'yish orqali ustiga yozib yuborishning oldi olinadi).

3. Hash Table

S: Hash Table qanday ishlaydi? Collision nima va qanday hal qilinadi? (Middle)

Ta'rif: Hash Table — kalitni hash funksiya orqali massiv indeksiga aylantirib, o'rtacha O(1) qidiruv/qo'shish beradigan tuzilma.

Mexanizm: hash(key) % capacity indeksni beradi (bucket). Collision — ikki xil kalit bir indeksga tushishi. Ikki asosiy yechim:

1. Chaining — har bucketda linked list; to'qnashganlar zanjirga qo'shiladi.
2. Open addressing — band bo'lsa keyingi bo'sh katakni qidiradi (linear/quadratic probing).

class HashMap {
  constructor(size = 16) { this.buckets = Array.from({ length: size }, () => []); }
  _hash(key) {
    let h = 0;
    for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) % this.buckets.length;
    return h;
  }
  set(key, val) {
    const b = this.buckets[this._hash(key)];
    const found = b.find((p) => p[0] === key);
    if (found) found[1] = val;       // yangilash
    else b.push([key, val]);          // collision  zanjirga qo'sh
  }
  get(key) {
    const b = this.buckets[this._hash(key)];
    const found = b.find((p) => p[0] === key);
    return found ? found[1] : undefined;
  }
}

Xato: Hash table'ni har doim O(1) deb o'ylash. Yomon hash yoki ko'p collision bo'lsa, eng yomon holat O(n). Yaxshi tarqatuvchi hash va load factor nazorati muhim.

Follow-up: Load factor nima? — elementlar / bucketlar. Odatda 0.75 ga yetganda jadval kattalashtirilib (rehash), collision kamaytiriladi. JavaScript'dagi Map/Object shu asosda ishlaydi.

Masala: Two Sum — yig'indisi target bo'lgan ikki indeksni toping

Yondashuv: Naive yechim ichma-ich sikl bilan O(n²). Hash map bilan yaxshilaymiz: har element uchun target - x avval ko'rilganmi deb tekshiramiz — bir o'tishda topamiz.

Yechim:

function twoSum(nums, target) {
  const seen = new Map(); // qiymat -> indeks
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return []; // topilmadi
}
// twoSum([2,7,11,15], 9) -> [0,1]

Vaqt/Xotira: Time O(n), Space O(n) (map).

Optimizatsiya: Bu allaqachon optimal. Agar massiv saralangan bo'lsa, O(1) space bilan two pointers ishlatish mumkin (pastda "Two Pointers" bo'limiga qarang).

Masala: Anagram tekshirish (Valid Anagram)

Yondashuv: Ikki so'z anagram bo'lsa, harflar chastotasi bir xil. Hash map (yoki 26 o'lchamli sanoq massivi) bilan chastotalarni sanab solishtiramiz.

Yechim:

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Map();
  for (const ch of s) count.set(ch, (count.get(ch) || 0) + 1);
  for (const ch of t) {
    if (!count.has(ch)) return false;
    count.set(ch, count.get(ch) - 1);
    if (count.get(ch) === 0) count.delete(ch);
  }
  return count.size === 0;
}
// isAnagram("listen", "silent") -> true

Vaqt/Xotira: Time O(n), Space O(k) (k — noyob harflar soni).

Optimizatsiya: Sortlab solishtirish ham mumkin (O(n log n)), lekin chastota sanash tezroq. Faqat kichik lotin harflari bo'lsa, Map o'rniga new Array(26) — kesh do'st va tezroq.

4. Stack va Queue

S: Stack va Queue farqi? Har biri qayerda ishlatiladi? (Junior)

Ta'rif: Stack — LIFO (Last In, First Out): oxirgi kirgan birinchi chiqadi. Queue — FIFO (First In, First Out): birinchi kirgan birinchi chiqadi.

Mexanizm: Stack: push/pop — bir uchdan. Queue: enqueue (oxirga) / dequeue (boshdan).

// Stack
const stack = [];
stack.push(1); stack.push(2);
stack.pop(); // 2

// Queue (samarali — shift O(n) bo'lgani uchun ko'rsatkichli)
class Queue {
  constructor() { this.items = {}; this.head = 0; this.tail = 0; }
  enqueue(x) { this.items[this.tail++] = x; }
  dequeue() {
    if (this.head === this.tail) return undefined;
    const v = this.items[this.head];
    delete this.items[this.head++];
    return v;
  }
}

Xato: JS massivida arr.shift() ni queue sifatida katta ma'lumotda ishlatish — u O(n) (barcha elementni suradi). Yuqoridagidek ko'rsatkichli yoki linked list bilan O(1) qiling.

Follow-up: Qayerlarda ishlatiladi? — Stack: funksiya chaqiruvlari (call stack), undo/redo, ifoda tekshirish, DFS. Queue: navbat, BFS, task scheduling, buffer.

Masala: Qavslar to'g'riligini tekshiring (Valid Parentheses)

Yondashuv: Ochilgan qavsni stackga qo'yamiz; yopiluvchi kelganda stack tepasi mos ochuvchi bo'lishi kerak. Oxirda stack bo'sh bo'lsa — to'g'ri.

Yechim:

function isValid(s) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else {
      if (stack.pop() !== pairs[ch]) return false; // mos kelmadi
    }
  }
  return stack.length === 0; // hammasi yopilgan bo'lsa
}
// isValid("({[]})") -> true;  isValid("(]") -> false

Vaqt/Xotira: Time O(n), Space O(n) (eng yomon holatda hammasi ochuvchi).

Optimizatsiya: Bu optimal. Kichik yaxshilanish: stack.pop() undefined qaytarsa (bo'sh stackka yopuvchi kelsa) ham !== avtomatik false beradi — alohida tekshiruv shart emas.

Masala: Min Stack — getMinni O(1)da bering

Yondashuv: Har bir elementga yonma-yon shu paytgacha ko'rilgan minimumni ham saqlaymiz (ikkinchi stack yoki juftlik). Shunda tepani ko'rish O(1).

Yechim:

class MinStack {
  constructor() { this.stack = []; } // har element: [qiymat, shu paytgacha min]
  push(x) {
    const min = this.stack.length ? Math.min(x, this.top()[1]) : x;
    this.stack.push([x, min]);
  }
  pop() { return this.stack.pop()[0]; }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() { return this.top()[1]; } // O(1)
}

Vaqt/Xotira: Barcha amallar Time O(1). Space O(n).

Optimizatsiya: Har elementga min saqlash o'rniga, faqat min o'zgarganda alohida "min stack"ga yozish xotirani tejaydi (takror minlarni saqlamaslik).

5. Tree, BST, AVL

S: Binary Tree, Binary Search Tree (BST) va balansli daraxt farqi? (Junior)

Ta'rif: Binary Tree — har tugunda ko'pi bilan 2 farzand. BST — qo'shimcha shart: chap qism-daraxt < tugun < o'ng qism-daraxt. Balanced tree (masalan AVL, Red-Black) — balandlik O(log n) da ushlab turiladigan BST.

Mexanizm: BST'da qidiruv har qadamda yarmini tashlaydi o'rtacha O(log n). Lekin BST buzilib zanjirga aylanishi mumkin (skewed) O(n). Balansli daraxt aylantirishlar (rotation) bilan buni oldini oladi.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function insertBST(root, val) {
  if (root === null) return new TreeNode(val);
  if (val < root.val) root.left = insertBST(root.left, val);
  else root.right = insertBST(root.right, val);
  return root;
}

Xato: BST'ni har doim O(log n) deb hisoblash. Saralangan ma'lumotni tartib bilan qo'ysangiz, u bir tomonlama zanjir (linked list) bo'lib qoladi — O(n). Shu sabab production'da balansli variant (yoki hash) ishlatiladi.

Follow-up: AVL qanday balanslaydi? — Har tugunda chap va o'ng balandlik farqi (balance factor) {-1, 0, 1} ichida bo'lishi shart. Buzilsa, LL/LR/RL/RR rotatsiyalar bilan tuzatiladi.

S: Daraxtni aylanish (traversal) turlarini tushuntiring: in/pre/post/level order. (Middle)

Ta'rif: Traversal — daraxtning barcha tugunlariga bir marta tashrif tartibi.

Mexanizm:

• Pre-order (Root Left Right): daraxtni nusxalash, ifoda daraxtini prefiks yozish.
• In-order (Left Root Right): BST'da saralangan tartibda beradi.
• Post-order (Left Right Root): tugunlarni o'chirish, papka hajmini hisoblash.
• Level-order (BFS): qavat-qavat, queue bilan.

function inorder(root, res = []) {
  if (!root) return res;
  inorder(root.left, res);
  res.push(root.val);      // root o'rtada
  inorder(root.right, res);
  return res;
}

function levelOrder(root) {
  const res = [], queue = root ? [root] : [];
  while (queue.length) {
    const level = [], size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(level);
  }
  return res;
}

Xato: In-order va pre-order tartibini aralashtirish. Eslab qoling: in-order root ichkarida (o'rtada), pre-order root oldin, post-order root oxirda.

Follow-up: BST to'g'ri qurilganini qanday tekshirasiz? — In-order traversal qat'iy o'sib boruvchi bo'lsa, bu haqiqiy BST.

Masala: Binary tree chuqurligi (Maximum Depth)

Yondashuv: Rekursiya: tugun chuqurligi = 1 + max(chap chuqurlik, o'ng chuqurlik). Bo'sh tugun chuqurligi 0.

Yechim:

function maxDepth(root) {
  if (root === null) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Vaqt/Xotira: Time O(n) — har tugun bir marta. Space O(h) — call stack, h daraxt balandligi (eng yomon O(n), balansli O(log n)).

Optimizatsiya: Chuqur daraxtda stack overflow'dan qochish uchun iterativ BFS/DFS (yashirin stack/queue bilan) ishlatish mumkin.

Masala: BST'da qidiruv (Search in BST)

Yondashuv: BST xossasidan foydalanamiz: qidirilayotgan qiymat tugundan kichik bo'lsa chapga, katta bo'lsa o'ngga. Har qadamda yarmini tashlaymiz.

Yechim:

function searchBST(root, target) {
  let node = root;
  while (node !== null) {
    if (node.val === target) return node;
    node = target < node.val ? node.left : node.right;
  }
  return null; // topilmadi
}

Vaqt/Xotira: Time O(h) — balansli O(log n), buzilgan O(n). Space O(1) (iterativ).

Optimizatsiya: Iterativ variant rekursivdan afzal — O(1) space va stack overflow yo'q.

6. Heap / Priority Queue

S: Heap nima? Priority Queue bilan qanday bog'liq? (Middle)

Ta'rif: Heap — to'liq binar daraxt bo'lib, heap xossasini saqlaydi: Min-heapda har ota farzandidan kichik yoki teng (ildizda eng kichik). Priority Queue — heap orqali samarali amalga oshiriladigan mavhum tuzilma.

Mexanizm: Heap odatda massivda saqlanadi: i tugunning farzandlari 2i+1 va 2i+2, otasi (i-1)/2. insert — oxirga qo'yib yuqoriga suzdirish (sift-up), extractMin — ildizni olib, oxirgini tepaga qo'yib pastga cho'ktirish (sift-down). Ikkalasi ham O(log n).

class MinHeap {
  constructor() { this.h = []; }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p] <= this.h[i]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  _down(i) {
    const n = this.h.length;
    while (true) {
      let small = i, l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && this.h[l] < this.h[small]) small = l;
      if (r < n && this.h[r] < this.h[small]) small = r;
      if (small === i) break;
      [this.h[small], this.h[i]] = [this.h[i], this.h[small]];
      i = small;
    }
  }
  push(x) { this.h.push(x); this._up(this.h.length - 1); }
  pop() {
    const top = this.h[0], last = this.h.pop();
    if (this.h.length) { this.h[0] = last; this._down(0); }
    return top;
  }
  peek() { return this.h[0]; }
  get size() { return this.h.length; }
}

Xato: Heap to'liq saralangan deb o'ylash. Faqat ildiz min/max kafolatlanadi; qolgan tartib qisman. Saralangan ketma-ketlik uchun ketma-ket pop qilish kerak (bu heapsort).

Follow-up: k ta eng katta elementni qanday topasiz? — n log n sortdan ko'ra, k o'lchamli min-heap yuriting: O(n log k), space O(k).

Masala: Massivdagi k-chi eng katta element (Kth Largest)

Yondashuv: Butun massivni sortlash O(n log n). Yaxshiroq: k o'lchamli min-heap saqlaymiz — har element uchun push qilib, hajm kdan oshsa eng kichigini (heap ildizi) tashlaymiz. Oxirda ildiz — k-chi eng katta.

Yechim:

function findKthLargest(nums, k) {
  const heap = new MinHeap(); // yuqoridagi klass
  for (const x of nums) {
    heap.push(x);
    if (heap.size > k) heap.pop(); // eng kichigini chiqarib tashla
  }
  return heap.peek(); // heapdagi eng kichik = k-chi eng katta
}
// findKthLargest([3,2,1,5,6,4], 2) -> 5

Vaqt/Xotira: Time O(n log k), Space O(k).

Optimizatsiya: O'rtacha O(n) uchun Quickselect (partition asosidagi) algoritmini ishlatish mumkin, lekin eng yomon holat O(n²). Heap barqarorroq va oqim (streaming) ma'lumotda ishlaydi.

7. Graph, BFS, DFS

S: Graph qanday ifodalanadi? Adjacency list vs matrix. (Middle)

Ta'rif: Graph — tugunlar (vertices) va ular orasidagi bog'lanishlar (edges) to'plami. Ikki asosiy ifoda: adjacency list (har tugun uchun qo'shnilar ro'yxati) va adjacency matrix (V×V jadval, 1/0 bog'lanish).

Mexanizm:

// Adjacency list — Map bilan
const graph = new Map([
  ['A', ['B', 'C']],
  ['B', ['A', 'D']],
  ['C', ['A', 'D']],
  ['D', ['B', 'C']],
]);

Xato: Har doim matritsa ishlatish. Real graflar (ijtimoiy tarmoq, yo'l xaritasi) siyrak bo'ladi — O(V²) xotira behuda; adjacency list afzal.

Follow-up: Yo'naltirilgan (directed) va yo'naltirilmagan (undirected) grafda list qanday farq qiladi? — Undirected'da qirra ikkala tugunga ham qo'shiladi; directed'da faqat bir yo'nalishda.

Masala: Graph BFS (kenglik bo'yicha aylanish)

Yondashuv: Queue va visited to'plam. Boshlang'ich tugunni navbatga qo'yamiz; har qadamda boshdan olib, ko'rilmagan qo'shnilarini navbatga qo'shamiz. BFS eng qisqa yo'l (og'irliksiz grafda) uchun ideal.

Yechim:

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const next of graph.get(node) || []) {
      if (!visited.has(next)) {
        visited.add(next);   // navbatga qo'yishdan OLDIN belgila
        queue.push(next);
      }
    }
  }
  return order;
}

Vaqt/Xotira: Time O(V + E), Space O(V) (queue + visited).

Optimizatsiya: queue.shift() O(n) — katta grafda ko'rsatkichli queue yoki head indeksi bilan O(1) dequeue qiling.

Masala: Graph DFS (chuqurlik bo'yicha aylanish)

Yondashuv: Rekursiya (yoki stack) va visited. Har tugundan uning ko'rilmagan qo'shnisiga chuqur kirib, orqaga qaytamiz (backtrack). Sikl aniqlash, topologik saralash, bog'langan komponentlar uchun asos.

Yechim:

function dfs(graph, start, visited = new Set(), order = []) {
  visited.add(start);
  order.push(start);
  for (const next of graph.get(start) || []) {
    if (!visited.has(next)) dfs(graph, next, visited, order);
  }
  return order;
}

Vaqt/Xotira: Time O(V + E), Space O(V) (visited + rekursiya stacki).

Optimizatsiya: Juda chuqur grafda rekursiya stack overflow beradi — aniq (explicit) stack bilan iterativ DFS xavfsizroq.

Masala: Orollar sonini toping (Number of Islands)

Yondashuv: Matritsa — grid graf. Har '1' (quruqlik) katakdan DFS/BFS bilan butun orolni "cho'ktiramiz" ('0' qilamiz), sanoqni oshiramiz. Yangi DFS boshlanishi = yangi orol.

Yechim:

function numIslands(grid) {
  let count = 0;
  const rows = grid.length, cols = grid[0].length;
  function sink(r, c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') return;
    grid[r][c] = '0';              // ko'rildi
    sink(r + 1, c); sink(r - 1, c);
    sink(r, c + 1); sink(r, c - 1);
  }
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === '1') { count++; sink(r, c); }
  return count;
}

Vaqt/Xotira: Time O(rows × cols) — har katak bir marta. Space O(rows × cols) eng yomon holatda (rekursiya stacki).

Optimizatsiya: Grid'ni o'zgartirmaslik kerak bo'lsa, alohida visited matritsa ishlatiladi. Juda katta grid uchun DFS o'rniga BFS stack overflow'dan himoya qiladi.

8. Trie

S: Trie (prefix tree) nima va qachon ishlatiladi? (Middle)

Ta'rif: Trie — satrlarni belgilar bo'yicha saqlaydigan daraxt; har yo'l (rootnode) bir prefiksni ifodalaydi. Avtoto'ldirish (autocomplete), imlo tekshirish, prefiks qidiruvida kuchli.

Mexanizm: Har tugun farzandlar map'ini (belgi tugun) va so'z tugadi bayrog'ini saqlaydi. n uzunlikdagi so'zni qo'shish/qidirish O(n) — lug'at hajmiga bog'liq emas.

class Trie {
  constructor() { this.root = {}; }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.isEnd = true; // so'z tugadi
  }
  search(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node[ch]) return false;
      node = node[ch];
    }
    return node.isEnd === true;
  }
  startsWith(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node[ch]) return false;
      node = node[ch];
    }
    return true; // prefiks mavjud
  }
}

Xato: isEnd bayrog'ini unutish — u holda search("app") "apple" bor bo'lsa noto'g'ri true qaytaradi. Prefiks mavjudligi so'z mavjudligini anglatmaydi.

Follow-up: Trie vs Hash Set qidiruv uchun? — Hash Set to'liq so'zni O(1) topadi, lekin prefiks qidiruv qila olmaydi. Trie prefiks bo'yicha barcha so'zlarni samarali beradi.

9. Saralash (Sorting)

S: Asosiy sort algoritmlari va murakkabliklarini solishtiring. Qachon qaysi? (Middle)

Ta'rif: Sorting — elementlarni ma'lum tartibda joylash. Algoritmlar vaqt, xotira va barqarorlik (stability) bo'yicha farqlanadi.

Mexanizm:

Qachon qaysi:

• Kichik massiv (n < 10-20) yoki deyarli saralangan Insertion.
• Kafolatli O(n log n) va barqarorlik kerak Merge.
• O'rtacha eng tez, xotira muhim Quick (yaxshi pivot bilan).
• Kafolatli O(n log n) + O(1) xotira Heap.

Xato: Quicksort'ni har doim O(n log n) deb bilish. Yomon pivot (masalan allaqachon saralangan massivda birinchi element) O(n²) beradi. Randomized pivot yoki median-of-three bu xavfni kamaytiradi.

Follow-up: JavaScript'ning Array.sort() nima ishlatadi? — Ko'p enginlarda Timsort (merge + insertion gibridi) — barqaror va real ma'lumotda tez. Diqqat: standart sort sonlarni satr sifatida solishtiradi, comparator bering: arr.sort((a,b) => a-b).

Masala: Merge Sort'ni yozing

Yondashuv: Divide and conquer: massivni yarmiga bo'lib, har yarmini rekursiv sortlab, so'ng ikki saralangan yarmni birlashtiramiz (merge).

Yechim:

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  // merge
  const res = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) res.push(left[i++]);
    else res.push(right[j++]);
  }
  while (i < left.length) res.push(left[i++]);
  while (j < right.length) res.push(right[j++]);
  return res;
}

Vaqt/Xotira: Time O(n log n) (har doim). Space O(n).

Optimizatsiya: slice yangi massiv yaratadi — indeks chegaralari (lo, hi) uzatib, xotirani kamaytirish mumkin. Kichik bo'laklarda insertion sortga o'tish (gibrid) amalda tezlashtiradi.

Masala: Quick Sort'ni yozing

Yondashuv: Pivot tanlaymiz, massivni pivotdan kichik / katta qismlarga bo'lamiz (partition), har qismni rekursiv sortlaymiz. In-place.

Yechim:

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  // random pivot — eng yomon holatdan himoya
  const pivotIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[pivotIdx], arr[hi]] = [arr[hi], arr[pivotIdx]];
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]]; // pivotni joyiga qo'y
  quickSort(arr, lo, i - 1);
  quickSort(arr, i + 1, hi);
  return arr;
}

Vaqt/Xotira: Time o'rtacha O(n log n), eng yomon O(n²). Space O(log n) (rekursiya).

Optimizatsiya: Random yoki median-of-three pivot; kichroq qismni oxirgi qilib rekursiya chuqurligini O(log n)da ushlash (tail-call uslubi); ko'p takror qiymatlar uchun 3-way partition (Dutch National Flag).

10. Qidiruv va Recursion

S: Binary Search qanday ishlaydi va sharti nima? (Junior)

Ta'rif: Binary Search — saralangan massivda har qadamda qidiruv oralig'ini yarmiga qisqartirib, elementni O(log n)da topadi.

Mexanizm: lo va hi chegara. O'rtani (mid) tekshiramiz: teng bo'lsa topildi; kichik bo'lsa o'ng yarimga (lo = mid+1), katta bo'lsa chap yarimga (hi = mid-1) o'tamiz.

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

Xato: mid = (lo + hi) / 2 — katta sonlarda overflow (boshqa tillarda) va butun songa yaxlitlamaslik. lo + (hi - lo) / 2 xavfsiz. Yana: lo <= hi shartida = ni unutib, bitta elementli oralig'ni o'tkazib yuborish.

Follow-up: Massiv saralanmagan bo'lsa? — Binary search ishlamaydi; avval sortlash (O(n log n)) yoki chiziqli qidiruv (O(n)). Bir marta qidiruv uchun sortlash foydasiz.

S: Recursion va iteration farqi? Qaysi biri qachon? (Middle)

Ta'rif: Recursion — funksiya o'zini chaqiradi, masalani kichikroq nusxasiga qisqartiradi. Iteration — sikl bilan takrorlash.

Mexanizm: Har rekursiv chaqiruv stack frame qo'shadi (O(chuqurlik) xotira). Iteratsiya konstanta xotira ishlatadi, lekin kod ba'zan uzunroq. Rekursiya daraxt/graf, divide-and-conquer'da tabiiy.

// Rekursiv — O(n) stack
function factR(n) { return n <= 1 ? 1 : n * factR(n - 1); }
// Iterativ — O(1) xotira
function factI(n) {
  let r = 1;
  for (let i = 2; i <= n; i++) r *= i;
  return r;
}

Xato: Base caseni unutish yoki uni tomon qadam qo'ymaslik cheksiz rekursiya, stack overflow. Har rekursiyada masala kichrayishi shart.

Follow-up: Tail recursion nima? — Rekursiv chaqiruv funksiyaning oxirgi amali bo'lsa; ba'zi tillar (JS engine'lari cheklangan) uni siklga optimallashtiradi (O(1) stack). JS'da ko'pincha qo'lda iteratsiyaga o'tish kerak.

11. Dynamic Programming va Greedy

S: Dynamic Programming nima? Memoization va Tabulation farqi? (Senior)

Ta'rif: DP — murakkab masalani qism-masalalarga bo'lib, ularning yechimini qayta ishlatib (takrorlamay) samarali yechish. Ikki shart: optimal substructure (yechim qism-yechimlardan quriladi) va overlapping subproblems (bir qism-masala qayta uchraydi).

Mexanizm:

• Memoization (top-down): rekursiya + kesh. Hisoblangan natijani saqlab, qayta so'ralganda darrov qaytaradi.
• Tabulation (bottom-up): kichik qism-masaladan boshlab jadvalni to'ldirib, kattasiga boradi. Rekursiya yo'q.

// Fibonacci — memoization (top-down)
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

// Fibonacci — tabulation (bottom-up), O(1) space
function fibTab(n) {
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) { [a, b] = [b, a + b]; }
  return b;
}

Naive rekursiv fibonacci O(2ⁿ) — DP uni O(n)ga tushiradi.

Xato: DP'ni har masala uchun ishlatishga urinish. Overlapping subproblems bo'lmasa (masalan oddiy divide-and-conquer) kesh foyda bermaydi. Yana: state (holat) ni noto'g'ri aniqlash — DP dizaynining eng qiyin qismi.

Follow-up: Qaysi biri afzal? — Tabulation stack overflow'dan xoli va ko'pincha tezroq; memoization yozish oson va faqat kerakli qism-masalalarni hisoblaydi (siyrak holatlarda tejamli).

Masala: Fibonacci'ni DP bilan — yuqorida yechilgan. Time O(n), Space O(1) (tabulation).

Masala: 0/1 Knapsack (ryukzak masalasi)

Yondashuv: Har buyum uchun ikki tanlov: olish yoki olmaslik. dp[i][w] = birinchi i buyum va w sig'im bilan maksimal qiymat. Har buyumda ikki variantning maksimumini olamiz.

Yechim:

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w]; // buyumni olmaslik
      if (weights[i - 1] <= w) {
        // olish: qolgan sig'imdagi eng yaxshi + shu qiymat
        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
      }
    }
  }
  return dp[n][capacity];
}
// knapsack([1,3,4], [15,20,30], 4) -> 35

Vaqt/Xotira: Time O(n × capacity), Space O(n × capacity).

Optimizatsiya: dp[i] faqat dp[i-1]ga bog'liq — bir o'lchovli massivga siqib, wni teskari aylanib, space'ni O(capacity)ga tushirish mumkin.

Masala: Longest Common Subsequence (LCS)

Yondashuv: dp[i][j] = aning birinchi i va bning birinchi j belgisidagi eng uzun umumiy ketma-ketlik. Belgilar mos kelsa 1 + dioganal; aks holda ikki qo'shni katakning maksimumi.

Yechim:

function lcs(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[m][n];
}
// lcs("ABCBDAB", "BDCAB") -> 4  ("BCAB")

Vaqt/Xotira: Time O(m × n), Space O(m × n).

Optimizatsiya: Faqat uzunlik kerak bo'lsa, ikki qatorli (O(min(m,n))) space yetarli. Aslidagi ketma-ketlikni tiklash uchun to'liq jadval saqlanadi.

S: Greedy algoritm nima? DP'dan qanday farq qiladi? (Middle)

Ta'rif: Greedy — har qadamda shu ondagi eng yaxshi (lokal optimal) tanlovni qiladi, orqaga qaytmaydi. Ba'zi masalalarda bu global optimalga olib keladi.

Mexanizm: Greedy tez va oddiy, lekin faqat greedy xossasi (greedy choice property) bo'lgan masalalarda to'g'ri ishlaydi. DP barcha variantlarni ko'radi (sekinroq, lekin kafolatli), greedy bitta yo'lni tanlaydi.

// Coin change (greedy — faqat kanonik tanga tizimida to'g'ri)
function coinsGreedy(coins, amount) {
  coins.sort((a, b) => b - a); // kattadan
  let count = 0;
  for (const c of coins) {
    while (amount >= c) { amount -= c; count++; }
  }
  return amount === 0 ? count : -1;
}

Xato: Greedy'ni isbotsiz ishonch bilan qo'llash. Masalan tangalar [1, 3, 4], summa 6: greedy 4+1+1 = 3 tanga beradi, optimal esa 3+3 = 2. Bunday holda DP kerak.

Follow-up: Greedy to'g'riligini qanday isbotlaysiz? — Exchange argument (almashtirish) yoki greedy-stays-ahead usuli bilan; yoki klassik masala (interval scheduling, Huffman, Dijkstra) ekanini tan olish.

12. Intervyu patternlari va klassik masalalar

12.1 Two Pointers

Naqsh: Saralangan massiv yoki ikki uchdan yaqinlashuvchi ko'rsatkichlar bilan O(n²)ni O(n)ga tushirish.

Masala: Palindrome tekshirish

Yondashuv: Ikki ko'rsatkich — bosh va oxir; ular yaqinlashguncha belgilarni solishtiramiz.

function isPalindrome(s) {
  s = s.toLowerCase().replace(/[^a-z0-9]/g, ''); // faqat harf/raqam
  let l = 0, r = s.length - 1;
  while (l < r) {
    if (s[l] !== s[r]) return false;
    l++; r--;
  }
  return true;
}
// isPalindrome("A man, a plan, a canal: Panama") -> true

Time O(n), Space O(n) (tozalash uchun; joyida indeks bilan O(1) ham mumkin).

Masala: Two Sum II (saralangan massiv)

Yondashuv: Ikki uchdan: yig'indi kichik bo'lsa chap ko'rsatkichni o'ngga, katta bo'lsa o'ng ko'rsatkichni chapga suramiz.

function twoSumSorted(nums, target) {
  let l = 0, r = nums.length - 1;
  while (l < r) {
    const sum = nums[l] + nums[r];
    if (sum === target) return [l, r];
    if (sum < target) l++; else r--;
  }
  return [];
}

Time O(n), Space O(1) — hash map variantidan xotira jihatidan afzal.

12.2 Sliding Window

Naqsh: Uzluksiz qism-massiv/qism-satr ustidagi masalalarda oynani kengaytirib-toraytirib, qayta hisoblashni tejash.

Masala: Takrorlanmaydigan eng uzun qism-satr (Longest Substring Without Repeating)

Yondashuv: O'ng chegarani suramiz; takror belgi kelsa, chap chegarani takror yo'qolguncha suramiz. Har belgi oxirgi ko'rilgan indeksini map'da saqlaymiz.

function lengthOfLongestSubstring(s) {
  const lastSeen = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {
      left = lastSeen.get(ch) + 1; // oynani takrordan keyingiga sur
    }
    lastSeen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}
// lengthOfLongestSubstring("abcabcbb") -> 3 ("abc")

Time O(n), Space O(k) (noyob belgilar).

Masala: Kattaligi k bo'lgan maksimal yig'indili qism-massiv

Yondashuv: Sobit o'lchamli oyna: dastlabki k yig'indini olamiz, keyin oynani suramiz — kirgan elementni qo'shib, chiqqanini ayiramiz.

function maxSubarraySum(arr, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += arr[i];
  let best = windowSum;
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // sur
    best = Math.max(best, windowSum);
  }
  return best;
}
// maxSubarraySum([2,1,5,1,3,2], 3) -> 9  ([5,1,3])

Time O(n), Space O(1). Naive qayta hisoblash O(n·k) bo'lardi.

12.3 Fast & Slow Pointers

Naqsh: Ikki ko'rsatkich turli tezlikda (Floyd's cycle detection) — sikl aniqlash, o'rtani topish.

Masala: Linked List'da sikl bormi (Detect Cycle)

Yondashuv: slow bir qadam, fast ikki qadam yuradi. Sikl bo'lsa, ular albatta uchrashadi; fast oxirga yetsa — sikl yo'q.

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;         // 1 qadam
    fast = fast.next.next;    // 2 qadam
    if (slow === fast) return true; // uchrashdi  sikl
  }
  return false;
}

Time O(n), Space O(1) — hash set variantidan (O(n) space) afzal.

Masala: Linked List o'rtasini toping (Middle of Linked List)

Yondashuv: fast oxirga yetganda slow aynan o'rtada bo'ladi.

function middleNode(head) {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  return slow; // o'rta tugun
}

Time O(n), Space O(1).

12.4 Merge Intervals

Naqsh: Oraliqlarni boshlanishi bo'yicha sortlab, ustma-ust tushganlarni birlashtirish.

Masala: Merge Intervals

Yondashuv: Boshlanish bo'yicha sortlaymiz; joriy oraliq oxirgi natijaning oxiri bilan kesishsa birlashtiramiz, aks holda yangi oraliq sifatida qo'shamiz.

function mergeIntervals(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const res = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = res[res.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]); // birlashtir
    } else {
      res.push(intervals[i]);
    }
  }
  return res;
}
// mergeIntervals([[1,3],[2,6],[8,10],[15,18]]) -> [[1,6],[8,10],[15,18]]

Time O(n log n) (sort), Space O(n) (natija).

12.5 Backtracking

Naqsh: Barcha variantlarni daraxt sifatida ko'rib, yaroqsizini tashlab (prune), yechim qurish.

Masala: Barcha permutatsiyalar (Permutations)

Yondashuv: Har pozitsiya uchun ishlatilmagan har elementni sinab ko'ramiz, chuqur kiramiz, keyin orqaga qaytib (backtrack) tanlovni bekor qilamiz.

function permute(nums) {
  const res = [];
  function backtrack(current, remaining) {
    if (remaining.length === 0) { res.push([...current]); return; }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      backtrack(current, [...remaining.slice(0, i), ...remaining.slice(i + 1)]);
      current.pop(); // backtrack
    }
  }
  backtrack([], nums);
  return res;
}
// permute([1,2,3]) -> 6 ta permutatsiya

Time O(n · n!), Space O(n) (rekursiya, natijasiz).

Masala: Subsets (barcha qism-to'plamlar)

Yondashuv: Har element uchun ikki tanlov — olish yoki olmaslik.

function subsets(nums) {
  const res = [];
  function backtrack(start, path) {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(0, []);
  return res;
}
// subsets([1,2,3]) -> 8 ta (2^3) qism-to'plam

Time O(n · 2ⁿ), Space O(n).

12.6 Binary Search variantlari

Masala: Aylantirilgan saralangan massivda qidiruv (Search in Rotated Sorted Array)

Yondashuv: Har qadamda yarmlardan biri albatta saralangan. midni tekshirib, target qaysi saralangan yarimda ekanini aniqlab, o'sha tomonga o'tamiz.

function searchRotated(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[lo] <= nums[mid]) {          // chap yarim saralangan
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                               // o'ng yarim saralangan
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}
// searchRotated([4,5,6,7,0,1,2], 0) -> 4

Time O(log n), Space O(1).

12.7 Kadane (Maximum Subarray)

Masala: Maksimal yig'indili uzluksiz qism-massiv (Maximum Subarray)

Yondashuv: Har pozitsiyada: "shu elementdan yangi boshlanish" yoki "avvalgi qism-massivga qo'shilish" — kattasini tanlaymiz. Global maksimumni yangilab boramiz.

function maxSubArray(nums) {
  let current = nums[0], best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]); // yangimi yoki davommi
    best = Math.max(best, current);
  }
  return best;
}
// maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) -> 6  ([4,-1,2,1])

Time O(n), Space O(1). Naive barcha qism-massivlar O(n²) bo'lardi.

12.8 FizzBuzz (klassik skrining)

Masala: FizzBuzz

Yondashuv: 1 dan n gacha: 3 va 5 ga bo'linsa "FizzBuzz", 3 ga "Fizz", 5 ga "Buzz", aks holda sonning o'zi.

function fizzBuzz(n) {
  const res = [];
  for (let i = 1; i <= n; i++) {
    let s = '';
    if (i % 3 === 0) s += 'Fizz';
    if (i % 5 === 0) s += 'Buzz';
    res.push(s || String(i));
  }
  return res;
}

Time O(n), Space O(n). E'tibor: 15 ni alohida tekshirmaslik — Fizz+Buzz birikmasidan avtomatik chiqadi.

Eng ko'p uchraydigan 15 masala

Intervyularda eng tez-tez uchraydigan masalalar. Har birini yodlamang — naqshini tushuning va qayta yecha oling.

Masala 10 uchun bonus yechim (Best Time to Buy and Sell Stock):

Yondashuv: Shu paytgacha ko'rilgan eng past narxni saqlaymiz; har kuni "bugun sotsam qancha foyda" ni hisoblab, maksimumni yangilaymiz.

function maxProfit(prices) {
  let minPrice = Infinity, maxProfit = 0;
  for (const price of prices) {
    minPrice = Math.min(minPrice, price);       // eng arzon sotib olish
    maxProfit = Math.max(maxProfit, price - minPrice); // eng katta foyda
  }
  return maxProfit;
}
// maxProfit([7,1,5,3,6,4]) -> 5  (1 da olib, 6 da sotish)

Time O(n), Space O(1).

Yakuniy maslahat: Intervyuda avval savolni aniqlashtiring (kirish chegaralari, bo'sh holat, takror qiymatlar), keyin naive yechimni ayting, so'ng optimallashtiring. Kod yozayotganda ovoz chiqarib fikrlang va oxirida Big-Oni aniq ayting. Ishlab beruvchi bir yechim mukammal, lekin ishlamaydigan "optimal" yechimdan yaxshiroq.