Почему именно эти 20 задач?

Мы проанализировали тысячи отзывов о собеседованиях на Glassdoor, LeetCode Discuss и Blind, чтобы выбрать задачи, которые:

• Часто встречаются на реальных интервью
• Покрывают основные паттерны алгоритмов
• Имеют оптимальный уровень сложности (Easy/Medium)
• Помогают развить алгоритмическое мышление

Каждая задача включает:

• Описание и примеры
• Оптимальное решение
• Анализ сложности
• Ключевые инсайты

Категория 1: Массивы и хеш-таблицы

1. Two Sum (Easy)

Частота на собеседованиях: Очень высокая (Google, Amazon, Meta)

Условие: Найти два числа в массиве, сумма которых равна target.

def two_sum(nums, target):
    """
    Решение за O(n) с использованием хеш-таблицы
    """
    seen = {}  # число -> индекс

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

    return []

# Пример: two_sum([2, 7, 11, 15], 9) = [0, 1]

JavaScript:

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 [];
}

Сложность: O(n) время, O(n) память

Ключевой инсайт: Вместо проверки всех пар O(n²), храним уже просмотренные числа в хеш-таблице.

2. Contains Duplicate (Easy)

Условие: Проверить, есть ли в массиве дубликаты.

def contains_duplicate(nums):
    return len(nums) != len(set(nums))

# Альтернативное решение с ранним выходом
def contains_duplicate_v2(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Сложность: O(n) время, O(n) память

3. Best Time to Buy and Sell Stock (Easy)

Частота: Очень высокая (Amazon, Goldman Sachs)

Условие: Найти максимальную прибыль от одной покупки и продажи.

def max_profit(prices):
    """
    Отслеживаем минимальную цену и максимальную прибыль
    """
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        profit = price - min_price
        max_profit = max(max_profit, profit)

    return max_profit

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Пример: max_profit([7, 1, 5, 3, 6, 4]) = 5 (купить за 1, продать за 6)

**Сложность:** O(n) время, O(1) память

---

### 4. Product of Array Except Self (Medium)

**Частота:** Высокая (Amazon, Microsoft, Meta)

**Условие:** Для каждого элемента вычислить произведение всех остальных элементов без использования деления.

```python
def product_except_self(nums):
    n = len(nums)
    result = [1] * n

    # Префиксные произведения (слева)
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # Суффиксные произведения (справа)
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

# Пример: product_except_self([1, 2, 3, 4]) = [24, 12, 8, 6]

Сложность: O(n) время, O(1) память (не считая результат)

5. Maximum Subarray (Medium)

Условие: Найти подмассив с максимальной суммой (алгоритм Кадане).

def max_subarray(nums):
    """
    Алгоритм Кадане: отслеживаем текущую и максимальную сумму
    """
    current_sum = max_sum = nums[0]

    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)

    return max_sum

# Пример: max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) = 6
# Подмассив: [4, -1, 2, 1]

Сложность: O(n) время, O(1) память

Категория 2: Строки

6. Valid Anagram (Easy)

Условие: Проверить, являются ли две строки анаграммами.

from collections import Counter

def is_anagram(s, t):
    return Counter(s) == Counter(t)

# Решение без Counter
def is_anagram_v2(s, t):
    if len(s) != len(t):
        return False

    count = {}
    for c in s:
        count[c] = count.get(c, 0) + 1

    for c in t:
        if c not in count or count[c] == 0:
            return False
        count[c] -= 1

    return True

7. Valid Palindrome (Easy)

Условие: Проверить, является ли строка палиндромом (игнорируя регистр и не-буквенные символы).

def is_palindrome(s):
    # Фильтруем и приводим к нижнему регистру
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]

# Two Pointers решение (O(1) память)
def is_palindrome_v2(s):
    left, right = 0, len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

8. Longest Substring Without Repeating Characters (Medium)

Частота: Очень высокая (Amazon, Microsoft, Bloomberg)

Условие: Найти длину самой длинной подстроки без повторяющихся символов.

def length_of_longest_substring(s):
    """
    Sliding Window с хеш-таблицей
    """
    char_index = {}  # символ -> последний индекс
    max_length = 0
    start = 0

    for end, char in enumerate(s):
        if char in char_index and char_index[char] >= start:
            start = char_index[char] + 1

        char_index[char] = end
        max_length = max(max_length, end - start + 1)

    return max_length

# Пример: "abcabcbb" -> 3 ("abc")
# Пример: "bbbbb" -> 1 ("b")

JavaScript:

function lengthOfLongestSubstring(s) {
    const charIndex = new Map();
    let maxLength = 0;
    let start = 0;

    for (let end = 0; end < s.length; end++) {
        const char = s[end];
        if (charIndex.has(char) && charIndex.get(char) >= start) {
            start = charIndex.get(char) + 1;
        }
        charIndex.set(char, end);
        maxLength = Math.max(maxLength, end - start + 1);
    }

    return maxLength;
}

Сложность: O(n) время, O(min(n, m)) память, где m — размер алфавита

Категория 3: Связные списки

9. Reverse Linked List (Easy)

Частота: Очень высокая (классика собеседований)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    """
    Итеративное решение с тремя указателями
    """
    prev = None
    current = head

    while current:
        next_node = current.next  # Сохраняем следующий
        current.next = prev       # Разворачиваем связь
        prev = current            # Двигаем prev
        current = next_node       # Двигаем current

    return prev

# Рекурсивное решение
def reverse_list_recursive(head):
    if not head or not head.next:
        return head

    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None

    return new_head

10. Merge Two Sorted Lists (Easy)

Условие: Слить два отсортированных списка в один.

def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    current = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    # Добавляем оставшийся хвост
    current.next = l1 or l2

    return dummy.next

11. Linked List Cycle (Easy)

Условие: Определить, есть ли цикл в связном списке.

def has_cycle(head):
    """
    Алгоритм Флойда (черепаха и заяц)
    """
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

Сложность: O(n) время, O(1) память

Категория 4: Стеки и очереди

12. Valid Parentheses (Easy)

Частота: Очень высокая (Amazon, Meta, Google)

def is_valid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:  # Закрывающая скобка
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        else:  # Открывающая скобка
            stack.append(char)

    return len(stack) == 0

# Примеры:
# is_valid("()[]{}") = True
# is_valid("([)]") = False
# is_valid("{[]}") = True

13. Min Stack (Medium)

Условие: Реализовать стек с операцией getMin() за O(1).

class MinStack:
    def __init__(self):
        self.stack = []  # (value, current_min)

    def push(self, val):
        current_min = min(val, self.get_min()) if self.stack else val
        self.stack.append((val, current_min))

    def pop(self):
        self.stack.pop()

    def top(self):
        return self.stack[-1][0]

    def get_min(self):
        return self.stack[-1][1]

Категория 5: Деревья

14. Maximum Depth of Binary Tree (Easy)

def max_depth(root):
    if not root:
        return 0

    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)

    return max(left_depth, right_depth) + 1

15. Invert Binary Tree (Easy)

Знаменитая задача: Макс Хауэлл (создатель Homebrew) не прошёл собеседование в Google из-за этой задачи.

def invert_tree(root):
    if not root:
        return None

    # Меняем детей местами
    root.left, root.right = root.right, root.left

    # Рекурсивно инвертируем поддеревья
    invert_tree(root.left)
    invert_tree(root.right)

    return root

16. Validate Binary Search Tree (Medium)

Частота: Высокая (Amazon, Microsoft)

def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True

    if root.val <= min_val or root.val >= max_val:
        return False

    return (is_valid_bst(root.left, min_val, root.val) and
            is_valid_bst(root.right, root.val, max_val))

Категория 6: Динамическое программирование

17. Climbing Stairs (Easy)

def climb_stairs(n):
    if n <= 2:
        return n

    prev2, prev1 = 1, 2

    for _ in range(3, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1

18. Coin Change (Medium)

Частота: Высокая (Amazon, Google)

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

19. Longest Increasing Subsequence (Medium)

def length_of_lis(nums):
    if not nums:
        return 0

    dp = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

# O(n log n) решение с бинарным поиском
import bisect

def length_of_lis_optimized(nums):
    sub = []

    for num in nums:
        pos = bisect.bisect_left(sub, num)
        if pos == len(sub):
            sub.append(num)
        else:
            sub[pos] = num

    return len(sub)

Категория 7: Графы

20. Number of Islands (Medium)

Частота: Очень высокая (Amazon, Meta, Google)

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or 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 r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)

    return count

Таблица сложности всех задач

План изучения на 4 недели

Неделя 1: Easy задачи

День 1-2: Two Sum, Contains Duplicate, Valid Anagram День 3-4: Valid Palindrome, Valid Parentheses День 5-6: Reverse Linked List, Merge Two Lists, Linked List Cycle День 7: Max Depth, Invert Tree, Climbing Stairs

Неделя 2: Medium задачи (часть 1)

День 1-2: Best Time to Buy/Sell, Maximum Subarray День 3-4: Product Except Self, Longest Substring День 5-7: Min Stack, Validate BST

Неделя 3: Medium задачи (часть 2)

День 1-3: Coin Change, LIS День 4-7: Number of Islands + повторение

Неделя 4: Закрепление и mock-интервью

День 1-3: Решение всех задач повторно с таймером День 4-7: Mock-интервью с партнёром или на Pramp

Советы для собеседования

1. Уточняйте условие — спрашивайте про edge cases, размер входных данных
2. Думайте вслух — объясняйте ход мыслей интервьюеру
3. Начните с brute force — покажите, что понимаете задачу
4. Оптимизируйте постепенно — переходите к лучшему решению
5. Тестируйте на примерах — проверьте код перед сдачей
6. Анализируйте сложность — всегда говорите O(n), O(n²) и т.д.

Заключение

Эти 20 задач покрывают основные паттерны, которые встречаются на собеседованиях. После их освоения вы сможете:

• Узнавать паттерны в новых задачах
• Быстро применять оптимальные подходы
• Уверенно чувствовать себя на интервью

Удачи в подготовке!