3.13-bob: Masala yechish strategiyalari (LeetCode uslubida)

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 tushun (kirish/chiqish, cheklovlar)
  2. EXAMPLES   — misollar (oddiy + chegaraviy: bo'sh, bitta, max)
  3. APPROACH   — naqshni tani, strategiya tanla (avval brute force)
  4. PLAN       — pseudokod 0.6-bob
  5. CODE       — yoz
  6. TEST       — misollarni sina (chegaraviy ham)
  7. OPTIMIZE   — Big-O ni yaxshila (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 optimallashtir

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 ayt 3.1-bob — "bu O(n²)"
  3. BOTTLENECK ni top — qaysi qism sekin?
  4. OPTIMALLASHTIR — 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  optimallashtir
NAQSH:    signal so'zlardan naqshni tani 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, gapirib tur, Big-O, test

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²)  optimallashtir 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²)
     - optimallashtir: "eng arzon shu kungacha" ni yodla  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 optimallashtir (2.2)

2) Chegaraviy holatlarni unutish

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

3) Big-O ni aytmaslik

 yechim yozib, murakkabligini bilmaslik
 har yechim uchun Big-O (vaqt + xotira) ayt (3.1, 2.5)

4) Jim ishlash (intervyuda)

 jim o'ylab, yechim topolmay qolish
 gapirib tur — 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 optimallashtir.
• Naqshlar 2.3-bob: ikki ko'rsatkich, sliding window, Hash Map, binary search, BFS/DFS, backtracking, DP, heap, stack — signal so'zlardan tanib 2.4-bob.
• Vaqt vs xotira savdosi (Hash/memo); chegaraviy holatlar; intervyu maslahatlari (gapirib tur, 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