Tarkibga o'tish

Masalani yechish yondashuvi

Intervyuga kirgan ko'pchilik bir xil xatoni qiladi: masalani o'qib, darhol kod yoza boshlaydi. Natijada o'rtada adashib qoladi — nima yozayotganini, nima tekshirayotganini bilmaydi.

Yaxshi muhandis masalani yechishda muayyan tartibga amal qiladi. Bu tartib intervyuda ham, mustaqil mashqda ham ishlaydi.

1-qadam: Masalani tushunish

Masala matnini o'qing. Bir marta emas — ikki marta. Keyin o'zingizga savol bering: "Bu masala nima so'rayapti?"

Aniqlashtiring:

  • Kirish nima? Massiv, son, string, daraxt?
  • Chiqish nima? Son, boolean, massiv, string?
  • Cheklovlar qanday? Elementlar soni (n), qiymat oralig'i, musbat/manfiy?
  • Maxsus shartlar bormi? Tartiblangan massiv, bog'liq ro'yxat, ikkilik daraxt?
Masala: "Tartiblangan massivda maqsadli qiymatni qidiring."

Savollar:
- Massiv har doim tartiblangan bo'ladimi?      → HA
- Takrorlanuvchi elementlar bo'ladimi?          → YO'Q
- Topilmasa nima qaytarish kerak?              → -1
- n ning maksimal qiymati nima?                → 10^4

Tushunmasdan yechishga urinish — yo'l xaritasisiz sayohat qilish.

2-qadam: Misollar

Masala bergan misollarni tekshiring. Keyin o'zingiz misollar tuzing:

  • Oddiy holat (2–3 elementli massiv)
  • Katta holat (5–7 element)
  • Edge case'lar (bo'sh massiv, bitta element, barcha bir xil)
Masala: Massivda takrorlanmaydigan elementni toping.

Misollar:
  [2, 2, 1]       → 1        (oddiy)
  [4, 1, 2, 1, 2] → 4        (katta)
  [1]              → 1        (bitta element)
  [0]              → 0        (nol)

Misollar orqali masalaning chegaralari aniqlanadi. Ba'zan misolda yashirin cheklov topiladi.

3-qadam: Qo'pol yechim (Brute Force)

Darhol optimalni izlashga urinmang. Avval ishlayotgan yechim tuzing.

Qo'pol yechim ko'pincha:

  • Ichma-ich tsikllar — O(n²) yoki O(n³)
  • Barcha variantlarni sinab ko'rish
  • Rekursiya (memoizatsiyasiz)
Masala: Ikkita sonning yig'indisi berilgan qiymatga teng bo'lgan indekslarni toping.

Qo'pol yechim:
  FOR i = 0 DAN n - 1 GACHA
    FOR j = i + 1 DAN n - 1 GACHA
      IF nums[i] + nums[j] = target
        RETURN [i, j]

Vaqt: O(n²). Bu yaxshi emas, lekin to'g'ri. Shu yechimdan optimallashtiriladi.

Note

Intervyuda qo'pol yechimni aytmay o'tish noto'g'ri. "Avval O(n²) yechim bor, lekin yaxshilash mumkin" — deb boshlang. Bu fikrlash jarayonini ko'rsatadi.

4-qadam: Optimallashtirish

Qo'pol yechimga qarang:

  • Nima takrorlanayapti?
  • Qayerda ortiqcha ish qilinayapti?
  • Qanday ma'lumot oldindan saqlanishi mumkin?

Asosiy savol: nima ortiqcha hisoblanayapti?

Two Sum uchun:
  Ichki tsikl har i uchun j ni qaytadan qidiradi.
  Agar nums[j] = target - nums[i] ni hashmap da saqlasak —
  har element uchun O(1) da tekshirish mumkin.

Optimallashtirilgan:
  seen = bo'sh hashmap
  FOR i = 0 DAN n - 1 GACHA
    complement = target - nums[i]
    IF complement seen ichida
      RETURN [seen[complement], i]
    seen[nums[i]] = i

Vaqt: O(n). Hashmap qidiruvni O(1) qildi.

5-qadam: Yondashuvni aniqlash

Masalaning xususiyatlariga qarab to'g'ri yondashuvni tanlash:

Masala xususiyati Ko'rib chiqiladigan yondashuv
Tartiblangan massiv, qidirish Ikkilik qidiruv
Ko'p so'rovli qidirish Hashmap / HashSet
Ketma-ket elementlar / kichik massiv Sliding window, Two pointers
Yo'llar soni, minimal/maksimal DP
Barcha variantlar / kombinatsiyalar Backtracking
Graf, bog'liqlik BFS / DFS
Eng qisqa yo'l (vaznsiz) BFS
Eng qisqa yo'l (vaznli) Dijkstra
Minimal/maksimal, lokal tanlov Greedy
Daraxt, rekursiv tuzilma DFS, rekursiya
Topologik tartib Topoligik sort (BFS/DFS)
Diapazon so'rovlari Prefix sum, Segment tree
Ko'p takrorlangan so'rovlar Kehlangan tuzilma (Trie, DSU)

Cheklovdan yondashuvni aniqlash

n ning qiymati qaysi murakkablikni qabul qilishini ko'rsatadi:

n qiymati Qabul qilinadigan murakkablik
n ≤ 10 O(n!), O(2^n)
n ≤ 20 O(2^n), O(n × 2^n)
n ≤ 100 O(n³)
n ≤ 1000 O(n²)
n ≤ 10^5 O(n log n), O(n)
n ≤ 10^6 O(n)
n ≤ 10^9 O(log n), O(1) 
n = 10^5 berilgan.
O(n²) = 10^10 operatsiya — juda ko'p.
O(n log n) = 10^5 × 17 ≈ 1.7 × 10^6 — qabul qilinadi.

Bu jadval "qaysi yondashuvni qidirish kerak?" degan savolga yo'nalish beradi.

6-qadam: Pseudocode

Kod yozishdan oldin pseudocode tuzing. Bu fikrni tartibga keltiradi va xatoliklarni koddan oldin ko'rish imkonini beradi.

Pseudocode:

  • Tilga bog'liq emas
  • Asosiy mantiqni ifodalaydi
  • Sintaktik to'g'rilik shart emas
FUNCTION SOLVE(input)
    // ma'lumot tayyorlaش
    preprocessing...

    // asosiy mantiq
    FOR har bir element
        hisoblash...

    // natijani qaytarish
    RETURN result

Pseudocode tayyor bo'lgandan keyin uni real kodga aylantirish oson.

7-qadam: Murakkablik tahlili

Har yechim uchun ikkita ko'rsatkich:

Vaqt murakkabligi: nechta operatsiya bajariladi?

Bitta tsikl:      O(n)
Ichma-ich tsikl:  O(n²)
Ikkilik qidiruv:  O(log n)
Tsikl + qidiruv:  O(n log n)

Xotira murakkabligi: qo'shimcha qancha xotira ishlatiladi?

Doimiy o'zgaruvchilar:  O(1)
n ta elementli array:   O(n)
n × m matritsa:         O(n × m)
Rekursiya chuqurligi:   O(chuqurlik)

Warning

Rekursiv yechimda call stack ham xotira sarflaydi. Chuqurlik n bo'lsa — xotira O(n), O(1) emas.

8-qadam: Edge case'lar

Eng ko'p xato edge case'larda bo'ladi. Har yechimdan keyin tekshiring:

Holat Misol
Bo'sh kirish [], "", 0
Bitta element [1]
Ikkita element [1, 2]
Barcha bir xil [3, 3, 3]
Manfiy sonlar [-1, -2, 3]
Nol [0, 0]
Maksimal qiymat n = 10^9, INT_MAX
Allaqachon tartiblangan [1, 2, 3]
Teskari tartiblangan [3, 2, 1]

Har masalada barcha holat tegishli bo'lmaydi. Ammo ro'yxatga bir nazar tashlash — ko'pincha biror muhim holat topiladi.

To'liq jarayon: misol

Massivdagi eng uzun ketma-ket pastki massiv topish.

1. Tushunish: - Kirish: butun sonlar massivi - Chiqish: eng uzun o'suvchi pastki massiv uzunligi - "Pastki massiv" — ketma-ket elementlar (indekslari uzluksiz)

2. Misollar: 

[1, 3, 5, 4, 7]  → 3   ([1,3,5] yoki [3,5] emas, [4,7]? Lekin [1,3,5]=3)
[2, 2, 2, 2]     → 1   (o'suvchi yo'q, bitta element)
[1]              → 1
[]               → 0

3. Qo'pol yechim: 

FOR i dan j gacha barcha oraliqlarni tekshirish → O(n²)

4. Optimallashtirish: 

Bir o'tishda: joriy uzunlik va maksimalni saqlash.
Oldingi < keyingi → uzaytiramiz.
Aks holda → qaytadan 1 dan boshlaymiz.

5. Pseudocode: 

FUNCTION LONGEST_INCREASING(nums)
    IF bo'sh: RETURN 0
    max_len = 1
    cur_len = 1

    FOR i = 1 DAN n - 1 GACHA
        IF nums[i] > nums[i - 1]
            cur_len = cur_len + 1
            max_len = MAX(max_len, cur_len)
        ELSE
            cur_len = 1

    RETURN max_len

6. Murakkablik: - Vaqt: O(n) — bir o'tish - Xotira: O(1) — faqat ikkita o'zgaruvchi

7. Edge case'lar: - Bo'sh: 0 - Barcha o'suvchi: n - Barcha kamayuvchi: 1

Tez-tez ishlatiluvchi tuzilmalar

Array/String masalalari uchun

Two Pointers:
  Tartiblangan massiv, juft topish, palindrom
  → left va right indekslari qarama-qarshidan yuradi

Sliding Window:
  Uzluksiz pastki massiv/string, shartli maksimal/minimal
  → oyna kengaytiradi yoki torayadi

Prefix Sum:
  Diapazon yig'indilari, ko'p so'rov
  → prefix[i] = prefix[i-1] + nums[i]

Graf/Daraxt masalalari uchun

BFS:
  Eng qisqa yo'l (vaznsiz), daraja bo'yicha
  → navbat (queue) bilan

DFS:
  Barcha yo'llar, bog'liqlik, daraxt traversal
  → stek yoki rekursiya bilan

Backtracking:
  Barcha kombinatsiyalar/permutatsiyalar
  → tanlash → rekursiya → bekor qilish

Optimizatsiya masalalari uchun

DP:
  Optimal pastki tuzilma + takrorlanuvchi pastki masalalar
  → rekurrentlik tenglamasini toping

Greedy:
  Lokal optimal = global optimal bo'ladigan hollar
  → tanlovni isbotlang (exchange argument)

Intervyuda gaplashish

Intervyuda jimgina kod yozish — noto'g'ri. Fikrlash jarayonini baland ovozda aytib boring:

"Masalani o'qidim. Tartiblangan massiv berilgan, demak ikkilik qidiruvni ko'rish kerak."

"Avval O(n) yechim bor. Ammo tartiblangan bo'lgani uchun O(log n) mumkin."

"Chap va o'ng chegaralarni olib, o'rtadan boshlayman..."

"Edge case: bo'sh massiv uchun -1 qaytarish kerak."

Bu intervyuerga: 1. Siz masalani tushunganingizni ko'rsatadi 2. Yanglishsangiz — to'g'ri yo'nalish berishiga imkon yaratadi 3. Yechim xato bo'lsa ham — fikrlash jarayoni baholanadi

Xulosa: 8 qadamli chiziqli jarayon

1. O'qish    → Masalani to'liq tushunish, savollar berish
2. Misollar  → Berilganlarni sinab ko'rish, o'z misollaringizni tuzish
3. Qo'pol    → Ishlayotgan, sodda yechimni topish
4. Optimallashtirish → Nima ortiqcha? Qanday kamaytirish?
5. Yondashuv → Cheklov va masala turiga qarab algoritm tanlash
6. Pseudocode → Mantiqni kodni yozishdan oldin shakllantirish
7. Murakkablik → Vaqt va xotira tahlili
8. Edge case → Bo'sh, bitta element, maksimal qiymat

Bu tartib birinchi martada sun'iy tuyuladi. Ko'p mashqdan keyin avtomatik bo'lib qoladi.