Algoritmik paradigmalar

Daraja:

Rekursiya, xotirada saqlash (memoization), dynamic programming va graph traversal — murakkab masalalarni yechishning asosiy usullari.

Recursion — base case, call stack, tail recursion

Middle

Nima bu?

Rekursiya — funksiya o‘zini chaqiradi. Base case — to‘xtash sharti (aks holda cheksiz loop). Call stack — har chaqiruv stack’ga qo‘shiladi, qaytishda chiqariladi. Tail recursion — rekursiv chaqiruv funksiyaning oxirgi amali; ba’zi tillarda optimizatsiya qilinadi (JavaScript’da emas).

Kod misoli

// Faktorial — base case: n <= 1
function factorial(n) {
  if (n <= 1) return 1
  return n * factorial(n - 1)
}

// Fibonacci — sekin (O(2^n)) — memoization kerak
function fib(n) {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)
}

// Tail recursion uslubi (JS optimizatsiya qilmaydi, lekin tushuncha muhim)
function factorialTail(n, acc = 1) {
  if (n <= 1) return acc
  return factorialTail(n - 1, n * acc)
}

// Sum of array — rekursiv
function sumArray(arr, index = 0) {
  if (index >= arr.length) return 0
  return arr[index] + sumArray(arr, index + 1)
}

// Power — divide and conquer
function power(base, exp) {
  if (exp === 0) return 1
  if (exp % 2 === 0) {
    const half = power(base, exp / 2)
    return half * half
  }
  return base * power(base, exp - 1)
}

console.log(factorial(5)) // 120
console.log(fib(10)) // 55
console.log(sumArray([1, 2, 3, 4, 5])) // 15
console.log(power(2, 10)) // 1024

Imtihonda

  • «Rekursiya qachon ishlatiladi? Base case nima?»
  • «Fibonacci rekursiv yechimning muammosi?» → exponential vaqt, stack chuqurligi
  • «Rekursiyani iteratsiyaga aylantiring»

Yodlash uchun

Har rekursiyada base case bo‘lishi shart; chuqur rekursiya stack overflow xavfi.

Memoization — top-down DP

MiddleSenior

Nima bu?

Memoization — rekursiv yechimda allaqachon hisoblangan natijalarni xotirada saqlash (cache). Top-down DP — yuqoridan pastga: rekursiya + cache. Fibonacci O(2^n) dan O(n) ga tushadi. JavaScript’da Map yoki oddiy ob'ekt ishlatiladi.

Klassik gotcha: function fibMemo(n, memo = new Map()) — default parametr har tashqi chaqiruvda yangi Map yaratadi, lekin ichki rekursiv chaqiruvlar uni explicit uzatgani uchun bitta umumiy cache bo‘lib qoladi. Agar kimdir memoni uzatishni unutib qoladigan qilib yozsa (masalan, closure'siz global memoize wrapper'da args key sifatida faqat bitta argument ishlatilsa), cache "urish" (hit) bo‘lmay qoladi va yechim yana O(2^n)ga qaytadi — bu memoization kodini review qilishda eng ko‘p uchraydigan xato. Yana bir nuance: memoize() wrapper'dagi JSON.stringify(args) kalit sifatida ishlaydi, lekin ob'ekt property tartibi yoki undefined/funksiya argumentlar bilan noto‘g‘ri yoki mos kelmaydigan kalit hosil qilishi mumkin.

Kod misoli

// Fibonacci + memoization
function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n
  if (memo.has(n)) return memo.get(n)
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo)
  memo.set(n, result)
  return result
}

// Climbing stairs — n pog'ona, 1 yoki 2 qadam
function climbStairs(n, memo = new Map()) {
  if (n <= 2) return n
  if (memo.has(n)) return memo.get(n)
  const result = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
  memo.set(n, result)
  return result
}

// Coin change — minimal tangalar soni
function coinChange(coins, amount, memo = new Map()) {
  if (amount === 0) return 0
  if (amount < 0) return Infinity
  if (memo.has(amount)) return memo.get(amount)

  let min = Infinity
  for (const coin of coins) {
    const result = coinChange(coins, amount - coin, memo)
    if (result !== Infinity) min = Math.min(min, result + 1)
  }
  memo.set(amount, min)
  return min
}

// Closure bilan memoization wrapper
function memoize(fn) {
  const cache = new Map()
  return function (...args) {
    const key = JSON.stringify(args)
    if (cache.has(key)) return cache.get(key)
    const result = fn.apply(this, args)
    cache.set(key, result)
    return result
  }
}

const fibCached = memoize((n) => {
  if (n <= 1) return n
  return fibCached(n - 1) + fibCached(n - 2)
})

console.log(fibMemo(50)) // 12586269025 — tez
console.log(climbStairs(10)) // 89
console.log(coinChange([1, 2, 5], 11)) // 3 (5+5+1)
console.log(fibCached(50))

Imtihonda

  • «Fibonacci ni memoization bilan optimallashtiring»
  • «Top-down va bottom-up DP farqi?»
  • «Coin change masalasini qanday yechasiz?»

Yodlash uchun

Takroriy subproblemlar bor + rekursiya → memoization (top-down DP).

Dynamic Programming — tabulation, bottom-up

Senior

Nima bu?

Bottom-up DP (tabulation) — kichik subproblemlardan boshlab, jadval (array) to‘ldiriladi. Rekursiya stack kerak emas. Optimal substructure — optimal yechim subproblemlarning optimal yechimidan tuziladi. Overlapping subproblems — bir xil subproblemlar qayta-qayta hisoblanadi.

Vs memoization (top-down): tabulation stack overflow xavfini yo‘qotadi va odatda tezroq ishlaydi (funksiya chaqiruv overhead'i yo‘q), lekin barcha subproblemlarni tartib bilan hisoblaydi — hatto kerak bo‘lmagan holatlarni ham (masalan, faqat bitta chuqur yo‘l kerak bo‘lganda). Memoization esa faqat aslida kerak bo‘lgan subproblemlarni hisoblaydi ("lazy"). Xotira optimizatsiyasi — muhim Senior nuance: climbStairsTab misolida butun dp[] massiv o‘rniga faqat oxirgi ikki qiymat (prev1, prev2) saqlanadi, chunki dp[i] faqat dp[i-1] va dp[i-2] ga bog‘liq — bu O(n) xotirani O(1) ga tushiradi ("rolling array" texnikasi) va ko‘p 1D DP masalalarida qo‘llanadi, lekin 2D DP (Knapsack, LCS) da odatda faqat oldingi qatorni saqlash orqali O(n×m) dan O(m) ga tushiriladi.

Kod misoli

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

// Climbing stairs — bottom-up, O(1) xotira
function climbStairsTab(n) {
  if (n <= 2) return n
  let prev2 = 1
  let prev1 = 2
  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2
    prev2 = prev1
    prev1 = current
  }
  return prev1
}

// 0/1 Knapsack — bottom-up
function knapsack(weights, values, capacity) {
  const n = weights.length
  const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0))

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(
          dp[i - 1][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]
        )
      } else {
        dp[i][w] = dp[i - 1][w]
      }
    }
  }
  return dp[n][capacity]
}

// Longest Common Subsequence
function lcs(text1, text2) {
  const m = text1.length
  const n = text2.length
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0))

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[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]
}

console.log(fibTab(10)) // 55
console.log(climbStairsTab(10)) // 89
console.log(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)) // 9
console.log(lcs('abcde', 'ace')) // 3

Imtihonda

  • «DP masala ekanligini qanday aniqlaysiz?»
  • «Knapsack masalasini bottom-up yeching»
  • «Memoization vs tabulation — qaysi biri qachon yaxshiroq?»

Yodlash uchun

Overlapping subproblems + optimal substructure = DP; bottom-up stack xavfsizroq.

DP jadvalining o‘lchami va holatini aniqlash — intervyuning muhim qismi. Avval rekursiv formulani, keyin jadvalni chizing.

BFS — Breadth First Search (queue)

Senior

Nima bu?

BFS — graph yoki tree’ni kenglik bo‘yicha ko‘rib chiqish. Queue ishlatiladi: birinchi qo‘shilgan birinchi chiqadi. Eng qisqa yo‘l (unweighted graph) va level-order traversal uchun ideal. Vaqt O(V + E), xotira O(V).

Muhim gotcha: visitedga node navbatga qo‘shilganda (enqueue vaqtida) belgilanishi kerak, dequeue qilinganda emas — aks holda bir xil node bir necha marta navbatga tushib qolishi mumkin (ayniqsa zich graph'da), bu esa vaqtni sezilarli oshiradi va ba’zi holatlarda noto‘g‘ri natija beradi. BFS faqat vaznsiz (unweighted) graph'da eng qisqa yo‘lni kafolatlaydi — vaznli graph'da Dijkstra (priority queue) kerak, chunki BFS "qadamlar soni"ni minimallashtiradi, "og‘irlik yig‘indisi"ni emas.

Kod misoli

function buildGraph(edges) {
  const graph = new Map()
  for (const [a, b] of edges) {
    if (!graph.has(a)) graph.set(a, [])
    if (!graph.has(b)) graph.set(b, [])
    graph.get(a).push(b)
    graph.get(b).push(a)
  }
  return graph
}

// BFS — graph traversal
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 neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor)
        queue.push(neighbor)
      }
    }
  }
  return order
}

// Eng qisqa yo'l (unweighted graph)
function shortestPath(graph, start, end) {
  if (start === end) return [start]
  const visited = new Set([start])
  const queue = [[start, [start]]]

  while (queue.length) {
    const [node, path] = queue.shift()
    for (const neighbor of graph.get(node) || []) {
      if (neighbor === end) return [...path, neighbor]
      if (!visited.has(neighbor)) {
        visited.add(neighbor)
        queue.push([neighbor, [...path, neighbor]])
      }
    }
  }
  return null
}

// Grid BFS — eng qisqa yo'l (labirint)
function gridBFS(grid, start, end) {
  const rows = grid.length
  const cols = grid[0].length
  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
  const visited = new Set([`${start[0]},${start[1]}`])
  const queue = [[start[0], start[1], 0]]

  while (queue.length) {
    const [r, c, dist] = queue.shift()
    if (r === end[0] && c === end[1]) return dist
    for (const [dr, dc] of dirs) {
      const nr = r + dr
      const nc = c + dc
      const key = `${nr},${nc}`
      if (
        nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
        grid[nr][nc] !== 1 && !visited.has(key)
      ) {
        visited.add(key)
        queue.push([nr, nc, dist + 1])
      }
    }
  }
  return -1
}

const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]
const graph = buildGraph(edges)
console.log(bfs(graph, 0)) // [0, 1, 2, 3, 4]
console.log(shortestPath(graph, 0, 4)) // [0, 1, 3, 4] yoki [0, 2, 3, 4]

const grid = [
  [0, 0, 1, 0],
  [1, 0, 1, 0],
  [0, 0, 0, 0],
]
console.log(gridBFS(grid, [0, 0], [2, 3])) // 5

Imtihonda

  • «BFS va DFS farqi — qachon qaysi biri?»
  • «Unweighted graphda eng qisqa yo‘l?» → BFS
  • «Grid labirintda minimal qadam soni»

Yodlash uchun

Eng qisqa yo‘l (unweighted) yoki level-order → BFS + queue.

DFS — Depth First Search (stack/recursion)

Senior

Nima bu?

DFS — graph yoki tree’ni chuqurlik bo‘yicha ko‘rib chiqish. Rekursiya yoki stack bilan amalga oshiriladi. Barcha yo‘llarni topish, cycle detection, topological sort uchun qulay. Vaqt O(V + E).

Gotcha: rekursiv DFS juda katta yoki chuqur graph'da (masalan, 100 000+ node ketma-ket zanjir) call stack limitiga urilib RangeError: Maximum call stack size exceeded berishi mumkin — shu sababli production kodda iterativ (explicit stack) versiya xavfsizroq. Cycle detection ham directed va undirected graph'da boshqacha ishlaydi: directed graph'da yuqoridagi kabi inStack (recursion stack) kuzatiladi, chunki faqat "orqaga qaytish" emas, balki hozirgi yo‘l ichidagi qaytish cycle hisoblanadi; undirected graph'da esa shunchaki visited + "parent orqali qaytmadikmi" tekshiruvi yetarli — directed algoritmni undirected graph'ga qo‘llash yolg‘on cycle topib beradi.

Kod misoli

function buildGraph(edges) {
  const graph = new Map()
  for (const [a, b] of edges) {
    if (!graph.has(a)) graph.set(a, [])
    if (!graph.has(b)) graph.set(b, [])
    graph.get(a).push(b)
    graph.get(b).push(a)
  }
  return graph
}

// DFS — rekursiv
function dfsRecursive(graph, node, visited = new Set(), order = []) {
  visited.add(node)
  order.push(node)
  for (const neighbor of graph.get(node) || []) {
    if (!visited.has(neighbor)) {
      dfsRecursive(graph, neighbor, visited, order)
    }
  }
  return order
}

// DFS — iterativ (stack)
function dfsIterative(graph, start) {
  const visited = new Set()
  const stack = [start]
  const order = []

  while (stack.length) {
    const node = stack.pop()
    if (visited.has(node)) continue
    visited.add(node)
    order.push(node)
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) stack.push(neighbor)
    }
  }
  return order
}

// Cycle detection — directed graph
function hasCycleDirected(graph) {
  const visited = new Set()
  const inStack = new Set()

  function dfs(node) {
    visited.add(node)
    inStack.add(node)
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor)) return true
      } else if (inStack.has(neighbor)) {
        return true
      }
    }
    inStack.delete(node)
    return false
  }

  for (const node of graph.keys()) {
    if (!visited.has(node) && dfs(node)) return true
  }
  return false
}

// Orollar soni — grid DFS
function numIslands(grid) {
  const rows = grid.length
  const cols = grid[0].length
  let count = 0

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') return
    grid[r][c] = '0'
    dfs(r + 1, c)
    dfs(r - 1, c)
    dfs(r, c + 1)
    dfs(r, c - 1)
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++
        dfs(r, c)
      }
    }
  }
  return count
}

const edges = [[0, 1], [0, 2], [1, 3], [2, 3]]
const graph = buildGraph(edges)
console.log(dfsRecursive(graph, 0)) // [0, 1, 3, 2]
console.log(dfsIterative(graph, 0))

const grid = [
  ['1', '1', '0', '0'],
  ['1', '0', '0', '1'],
  ['0', '0', '1', '1'],
]
console.log(numIslands(grid)) // 2

Imtihonda

  • «DFS rekursiv va iterativ farqi?»
  • «Graphda cycle qanday aniqlanadi?»
  • «Number of Islands masalasini qanday yechasiz?»

Yodlash uchun

Chuqur ko‘rib chiqish, barcha yo‘l, orollar → DFS; eng qisqa yo‘l → BFS.