Ma'lumot tuzilmalari

Daraja:

To‘g‘ri ma’lumot tuzilmasini tanlash algoritm samaradorligining kaliti. Har bir tuzilmaning qo‘shish, o‘qish, qidirish va o‘chirish amallari turli murakkablikka ega.

Array — in-place va funksional usullar

Junior

Nima bu?

Array — ketma-ket xotirada joylashgan elementlar to‘plami. Index bo‘yicha kirish O(1), oxiriga push/pop amortized O(1), boshiga unshift/splice O(n). In-place usul mavjud massivni o‘zgartiradi (xotira tejaydi), funksional usul yangi massiv qaytaradi (asl ma’lumot saqlanadi).

Kod misoli

const nums = [3, 1, 4, 1, 5]

// In-place: massiv ichida o'zgartirish
function removeEvensInPlace(arr) {
  let write = 0
  for (let read = 0; read < arr.length; read++) {
    if (arr[read] % 2 !== 0) {
      arr[write] = arr[read]
      write++
    }
  }
  arr.length = write
  return arr
}

// Funksional: yangi massiv (asl o'zgarmaydi)
const evensRemoved = nums.filter((x) => x % 2 === 0)
const doubled = nums.map((x) => x * 2)
const sum = nums.reduce((acc, x) => acc + x, 0)

// In-place teskari aylantirish
function reverseInPlace(arr) {
  for (let i = 0, j = arr.length - 1; i < j; i++, j--) {
    ;[arr[i], arr[j]] = [arr[j], arr[i]]
  }
  return arr
}

console.log(removeEvensInPlace([1, 2, 3, 4, 5])) // [1, 3, 5]
console.log(reverseInPlace([1, 2, 3])) // [3, 2, 1]

Imtihonda

  • «Massiv boshiga element qo‘shish murakkabligi qanday?»
  • «In-place va yangi massiv yaratish farqi nima? Qachon qaysi biri?»
  • «filter va manual loop bilan in-place filtrlash farqi?»

Yodlash uchun

Index kirish O(1), boshiga qo‘shish O(n) — ko‘p bosh operatsiyasi bo‘lsa linked list yoki boshqa tuzilma ko‘rib chiqiladi.

HashMap / Map / Set — O(1) amallar

JuniorMiddle

Nima bu?

HashMap (JavaScript’da Map yoki oddiy Object) kalit-qiymat juftliklarini saqlaydi. Set faqat noyob qiymatlarni saqlaydi. O‘rtacha get, set, has, delete amallari O(1). Bu tez lookup, frequency counting va duplicate tekshirish uchun ideal.

Gotcha: O(1) — amortizatsiyalangan o‘rtacha, eng yomon holatda (ko‘p hash collision bo‘lsa) O(n) gacha yomonlashishi mumkin. Yana muhim farq: oddiy Objectda kalit har doim string yoki symbolga aylanadi (obj[1] va obj['1'] bir xil kalit), Mapda esa istalgan tip (ob’ekt, NaN, funksiya) o‘zgarmasdan kalit bo‘la oladi va NaN === NaN false bo‘lsa ham Map uni bir xil kalit deb hisoblaydi (SameValueZero). Object prototipdan meros property’larga ega (toString, __proto__) — buni oldini olish uchun Object.create(null) yoki to‘g‘ridan-to‘g‘ri Map afzal.

Kod misoli

// Map — istalgan tip kalit, tartib saqlanadi
const userScores = new Map()
userScores.set('Ali', 95)
userScores.set('Vali', 87)
userScores.set('Ali', 98) // yangilash
console.log(userScores.get('Ali')) // 98
console.log(userScores.has('Vali')) // true

// Set — noyob elementlar
const unique = new Set([1, 2, 2, 3, 3, 3])
console.log([...unique]) // [1, 2, 3]

// Frequency counter — intervyuda juda ko'p
function countChars(str) {
  const freq = new Map()
  for (const ch of str) {
    freq.set(ch, (freq.get(ch) || 0) + 1)
  }
  return freq
}

// Two Sum uchun Map
function twoSum(nums, target) {
  const seen = new Map() // qiymat -> index
  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 null
}

console.log(twoSum([2, 7, 11, 15], 9)) // [0, 1]

Imtihonda

  • «Object va Map farqi nima? Qachon Map ishlatasiz?»
  • «Anagram tekshirish uchun qanday tuzilma?» → frequency Map
  • «Two Sum ni Map siz va Map bilan qanday yechasiz?»

Yodlash uchun

Tez lookup kerak bo‘lsa — Map/Set; tartib muhim bo‘lsa — Map Object’dan yaxshiroq.

Object kalitlari stringga aylanadi; Map da `{ }` yoki `[]` ham kalit bo‘lishi mumkin.

Stack va Queue — LIFO, FIFO

Middle

Nima bu?

Stack (LIFO — Last In First Out): oxirgi qo‘shilgan birinchi chiqadi. Masalan: undo, qavs tekshirish, DFS. Queue (FIFO — First In First Out): birinchi qo‘shilgan birinchi chiqadi. Masalan: BFS, task navbat. JavaScript’da stack uchun push/pop, queue uchun push/shift ishlatiladi.

Gotcha: push/pop massiv oxirida ishlagani uchun O(1), lekin shift() massiv boshidan olib, qolgan barcha elementlarni chapga suradi — bu O(n). Demak yuqoridagi Queue klassi katta hajmda sekin ishlaydi; ishlab chiqarish darajasidagi yechim uchun ikkita stack (enqueue/dequeue stack) yoki circular buffer/linked-list asosidagi navbat ishlatiladi, ular haqiqiy amortizatsiyalangan O(1) beradi.

Kod misoli

// Stack — qavs to'g'riligini tekshirish
function isValidParentheses(s) {
  const stack = []
  const pairs = { ')': '(', ']': '[', '}': '{' }
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch)
    } else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false
    }
  }
  return stack.length === 0
}

console.log(isValidParentheses('({[]})')) // true
console.log(isValidParentheses('([)]')) // false

// Queue — BFS uchun
class Queue {
  constructor() {
    this.items = []
  }
  enqueue(item) {
    this.items.push(item)
  }
  dequeue() {
    return this.items.shift()
  }
  isEmpty() {
    return this.items.length === 0
  }
}

const q = new Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
console.log(q.dequeue()) // 1
console.log(q.dequeue()) // 2

Imtihonda

  • «Valid parentheses masalasini qanday yechasiz?»
  • «Stack va Queue qachon ishlatiladi?»
  • «BFS uchun nima kerak — stack yoki queue?»

Yodlash uchun

Orqaga qaytish/undo → Stack; navbat/tartib bilan ishlash → Queue.

Linked List — yaratish, traversal

MiddleSenior

Nima bu?

Linked List — har bir node keyingi node’ga ko‘rsatkich (next) saqlaydi. Array’dan farqi: index kirish O(n), lekin boshiga qo‘shish/o‘chirish O(1) (pointer o‘zgartirish). Traversal — boshidan oxirigacha har bir node’ni ko‘rib chiqish.

Kod misoli

class ListNode {
  constructor(val, next = null) {
    this.val = val
    this.next = next
  }
}

// Massivdan linked list yaratish
function arrayToList(arr) {
  const dummy = new ListNode(0)
  let current = dummy
  for (const val of arr) {
    current.next = new ListNode(val)
    current = current.next
  }
  return dummy.next
}

// Traversal — massivga aylantirish
function listToArray(head) {
  const result = []
  let current = head
  while (current) {
    result.push(current.val)
    current = current.next
  }
  return result
}

// Teskari aylantirish (in-place)
function reverseList(head) {
  let prev = null
  let current = head
  while (current) {
    const next = current.next
    current.next = prev
    prev = current
    current = next
  }
  return prev
}

// Ikkinchi yarmi o'rtasini topish (slow/fast pointer)
function findMiddle(head) {
  let slow = head
  let fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
  }
  return slow
}

const list = arrayToList([1, 2, 3, 4, 5])
console.log(listToArray(list)) // [1, 2, 3, 4, 5]
console.log(listToArray(reverseList(list))) // [5, 4, 3, 2, 1]
console.log(findMiddle(arrayToList([1, 2, 3, 4, 5])).val) // 3

Imtihonda

  • «Linked list ni teskari aylantiring»
  • «Cycle bor-yo‘qligini qanday aniqlaysiz?» → Floyd's tortoise and hare
  • «Array va Linked List farqi — qachon qaysi biri?»

Yodlash uchun

Ko‘p bosh operatsiyasi va kam index kirish → Linked List; tez index kirish → Array.

Tree — binary tree, BST traversal

Senior

Nima bu?

Binary Tree — har node’da ko‘pi bilan 2 ta farzand. BST (Binary Search Tree) da chap farzand ota, o‘ng farzand ota. Traversal turlari: Inorder (L-O-R, BST da tartiblangan), Preorder (O-L-R), Postorder (L-R-O), Level-order (BFS).

Muhim gotcha: BST'dagi qidiruv, qo‘shish va o‘chirish O(log n) faqat daraxt balanslangan bo‘lsa. Elementlar tartiblangan ketma-ketlikda qo‘shilsa (masalan, 1, 2, 3, 4, 5), daraxt aslida linked list'ga aylanadi va murakkablik O(n)ga tushib ketadi — bu Senior intervyularda ko‘p so‘raladigan "nega BST har doim O(log n) emas" savoli. Shu sababli production'da AVL yoki Red-Black Tree kabi o‘z-o‘zini balanslovchi daraxtlar ishlatiladi. Rekursiv traversal chuqur daraxtda call stack O(h) (balandlik) sarflaydi — juda chuqur/skewed daraxtda stack overflow xavfi bor, shuning uchun ba’zan explicit stack bilan iterativ traversal afzal ko‘riladi.

Kod misoli

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

// Inorder — rekursiv (BST da tartiblangan chiqish)
function inorder(root, result = []) {
  if (!root) return result
  inorder(root.left, result)
  result.push(root.val)
  inorder(root.right, result)
  return result
}

// Preorder — rekursiv
function preorder(root, result = []) {
  if (!root) return result
  result.push(root.val)
  preorder(root.left, result)
  preorder(root.right, result)
  return result
}

// Level-order (BFS) — queue bilan
function levelOrder(root) {
  if (!root) return []
  const result = []
  const queue = [root]
  while (queue.length) {
    const node = queue.shift()
    result.push(node.val)
    if (node.left) queue.push(node.left)
    if (node.right) queue.push(node.right)
  }
  return result
}

// BST da qidiruv
function searchBST(root, val) {
  if (!root || root.val === val) return root
  if (val < root.val) return searchBST(root.left, val)
  return searchBST(root.right, val)
}

const tree = new TreeNode(4,
  new TreeNode(2, new TreeNode(1), new TreeNode(3)),
  new TreeNode(6, new TreeNode(5), new TreeNode(7))
)

console.log(inorder(tree)) // [1, 2, 3, 4, 5, 6, 7]
console.log(levelOrder(tree)) // [4, 2, 6, 1, 3, 5, 7]
console.log(searchBST(tree, 5).val) // 5

Imtihonda

  • «Inorder, Preorder, Postorder farqi va qachon ishlatiladi?»
  • «BST da min/max elementni topish?» → chap eng chuqur / o‘ng eng chuqur
  • «Tree balandligini (height) hisoblang»

Yodlash uchun

Inorder = tartiblangan chiqish (BST), Level-order = BFS + queue.

Graph — adjacency list/matrix

Senior

Nima bu?

Graph — vertex (tugun) va edge (yo‘l) lar to‘plami. Adjacency list — har vertex uchun qo‘shni vertexlar ro‘yxati (xotira tejamkor, ko‘p graph uchun). Adjacency matrix — n×n jadval, matrix[i][j] = 1 bo‘lsa yo‘l bor (tez edge tekshirish, lekin xotira O(n²)).

Kod misoli

// Adjacency list — Map bilan
function buildGraph(edges, directed = false) {
  const graph = new Map()
  const addEdge = (a, b) => {
    if (!graph.has(a)) graph.set(a, [])
    if (!graph.has(b)) graph.set(b, [])
    graph.get(a).push(b)
    if (!directed) graph.get(b).push(a)
  }
  for (const [a, b] of edges) addEdge(a, b)
  return graph
}

// Adjacency matrix
function buildMatrix(n, edges, directed = false) {
  const matrix = Array.from({ length: n }, () => Array(n).fill(0))
  for (const [a, b] of edges) {
    matrix[a][b] = 1
    if (!directed) matrix[b][a] = 1
  }
  return matrix
}

// DFS — rekursiv (adjacency list)
function dfs(graph, start, visited = new Set()) {
  visited.add(start)
  console.log(start)
  for (const neighbor of graph.get(start) || []) {
    if (!visited.has(neighbor)) dfs(graph, neighbor, visited)
  }
}

// BFS — queue
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
}

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

Imtihonda

  • «Adjacency list va matrix farqi — qachon qaysi biri?»
  • «Graphda cycle bor-yo‘qligini qanday aniqlaysiz?»
  • «Ikki vertex o‘rtasida yo‘l bormi?» → BFS/DFS

Yodlash uchun

Kam edge, katta graph → adjacency list; tez edge lookup, kichik graph → matrix.