Amaliy masalalar
Daraja:
Intervyuda eng ko‘p uchraydigan pattern’lar: hash map bilan juftlik topish, sliding window va two pointers. Bu pattern’larni tanish bo‘lish tez yechish imkonini beradi.
Two Sum, Three Sum — hash map yondashuv
Middle
Nima bu?
Two Sum — massivda ikki element yig‘indisi target ga teng bo‘lgan indexlarni topish. Hash map bilan O(n) vaqt. Three Sum — uchta element yig‘indisi nolga teng bo‘lgan unique triple’lar; avval sort, keyin har element uchun Two Sum (two pointers).
Kod misoli
// Two Sum — Map bilan O(n)
function twoSum(nums, target) {
const seen = new Map()
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i]
if (seen.has(complement)) {
return [seen.get(complement), i]
}
seen.set(nums[i], i)
}
return null
}
// Two Sum II — tartiblangan massiv, two pointers
function twoSumSorted(nums, target) {
let left = 0
let right = nums.length - 1
while (left < right) {
const sum = nums[left] + nums[right]
if (sum === target) return [left + 1, right + 1]
if (sum < target) left++
else right--
}
return null
}
// Three Sum — sort + two pointers
function threeSum(nums) {
nums.sort((a, b) => a - b)
const result = []
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue
let left = i + 1
let right = nums.length - 1
while (left < right) {
const sum = nums[i] + nums[left] + nums[right]
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]])
while (left < right && nums[left] === nums[left + 1]) left++
while (left < right && nums[right] === nums[right - 1]) right--
left++
right--
} else if (sum < 0) {
left++
} else {
right--
}
}
}
return result
}
// Four Sum — kengaytma (Two Sum pairs)
function fourSum(nums, target) {
nums.sort((a, b) => a - b)
const result = []
const n = nums.length
for (let i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue
for (let j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) continue
let left = j + 1
let right = n - 1
while (left < right) {
const sum = nums[i] + nums[j] + nums[left] + nums[right]
if (sum === target) {
result.push([nums[i], nums[j], nums[left], nums[right]])
while (left < right && nums[left] === nums[left + 1]) left++
while (left < right && nums[right] === nums[right - 1]) right--
left++
right--
} else if (sum < target) {
left++
} else {
right--
}
}
}
}
return result
}
console.log(twoSum([2, 7, 11, 15], 9)) // [0, 1]
console.log(twoSumSorted([2, 7, 11, 15], 9)) // [1, 2]
console.log(threeSum([-1, 0, 1, 2, -1, -4])) // [[-1, -1, 2], [-1, 0, 1]]
console.log(fourSum([1, 0, -1, 0, -2, 2], 0)) // [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
Imtihonda
- «Two Sum ni O(n²) dan O(n) ga qanday yaxshilaysiz?»
- «Three Sum da duplicate triple’lardan qanday qochasiz?»
- «Two Sum sorted va unsorted farqi?»
Yodlash uchun
Juftlik/complement qidirish → Map; tartiblangan + juftlik → two pointers.
Sliding Window pattern
MiddleSenior
Nima bu?
Sliding Window — ketma-ket elementlar oralig‘ini (window) siljitib, har qadamda natijani yangilash. Fixed window — oyna hajmi doim bir xil. Variable window — shart bajarilguncha kengaytirish/yig‘ish. Subarray/substring masalalarida O(n) yechim beradi.
Kod misoli
// Fixed window — k ta element yig'indisi maksimali
function maxSumSubarray(arr, k) {
let windowSum = 0
let maxSum = 0
for (let i = 0; i < arr.length; i++) {
windowSum += arr[i]
if (i >= k - 1) {
maxSum = Math.max(maxSum, windowSum)
windowSum -= arr[i - k + 1]
}
}
return maxSum
}
// Variable window — eng qisqa subarray yig'indisi >= target
function minSubArrayLen(target, nums) {
let left = 0
let sum = 0
let minLen = Infinity
for (let right = 0; right < nums.length; right++) {
sum += nums[right]
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1)
sum -= nums[left]
left++
}
}
return minLen === Infinity ? 0 : minLen
}
// Longest substring without repeating characters
function lengthOfLongestSubstring(s) {
const seen = new Map()
let left = 0
let maxLen = 0
for (let right = 0; right < s.length; right++) {
const ch = s[right]
if (seen.has(ch) && seen.get(ch) >= left) {
left = seen.get(ch) + 1
}
seen.set(ch, right)
maxLen = Math.max(maxLen, right - left + 1)
}
return maxLen
}
// Permutation in string — s1 ning anagrami s2 ichidami?
function checkInclusion(s1, s2) {
if (s1.length > s2.length) return false
const count1 = Array(26).fill(0)
const count2 = Array(26).fill(0)
for (let i = 0; i < s1.length; i++) {
count1[s1.charCodeAt(i) - 97]++
count2[s2.charCodeAt(i) - 97]++
}
if (count1.every((c, i) => c === count2[i])) return true
for (let i = s1.length; i < s2.length; i++) {
count2[s2.charCodeAt(i) - 97]++
count2[s2.charCodeAt(i - s1.length) - 97]--
if (count1.every((c, j) => c === count2[j])) return true
}
return false
}
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)) // 9 (5+1+3)
console.log(minSubArrayLen(7, [2, 3, 1, 2, 4, 3])) // 2 ([4, 3])
console.log(lengthOfLongestSubstring('abcabcbb')) // 3 ('abc')
console.log(checkInclusion('ab', 'eidbaooo')) // true
Imtihonda
- «Subarray/substring masalalarida sliding window qachon ishlatiladi?»
- «Longest substring without repeating characters yechimi?»
- «Fixed vs variable window farqi?»
Yodlash uchun
Ketma-ket oralik + optimal subarray/substring → sliding window; ichma-ich loop o‘rniga O(n).
Window kengayganda `right++`, shart buzilganda `left++` — bu ikki pointer ham sliding window ning bir qismi.
Two Pointers pattern
MiddleSenior
Nima bu?
Two Pointers — ikkita index (left, right yoki slow, fast) bilan massiv/string ustida bir vaqtda harakatlanish. Opposite ends — tartiblangan massivda juftlik qidirish. Same direction — slow/fast bilan duplicate olib tashlash yoki subarray. Ko‘pincha O(n) vaqt, O(1) xotira.
Kod misoli
// Opposite ends — palindrome tekshirish
function isPalindrome(s) {
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '')
let left = 0
let right = cleaned.length - 1
while (left < right) {
if (cleaned[left] !== cleaned[right]) return false
left++
right--
}
return true
}
// Opposite ends — container with most water
function maxArea(height) {
let left = 0
let right = height.length - 1
let maxWater = 0
while (left < right) {
const width = right - left
const h = Math.min(height[left], height[right])
maxWater = Math.max(maxWater, width * h)
if (height[left] < height[right]) left++
else right--
}
return maxWater
}
// Same direction — duplicate'larni olib tashlash (sorted array)
function removeDuplicates(nums) {
if (nums.length === 0) return 0
let write = 1
for (let read = 1; read < nums.length; read++) {
if (nums[read] !== nums[read - 1]) {
nums[write] = nums[read]
write++
}
}
return write
}
// Slow/fast — linked list cycle detection
function hasCycle(head) {
let slow = head
let fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) return true
}
return false
}
// Merge two sorted arrays — in-place (nums1 ga)
function merge(nums1, m, nums2, n) {
let i = m - 1
let j = n - 1
let k = m + n - 1
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k] = nums1[i]
i--
} else {
nums1[k] = nums2[j]
j--
}
k--
}
}
console.log(isPalindrome('A man, a plan, a canal: Panama')) // true
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])) // 49
console.log(removeDuplicates([1, 1, 2, 2, 3])) // 3 (massiv: [1, 2, 3, ...])
Imtihonda
- «Two pointers qachon ishlatiladi? Sliding window dan farqi?»
- «Container with most water yechimini tushuntiring»
- «Sorted array’da duplicate olib tashlash — in-place?»
Yodlash uchun
Tartiblangan + juftlik/palindrome → opposite ends; in-place filtrlash → slow/fast same direction.
Two pointers va sliding window yaqin pattern’lar. Sliding window subarray oralig‘ini siljitadi; two pointers ko‘proq juft index strategiyasi.