30 наиболее вероятных задач для собеседования по алгоритмам на Python

Список задач

Валидный пароль [Easy] - Строки, проверки
Проверить, является ли пароль валидным. Пароль должен содержать минимум 8 символов, хотя бы одну цифру, одну заглавную и одну строчную букву.
Угол между стрелками часов [Medium] - Математика, геометрия
По заданному времени (часы и минуты) вычислить наименьший угол между часовой и минутной стрелками.
Пересечение двух массивов [Easy] - Массивы, множества
Даны два массива целых чисел. Вернуть массив их пересечения (общие элементы).
Сумма двух чисел [Easy] - Массивы, хеш-таблицы
Найти в массиве два числа, сумма которых равна заданному числу. Вернуть их индексы.
Палиндром [Easy] - Строки, два указателя
Проверить, является ли строка палиндромом (читается одинаково слева направо и справа налево).
Реализация стека [Easy] - Структуры данных
Реализовать структуру данных стек с операциями push, pop, peek, empty.
Сортировка пузырьком [Easy] - Сортировка
Реализовать алгоритм сортировки пузырьком.
Бинарный поиск [Easy] - Поиск
Реализовать бинарный поиск в отсортированном массиве.
Обратная строка [Easy] - Строки
Перевернуть строку (развернуть символы в обратном порядке).
Поиск максимального элемента [Easy] - Массивы
Найти максимальный элемент в массиве.
Удалить дубликаты из отсортированного массива [Easy] - Массивы, два указателя
Удалить дубликаты из отсортированного массива на месте, вернуть новую длину.
Проверка скобок [Easy] - Стек, строки
Проверить, правильно ли расставлены скобки в строке (скобки: (), [], {}).
Слияние двух отсортированных массивов [Easy] - Массивы, слияние
Слить два отсортированных массива в один отсортированный.
Подсчет гласных [Easy] - Строки
Посчитать количество гласных букв в строке.
Сумма элементов массива [Easy] - Массивы
Вычислить сумму всех элементов массива.
Поиск отсутствующего числа [Easy] - Математика, массивы
Дан массив чисел от 0 до n с одним пропущенным числом. Найти пропущенное число.
Проверка на анаграмму [Easy] - Строки, хеш-таблицы
Проверить, являются ли две строки анаграммами (состоят из одних и тех же символов в разном порядке).
Реверс связанного списка [Easy] - Связанные списки
Развернуть односвязный список.
Поиск в глубину (DFS) [Medium] - Графы
Реализовать обход графа в глубину.
Поиск в ширину (BFS) [Medium] - Графы
Реализовать обход графа в ширину.
Проверка на простое число [Easy] - Математика
Проверить, является ли число простым.
Числа Фибоначчи [Easy] - Рекурсия, динамическое программирование
Вычислить n-ое число Фибоначчи.
Наибольший общий делитель (НОД) [Easy] - Математика
Найти наибольший общий делитель двух чисел.
Минимальный элемент в повернутом отсортированном массиве [Medium] - Бинарный поиск
Найти минимальный элемент в повернутом отсортированном массиве.
Сортировка выбором [Easy] - Сортировка
Реализовать алгоритм сортировки выбором.
Сортировка вставками [Easy] - Сортировка
Реализовать алгоритм сортировки вставками.
Декоратор с кэшированием [Medium] - Python, декораторы
Создать декоратор для кэширования результатов функции.
Генератор простых чисел [Medium] - Python, генераторы
Создать генератор, который будет выдавать простые числа.
Сумма цифр числа [Easy] - Математика
Вычислить сумму цифр заданного числа.
Проверка на степень двойки [Easy] - Битовые операции
Проверить, является ли число степенью двойки.

Решения задач (с объяснениями)

1. Валидный пароль

Решение:

def is_valid_password(password): 
    if len(password) < 8: 
        return False 
    if not any(char.isdigit() for char in password):
        return False 
    if not any(char.isupper() for char in password): 
        return False 
    if not any(char.islower() for char in password): 
        return False 

    return True

Объяснение: Проверяем длину, наличие цифр, заглавных и строчных букв. Сложность: O(n), память: O(1).

2. Угол между стрелками часов

Решение:

def angle_between_hands(hour, minute): 
    hour_angle = (hour % 12) * 30 + minute * 0.5 
    minute_angle = minute * 6 
    angle = abs(hour_angle - minute_angle) 
    
    return min(angle, 360 - angle)

Объяснение: Часовая стрелка - 0.5° в минуту, минутная - 6° в минуту. Находим разность углов и минимальный угол. Сложность: O(1).

3. Пересечение двух массивов

Решение:

def array_intersection(arr1, arr2): 
    set1 = set(arr1) 
    result = [x for x in arr2 if x in set1] 
    return result

Объяснение: Используем множество для быстрого поиска. Сложность: O(n+m), память: O(min(n,m)).

4. Сумма двух чисел

Решение:

def two_sum(nums, target): 
    num_map = {} 

    for i, num in enumerate(nums): 
        complement = target - num 

        if complement in num_map: 
            return [num_map[complement], i] 
        num_map[num] = i 

    return []

Объяснение: Храним числа и их индексы в словаре, ищем complement. Сложность: O(n), память: O(n).

5. Палиндром

Решение:

def is_palindrome(s): 
    cleaned = ''.join(char.lower() for char in s if char.isalnum()) 
    return cleaned == cleaned[::-1]

Объяснение: Очищаем строку, сравниваем с обратной. Сложность: O(n), память: O(n).

6. Реализация стека

Решение:

class Stack: 
    def __init__(self): 
        self.items = [] 
    
    def push(self, item): 
        self.items.append(item) 
    
    def pop(self): 
        return self.items.pop() if self.items else None 

    def peek(self): 
        return self.items[-1] if self.items else None 

    def is_empty(self): 
        return len(self.items) == 0 

    def size(self): 
        return len(self.items)

Объяснение: Используем список Python. Все операции O(1).

7. Сортировка пузырьком

Решение:

def bubble_sort(arr): 
    n = len(arr) 
    for i in range(n - 1): 
        swapped = False
 
        for j in range(n - 1 - i): 
            if arr[j] > arr[j + 1]: 
                arr[j], arr[j + 1] = arr[j + 1], arr[j] 
                swapped = True 

        if not swapped: 
            break 
    return arr

Объяснение: "Всплываем" максимальные элементы. Сложность: O(n²) худший, O(n) лучший.

8. Бинарный поиск

Решение:

def binary_search(arr, target): 
    left, right = 0, len(arr) - 1 
    
    while left <= right: 
        mid = left + (right - left) // 2 

        if arr[mid] == target: 
            return mid 
        elif arr[mid] < target: 
            left = mid + 1 
        else: 
            right = mid - 1 
    
    return -1

Объяснение: Делим область поиска пополам. Сложность: O(log n).

9. Обратная строка

Решение:

def reverse_string(s): 
    return s[::-1] # Самый Pythonic способ

Объяснение: Используем срез с шагом -1. Сложность: O(n), память: O(n).

10. Поиск максимального элемента

Решение:

def find_max(arr): 
    if not arr: 
        return None 

    max_val = arr[0] 
    
    for num in arr[1:]: 
        if num > max_val: 
            max_val = num 

    return max_val

Объяснение: Линейный поиск с одним проходом. Сложность: O(n).

11. Удалить дубликаты из отсортированного массива

Решение:

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

    i = 0 
    
    for j in range(1, len(nums)): 
        if nums[j] != nums[i]: 
            i += 1 
            nums[i] = nums[j] 
    
    return i + 1

Объяснение: Два указателя: i - позиция уникального элемента, j - текущий элемент. Сложность: O(n).

12. Проверка скобок

Решение:

def is_valid_parentheses(s): 
    stack = [] 
    mapping = {')': '(', ']': '[', '}': '{'} 
    
    for char in s: 
        if char in mapping.values(): 
            stack.append(char) 
        elif char in mapping: 
            if not stack or stack.pop() != mapping[char]: 
                return False 
    
    return not stack

Объяснение: Используем стек для отслеживания открывающих скобок. Сложность: O(n).

13. Слияние двух отсортированных массивов

Решение:

def merge_sorted_arrays(arr1, arr2): 
    result = [] 
    i = j = 0 
    
    while i < len(arr1) and j < len(arr2): 
        if arr1[i] <= arr2[j]: 
            result.append(arr1[i]) 
            i += 1 
        else: 
            result.append(arr2[j]) 
            j += 1 
    
    result.extend(arr1[i:]) 
    result.extend(arr2[j:]) 
    
    return result

Объяснение: Два указателя, сравниваем элементы. Сложность: O(n+m).

14. Подсчет гласных

Решение:

def count_vowels(s): 
    vowels = set('aeiouAEIOU') 
    count = 0 

    for char in s: 
        if char in vowels: 
            count += 1 

    return count

Объяснение: Используем множество для быстрой проверки. Сложность: O(n).

15. Сумма элементов массива

Решение:

def array_sum(arr): 
    total = 0 

    for num in arr: 
        total += num 
    
    return total

Объяснение: Простая итерация. Сложность: O(n).

16. Поиск отсутствующего числа

Решение:

def missing_number(nums): 
    n = len(nums) 

    expected_sum = n * (n + 1) // 2 
    actual_sum = sum(nums) 

    return expected_sum - actual_sum

Объяснение: Используем формулу суммы арифметической прогрессии. Сложность: O(n).

17. Проверка на анаграмму

Решение:

def is_anagram(s1, s2): 
    if len(s1) != len(s2): 
        return False 
    
    from collections import Counter 

    return Counter(s1) == Counter(s2)

Объяснение: Сравниваем частоты символов. Сложность: O(n).

18. Реверс связанного списка

Решение:

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 
            current = next_node 
        
        return prev

Объяснение: Итеративно меняем указатели. Сложность: O(n).

19. Поиск в глубину (DFS)

Решение:

def dfs(graph, start): 
    visited = set() 
    stack = [start] 
    
     while stack: 
        vertex = stack.pop() 
        
        if vertex not in visited: 
            visited.add(vertex) 
            stack.extend(graph[vertex] - visited) 
    
    return visited

Объяснение: Используем стек (LIFO). Сложность: O(V+E).

20. Поиск в ширину (BFS)

Решение:

from collections import deque 

def bfs(graph, start): 
    visited = set() 
    queue = deque([start]) 
    
    while queue: 
        vertex = queue.popleft() 
    
        if vertex not in visited: 
            visited.add(vertex) 
            queue.extend(graph[vertex] - visited) 

    return visited

Объяснение: Используем очередь (FIFO). Сложность: O(V+E).

21. Проверка на простое число

Решение:

def is_prime(n): 
    if n < 2: 
        return False 
    if n == 2: 
        return True 
    
    if n % 2 == 0: 
        return False 

    for i in range(3, int(n**0.5) + 1, 2): 
        if n % i == 0: 
            return False 

    return True

Объяснение: Проверяем делители до √n. Сложность: O(√n).

22. Числа Фибоначчи

Решение:

def fibonacci(n): 
    if n <= 1: 
        return n 
    
    a, b = 0, 1 
    
    for _ in range(2, n + 1): 
        a, b = b, a + b 

    return b

Объяснение: Итеративный подход с двумя переменными. Сложность: O(n).

23. Наибольший общий делитель (НОД)

Решение:

def gcd(a, b): 
    while b: 
        a, b = b, a % b 

    return a

Объяснение: Алгоритм Евклида. Сложность: O(log(min(a,b))).

24. Минимальный элемент в повернутом отсортированном массиве

Решение:

def find_min_in_rotated(nums): 
    left, right = 0, len(nums) - 1 
    
    while left < right: 
        mid = left + (right - left) // 2 
        if nums[mid] > nums[right]: 
            left = mid + 1 
        else: 
            right = mid 

    return nums[left]

Объяснение: Модифицированный бинарный поиск. Сложность: O(log n).

25. Сортировка выбором

Решение:

def selection_sort(arr): 
    n = len(arr) 
    for i in range(n): 
        min_idx = i 
        for j in range(i + 1, n): 
            if arr[j] < arr[min_idx]: 
                min_idx = j 
                arr[i], arr[min_idx] = arr[min_idx], arr[i] 
    return arr

Объяснение: На каждом шаге находим минимальный элемент. Сложность: O(n²).

26. Сортировка вставками

Решение:

def insertion_sort(arr): 
    for i in range(1, len(arr)): 
        key = arr[i] 

    j = i - 1 

    while j >= 0 and arr[j] > key: 
        arr[j + 1] = arr[j] 
        j -= 1 
        arr[j + 1] = key 

    return arr

Объяснение: Вставляем элемент в отсортированную часть. Сложность: O(n²).

27. Декоратор с кэшированием

Решение:

from functools import wraps 

def memoize(func): 
    cache = {} 

    @wraps(func) 
    def wrapper(*args): 
        if args not in cache: 
            cache[args] = func(*args) 
        return cache[args] 
    
    return wrapper

Объяснение: Храним результаты вызовов в словаре. Сложность: O(1) для повторных вызовов.

28. Генератор простых чисел

Решение:

def prime_generator(): 
    yield 2 
    primes = [2] 
    candidate = 3 

    while True: 
        is_prime = True 

        for prime in primes: 
            if prime * prime > candidate: 
                break 
            if candidate % prime == 0: 
                is_prime = False 
                break 
        
        if is_prime: 
            primes.append(candidate) 
            yield candidate 
        
        candidate += 2

Объяснение: Генерируем простые числа с проверкой делимости. Бесконечный генератор.

29. Сумма цифр числа

Решение:

def sum_of_digits(n): 
    total = 0 

    while n > 0: 
        total += n % 10 
        n //= 10 

    return total

Объяснение: Извлекаем цифры через деление на 10. Сложность: O(log₁₀ n).

30. Проверка на степень двойки

Решение:

def is_power_of_two(n): 
    if n <= 0: 
        return False 

    return (n & (n - 1)) == 0

Объяснение: Используем битовую операцию (степени двойки имеют только одну единицу в двоичном представлении). Сложность: O(1).

Используемые источники:

Все задачи соответствуют уровням Easy и Medium, которые встречаются на собеседованиях по данным официальных источников. Решения включают оптимальные подходы с учетом сложности и памяти.

ИИ-помощник

Задайте уточняющий вопрос по теме урока, чтобы получить подсказку.

Привет! Я помогу разобраться с материалом урока. Просто напишите вопрос.