Algoritmik masala yechish strategiyalari — LeetCode va intervyu uchun (3.13-bob)

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 13-mavzu (yakuniy)

1. Kirish va motivatsiya

Barcha ma'lumotlar tuzilmalari va algoritmlarni (3.1–3.12) o'rgandik. Endi ularni birlashtirib, yangi, tanish bo'lmagan masalaga qanday yondashishni o'rganamiz. Bu — 3-QISMning yakuni va texnik intervyuga tayyorlanishning kaliti.

Eng katta sir: tajribali dasturchi yangi masalani ko'rganda "yangi" deb qo'rqmaydi — u naqsh (pattern) ni izlaydi. "Bu — ikki ko'rsatkich masalasi", "bu — DP", "bu — graf BFS". Naqshlarni bilsangiz (0.6: pattern recognition), minglab masala bir necha tanish turga bo'linadi.

O'xshatish: shifokor bemorni ko'rganda har simptomni "yangi kasallik" deb o'ylamaydi — u naqshni taniydi ("bu — gripp belgilari"). Tajriba — bu naqshlar to'plami. Algoritm masalalari ham shunday: cheksiz ko'rinadi, lekin ~15 ta asosiy naqshga bo'linadi.

Nega muhim?

• Texnik intervyu — deyarli har kompaniyada (LeetCode uslubi).
• Yangi masalaga tizimli yondashuv — qo'rquvni yo'qotadi.
• 3.1–3.12 ni birlashtiradi, mustahkamlaydi.
• Kundalik ishda ham: real muammoni tanish naqshga bog'lash.

2. Nazariya — chuqur tushuntirish

2.1. Masala yechish jarayoni (UMPIRE / 7 qadam)

0.6-bobdagi yondashuvni intervyu uchun aniqlashtiramiz:

  1. UNDERSTAND — masalani aniq tushunish (kirish/chiqish, cheklovlar)
  2. EXAMPLES   — misollar (oddiy + chegaraviy: bo'sh, bitta, max)
  3. APPROACH   — naqshni tanish, strategiya tanlash (avval brute force)
  4. PLAN       — pseudokod 0.6-bob
  5. CODE       — kod yozish
  6. TEST       — misollarni sinash (chegaraviy ham)
  7. OPTIMIZE   — Big-O ni yaxshilash (3.1)

Intervyuda eng muhim: gapirib turish (think out loud). Yechim topolmasangiz ham, fikrlash jarayoningiz baholanadi. Avval brute force, keyin optimallashtiring.

2.2. Avval brute force, keyin optimallashtirish

Eng katta xato — darrov "eng yaxshi" yechimni izlash. To'g'ri yo'l:

  1. BRUTE FORCE — ishlaydigan har qanday yechim (hatto O(n²))
  2. Big-O ni aytish 3.1-bob — "bu O(n²)"
  3. BOTTLENECK ni topish — qaysi qism sekin?
  4. OPTIMALLASHTIRISH — naqsh bilan (Hash Table, ikki ko'rsatkich...)

Brute force — "men masalani tushundim" degani; optimizatsiya — "men yaxshilashni bilaman". Ikkalasi ham muhim.

2.3. Asosiy naqshlar (pattern recognition — 0.6)

Masalalarning katta qismi shu naqshlarga bo'linadi (har biri oldingi boblardan):

2.4. Naqshni tanish — kalit so'zlar

Masala matnidagi signal so'zlar naqshni ko'rsatadi:

  "tartiblangan massiv"        → ikki ko'rsatkich / binary search
  "uzluksiz / ketma-ket"       → sliding window
  "juftlik / yig'indi"         → hash map / ikki ko'rsatkich
  "eng qisqa yo'l"             → BFS
  "barcha kombinatsiya/yo'l"   → backtracking
  "eng ko'p / eng kam (optimal)" → DP yoki greedy
  "top K / eng katta K"        → heap
  "necha usul"                 → DP
  "balanslangan qavs"          → stack

2.5. Vaqt vs xotira savdosi (3.1)

Ko'p masalada tezlikni xotira evaziga sotib olamiz (0.1: caching, 3.5):

  O(n²) ikki tsikl  →  O(n) + Hash Map (O(n) xotira)   [Two Sum — 3.2]
  Qayta hisoblash   →  memoization (O(n) xotira)        [DP — 3.12]

Intervyuda: "Men O(n²) ni O(n) ga tushira olaman, lekin O(n) qo'shimcha xotira evaziga" — bu yaxshi javob.

2.6. Chegaraviy holatlar (edge cases — 0.6)

Yechimni sinashda doim tekshiring:

  - Bo'sh kirish ([], "", null)
  - Bitta element
  - Hammasi bir xil / takror
  - Manfiy sonlar
  - Juda katta kirish (Big-O muhimmi?)
  - Topilmadi / yo'q holat

Intervyuda chegaraviy holatlarni o'zingiz aytib o'tish — kuchli signal.

2.7. Murakkablikni yaxshilash usullari

  O(n²) → O(n log n):  saralash + ikki ko'rsatkich/binary
  O(n²) → O(n):        Hash Map (qidiruv O(1))
  O(2ⁿ) → O(n):        DP / memoization 3.12-bob
  Ko'p qidiruv:        bir marta sort/Hash, keyin tez
  Min/max tez-tez:     Heap (3.8)

2.8. Intervyu maslahatlari

• Aniqlovchi savol bering — cheklovlar, kirish turi, takror bormi.
• Gapirib turing — fikrlashni ovoz chiqarib.
• Brute force'dan boshlang — keyin optimallashtiring.
• Big-O ni ayting — har yechim uchun.
• Test qiling — misol bilan kodni "yuring".
• Toza kod — mazmunli nom (0.6, 15.1).

3. Strategiya — tez ma'lumotnoma

JARAYON:  Understand → Examples → Approach → Plan → Code → Test → Optimize
USLUB:    brute force → Big-O → bottleneck → optimallashtirish
NAQSH:    signal so'zlardan naqshni tanish 2.4-bob
SAVDO:    vaqt ↔ xotira (Hash/memo) 2.5-bob
EDGE:     bo'sh, bitta, takror, manfiy, katta, yo'q 2.6-bob
INTERVYU: aniqlovchi savol berish, gapirib turish, Big-O ni aytish, test qilish

4. Batafsil misollar (jarayonni qo'llash)

Misol 1 — Two Sum (jarayon namoyishi — 2.1, 2.2)

  1. UNDERSTAND: massiv + target; yig'indisi target bo'lgan 2 indeks
  2. EXAMPLES: [2,7,11], target=9 → [0,1]; juftlik yo'q → null
  3. APPROACH: brute force O(n²) → optimallashtirish: Hash Map (naqsh: "juftlik")
  4-5. CODE:

// Brute force — O(n²) (avval)
function twoSumBrute(arr, t) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] + arr[j] === t) return [i, j];
}
// Optimallashtirilgan — O(n), Hash Map (3.5, naqsh — 2.3)
function twoSum(arr, t) {
  const seen = new Map();
  for (let i = 0; i < arr.length; i++) {
    if (seen.has(t - arr[i])) return [seen.get(t - arr[i]), i];  // juftini ko'rdimmi?
    seen.set(arr[i], i);
  }
  return null;   // edge: yo'q (2.6)
}
// 6-7. TEST + OPTIMIZE: O(n²) → O(n) (vaqt vs xotira — 2.5)

Misol 2 — Naqshni tanish mashqi (2.3, 2.4)

  "Tartiblangan massivda yig'indisi target juftlik"
    → "tartiblangan" + "juftlik" → IKKI KO'RSATKICH 3.2-bob

  "Eng uzun takrorsiz substring"
    → "uzluksiz substring" → SLIDING WINDOW 3.2-bob

  "Daraxtning eng chuqur darajasi"
    → daraxt + daraja → BFS yoki DFS 3.6-bob

  "n tanga bilan summani yig'ish min usul"
    → "min" + "necha usul" → DP 3.12-bob

  "Eng katta 3 element"
    → "top K" → HEAP 3.8-bob yoki sort (3.9)

Misol 3 — Optimallashtirish zanjiri (2.7)

// Masala: massivda dublikat bormi?
// V1: brute force O(n²)
function hasDupBrute(arr) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] === arr[j]) return true;
  return false;
}
// V2: sort + qo'shni O(n log n), O(1) xotira
function hasDupSort(arr) {
  const a = [...arr].sort((x, y) => x - y);
  for (let i = 1; i < a.length; i++) if (a[i] === a[i - 1]) return true;
  return false;
}
// V3: Set O(n), O(n) xotira (eng tez — 3.5)
function hasDup(arr) { return new Set(arr).size !== arr.length; }
// Savdo: V3 tezroq, lekin ko'proq xotira (2.5)

Misol 4 — Murakkab masalaga yondashuv (2.1)

  Masala: "Kunlik narxlar massivi; bir marta olib-sotib max foyda"
  1. UNDERSTAND: arr[i] = i-kun narx; oldin ol, keyin sot, max foyda
  2. EXAMPLES: [7,1,5,3,6,4] → 5 (1 da ol, 6 da sot); [7,6,4] → 0
  3. APPROACH:
     - brute force: har juftlik O(n²)
     - optimallashtirish: "eng arzon shu kungacha" bo'lgan qiymatni saqlash → O(n) (DP/sliding g'oya)
  4-5. CODE:

function maxFoyda(narx) {
  let minNarx = Infinity, maxFoyda = 0;
  for (const n of narx) {                  // O(n) — bir o'tish
    minNarx = Math.min(minNarx, n);        // eng arzon shu kungacha
    maxFoyda = Math.max(maxFoyda, n - minNarx);  // shu kunda sotsam foyda
  }
  return maxFoyda;
}
// O(n) vaqt, O(1) xotira — brute force O(n²) o'rniga (2.7)

5. To'g'ri va noto'g'ri holatlar

1) Darrov optimal yechim izlash

❌ masalani ko'rib, darrov "eng yaxshi" yechimni izlab qotib qolish
✅ avval brute force (ishlaydigan), keyin optimallashtirish (2.2)

2) Chegaraviy holatlarni unutish

❌ faqat "oddiy" misolda sinash → intervyuda bo'sh/null da qulaydi
✅ bo'sh, bitta, takror, yo'q — doim tekshiring (2.6)

3) Big-O ni aytmaslik

❌ yechim yozib, murakkabligini bilmaslik
✅ har yechim uchun Big-O (vaqt + xotira) ni ayting (3.1, 2.5)

4) Jim ishlash (intervyuda)

❌ jim o'ylab, yechim topolmay qolish
✅ gapirib turing — fikrlash jarayoni baholanadi (2.8)

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — Masalani noto'g'ri tushunish

Sababi: shoshib kod yozish 0.6-bob. Yechimi: avval aniq tushuning, misol yozing, aniqlovchi savol bering 2.1-bob.

Xato 2 — Noto'g'ri naqsh tanlash

Sababi: signal so'zlarni o'qimaslik 2.4-bob. Yechimi: "tartiblangan?", "uzluksiz?", "optimal?" — kalit so'zlardan naqshni taning.

Xato 3 — Off-by-one / chegara xatosi

Sababi: indeks/shart chegarasi (0.6, 3.10). Yechimi: kichik misolda qo'lda yuring; chegaraviy holatlar.

Xato 4 — Optimallashtira olmaslik

Sababi: naqshlarni bilmaslik 2.3-bob. Yechimi: bottleneck'ni toping; Hash Map/saralash/DP bilan yaxshilang 2.7-bob.

Xato 5 — Vaqt tugashi (intervyuda)

Sababi: bitta yechimga juda ko'p vaqt. Yechimi: brute force'ni tez yozing (ishlaydi), keyin vaqt qolsa optimallashtiring 2.2-bob.

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

• Butun 3-QISM (3.1–3.12): barcha tuzilma/algoritm — bu yerda birlashadi.
• Algoritmik fikrlash 0.6-bob: pattern recognition, decomposition.
• System Design 15.7-bob: kattaroq miqyosda muammo yechish.
• Real ish: har bir feature — muammo yechish; naqshni tanish.
• Kod sifati 15.1-bob: toza, o'qishli yechim.
• Intervyu: texnik suhbatning asosi.

8. Eng yaxshi amaliyotlar (best practices)

• Jarayonga rioya qiling: Understand → Examples → Approach → Plan → Code → Test → Optimize 2.1-bob.
• Brute force'dan boshlang, keyin optimallashtiring 2.2-bob.
• Naqshni taning — signal so'zlardan (2.3, 2.4).
• Big-O ni har doim ayting (vaqt + xotira — 3.1, 2.5).
• Chegaraviy holatlarni o'zingiz aytib o'ting 2.6-bob.
• Gapirib turing (intervyuda — 2.8).
• Ko'p masala yeching — naqshlar barmoq xotirasiga o'tadi 2.3-bob; LeetCode/Codeforces.
• Toza kod — mazmunli nom, kichik funksiya 15.1-bob.

9. Amaliy loyiha: "Masala Yechish Jurnali (Problem-Solving Journal)"

3-QISMni yakunlovchi loyiha — barcha naqshlarni birlashtiradi.

Maqsad

7 qadamli jarayonni, naqsh tanishni va optimallashtirishni odatga aylantirish; barcha asosiy naqshlarni amalda qo'llash.

Talablar (requirements)

Har naqsh uchun kamida bitta masala yeching (10+ masala). Har masala uchun jurnal: 7 qadam 2.1-bob, naqsh nomi 2.3-bob, brute force + optimal versiya, Big-O ikkalasi 3.1-bob, chegaraviy holatlar 2.6-bob:

1. Ikki ko'rsatkich: palindrom yoki saralangan juftlik 3.2-bob.
2. Sliding window: eng uzun takrorsiz substring 3.2-bob.
3. Hash Map: Two Sum (Misol 1) yoki anagram guruhlari 3.5-bob.
4. Binary search: insert position yoki sqrt 3.10-bob.
5. BFS: daraxt/graf eng qisqa yo'l yoki daraja 3.7-bob.
6. Backtracking: subsets yoki permutatsiyalar 3.11-bob.
7. DP: coin change yoki pog'onalar 3.12-bob.
8. Heap: top-K element 3.8-bob.
9. Stack: qavs muvozanati 3.4-bob.
10. Max foyda (Misol 4) — brute force → O(n).
11. Har masala uchun brute force va optimal Big-O farqini yozing 2.7-bob.

Maslahatlar (hint)

• Har masalada signal so'zlardan naqshni taning 2.4-bob.
• Avval brute force (ishlaydi), keyin optimallashtiring 2.2-bob.
• Big-O — vaqt va xotira 2.5-bob.
• Chegaraviy holatlar (bo'sh, bitta, yo'q — 2.6).
• Jurnal formati: masala → 7 qadam → kod → Big-O → o'rganilgan saboq.
• LeetCode/Codeforces'da o'xshash masalalarni qidirib mashq qiling.

"Tayyor" mezonlari (acceptance criteria)

• 10+ masala, har asosiy naqsh qamralgan.
• Har masala uchun naqsh aniqlangan.
• Brute force va optimal versiyalar bor.
• Har yechim Big-O (vaqt+xotira) bilan.
• Chegaraviy holatlar tekshirilgan.
• 7 qadamli jarayon qo'llanilgan (jurnal).
• Optimallashtirish farqi (O(n²)→O(n)) ko'rsatilgan.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa — 3-QISM yakunlandi!

Bu bobda barcha algoritm va tuzilmalarni birlashtirib, masala yechish strategiyasini o'rgandik:

• Jarayon: Understand → Examples → Approach → Plan → Code → Test → Optimize.
• Uslub: brute force → Big-O → bottleneck → optimallashtirish.
• Naqshlar 2.3-bob: ikki ko'rsatkich, sliding window, Hash Map, binary search, BFS/DFS, backtracking, DP, heap, stack — signal so'zlardan tanish 2.4-bob.
• Vaqt vs xotira savdosi (Hash/memo); chegaraviy holatlar; intervyu maslahatlari (gapirib turish, Big-O).

3-QISM (Algoritm va ma'lumotlar tuzilmasi) — to'liq yakunlandi! (13 bob)

Siz endi bilasiz: Big-O, massiv/string algoritmlari, Linked List, Stack, Queue, Hash Table, Tree/BST, Graph, Heap, saralash, qidiruv, rekursiya/backtracking, DP, va masala yechish strategiyalari. Bu — kuchli dasturchi va intervyu tayyorgarligining poydevori.

Keyingi bob — 4.1-bob: Git asoslari (init, add, commit, status, log). 4-QISM (Git va hamkorlik) boshlanadi. Kod yozishni bildik; endi uni boshqarishni — versiyalash, tarix, hamkorlik — o'rganamiz. Git — har bir professional dasturchining kunlik quroli (0.3: terminal'da ishlaydi).

Foydalanilgan rasmiy/ishonchli manbalar

• Universal CS — problem-solving patterns, algorithmic interview preparation
• bigocheatsheet.com — naqshlar va murakkablik (umumlashtirilgan)
• 3.1–3.12 boblar — barcha tuzilma va algoritmlar shu yerda birlashadi