Профессия:
Задачи с собеседований на Python-разработчика: алгоритмы и структуры данных, разбор строк, обход графов и деревьев, подводные камни языка (изменяемый аргумент по умолчанию, поверхностное копирование, контекстные менеджеры, декораторы), REST API на Flask. У каждой задачи есть разбор с рабочим кодом.
Частота символов в строке
Подсчёт частоты символов — классическая задача обработки строк. Требуется найти количество каждого уникального символа и вернуть результат в виде словаря.
Решение 1: С использованием словаря
def char_frequency(s: str) -> dict:
"""
Подсчитывает частоту каждого символа в строке.
Args:
s: Входная строка
Returns:
Словарь {символ: количество}
Временная сложность: O(n)
Пространственная сложность: O(k), где k - количество уникальных символов
"""
frequency = {}
for char in s:
# Если символ уже в словаре, увеличиваем счётчик
# Иначе, добавляем с начальным значением 1
frequency[char] = frequency.get(char, 0) + 1
return frequency
Бинарный поиск: полный разбор
Бинарный поиск — это эффективный алгоритм поиска элемента в отсортированном массиве. Работает по принципу разделения пополам: исключаем половину возможных вариантов на каждой итерации.
Решение 1: Итеративный подход ⭐ РЕКОМЕНДУЕТСЯ
Числа Фибоначчи
Описание
Последовательность Фибоначчи — это классическая задача программирования, где каждое число равно сумме двух предыдущих. Это отличный пример для демонстрации различных подходов к решению: от наивного рекурсивного решения до оптимизированных методов.
Решение 1: Рекурсивный подход (простой, но неэффективный)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
# Примеры
print(fib(0)) # 0
print(fib(1)) # 1
print(fib(6)) # 8
print(fib(10)) # 55
Проблемы: временная сложность O(2^n), многократное вычисление одних и тех же значений.
Решение 2: Рекурсия с мемоизацией (оптимальный баланс)
def fib(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
# Или с использованием decorator
from functools import lru_cache
Разворот числа
Развернуть число — это перевернуть порядок его цифр. Например, 12345 становится 54321, а -123 становится -321 (знак остаётся на месте).
Решение 1: Использование строк
def reverse_number(n):
"""Разворот числа через преобразование в строку."""
# Обработка отрицательных чисел
sign = -1 if n < 0 else 1
n = abs(n)
# Преобразуем в строку, разворачиваем, преобразуем обратно
reversed_n = int(str(n)[::-1])
return sign * reversed_n
# Тесты
print(reverse_number(12345)) # 54321
print(reverse_number(-123)) # -321
print(reverse_number(100)) # 1 (ведущие нули отпадают)
print(reverse_number(0)) # 0
print(reverse_number(-1)) # -1
Решение 2: Математический подход (без строк)
FizzBuzz
Классическое решение
Эта знаменитая задача часто используется на собеседованиях для проверки базовых навыков программирования. Есть несколько подходов различной сложности.
1. Наивное решение
def fizzbuzz_naive(n: int) -> list:
"""
Простое решение с проверкой условий.
"""
result = []
for i in range(1, n + 1):
if i % 15 == 0: # Делится на 3 и 5
result.append("FizzBuzz")
elif i % 3 == 0:
result.append("Fizz")
elif i % 5 == 0:
result.append("Buzz")
else:
result.append(i)
return result
# Использование
print(fizzbuzz_naive(15))
# [1, 2, "Fizz", 4, "Buzz", "Fizz", 7, 8, "Fizz", "Buzz", 11, "Fizz", 13, 14, "FizzBuzz"]
Особенности:
2. Решение со строковой конкатенацией
Проверка палиндрома (число)
Палиндром — число, которое читается одинаково слева направо и справа налево (без учёта знака).
Примеры
Решение 1: Через строку (простое)
Преобразуем число в строку и проверяем, равна ли она своей инверсии:
def is_palindrome(num: int) -> bool:
"""
Проверяет, является ли число палиндромом.
Отрицательные числа — не палиндромы (минус не симметричен).
"""
# Отрицательные числа не палиндромы
if num < 0:
return False
# Преобразуем в строку
s = str(num)
# Сравниваем со своей инверсией
return s == s[::-1]
Замена пробелов в строке
Задача замены пробелов на другую подстроку — это базовая операция обработки строк, часто встречающаяся при кодировании URL, форматировании данных и обработке текста. В Python есть несколько способов решить эту задачу с разными уровнями оптимизации.
Простое решение: встроенный метод replace()
def replace_spaces(text: str, replacement: str) -> str:
"""
Заменяет все пробелы в строке на заданную подстроку.
Args:
text: Исходная строка
replacement: Подстрока для замены
Returns:
Строка с замененными пробелами
Временная сложность: O(n)
Пространственная сложность: O(n)
"""
return text.replace(" ", replacement)
Удаление символа из строки
Задача: удалить все вхождения указанного символа из строки. Это базовая операция обработки строк, которая часто встречается в разработке.
Решение 1: Метод replace()
def remove_char(string, char):
"""Удалить все вхождения символа из строки."""
return string.replace(char, "")
# Примеры
print(remove_char("hello world", "o")) # hell wrld
print(remove_char("banana", "a")) # bnn
print(remove_char("aaaaaa", "a")) # (пустая строка)
print(remove_char("test", "x")) # test (символ не найден)
Решение 2: Список (list comprehension)
def remove_char_v2(string, char):
"""Удалить символ через list comprehension."""
return "".join(c for c in string if c != char)
# Примеры
print(remove_char_v2("hello world", "o")) # hell wrld
print(remove_char_v2("banana", "a")) # bnn
print(remove_char_v2("test", "x")) # test
Решение 3: Метод filter()
Проверка простого числа: полный разбор
Простое число — это натуральное число больше 1, которое делится только на 1 и на само себя. Это фундаментальная задача в программировании, которая помогает понять оптимизацию алгоритмов.
Решение 1: Базовый подход (O(n))
def is_prime_basic(n: int) -> bool:
"""
Проверяет, является ли число простым (базовый подход).
Args:
n: Проверяемое число
Returns:
True, если число простое, иначе False
"""
# Числа меньше 2 не являются простыми
if n < 2:
return False
# 2 - единственное чётное простое число
if n == 2:
return True
# Все чётные числа (кроме 2) не простые
if n % 2 == 0:
return False
# Проверяем делители от 3 до n-1
for i in range(3, n):
if n % i == 0:
return False # Нашли делитель, число не простое
return True
Разворот порядка слов в строке
Задача: Развернуть порядок слов в строке, убедившись что между словами ровно один пробел, без пробелов в начале и конце.
Решение 1: Через split() и join() (рекомендуется)
Самое простое и читаемое решение:
def reverse_words(s):
"""
Разворачивает порядок слов в строке.
Алгоритм:
1. split() без аргументов разбивает по любым пробелам и удаляет пустые строки
2. [::-1] разворачивает список слов
3. join(' ') соединяет слова одиночным пробелом
"""
return " ".join(s.split()[::-1])
# Примеры
print(reverse_words("hello world")) # world hello
print(reverse_words(" the sky is blue ")) # blue is sky the
print(reverse_words("Python")) # Python
print(reverse_words("")) # ""
print(reverse_words(" multiple spaces ")) # spaces multiple
Разворот строки
Задача: Перевернуть строку без использования встроенных функций reverse() или срезов [::-1].
Решение 1: Цикл в обратном порядке
Проходим по строке от конца к началу:
def reverse_string(s: str) -> str:
"""
Переворачивает строку через цикл.
"""
result = ""
for i in range(len(s) - 1, -1, -1):
result += s[i]
return result
# Тестирование
test_cases = [
("hello", "olleh"),
("Python", "nohtyP"),
("a", "a"),
("", ""),
("12345", "54321"),
("abc", "cba"),
]
for input_str, expected in test_cases:
result = reverse_string(input_str)
status = "✓" if result == expected else "✗"
print(f"{status} reverse_string('{input_str}') = '{result}'")
Сложность:
Минус: В Python конкатенация строк неэффективна, так как создаёт новый объект каждый раз.
Решение 2: Со списком (более эффективно)
Проверка анаграммы
Анаграмма — это слово, образованное перестановкой букв другого слова. Например, "listen" и "silent" — анаграммы, так как содержат одинаковые буквы в разном порядке.
Основной подход: сортировка букв
Если две строки содержат одинаковые буквы с одинаковой частотой, то они анаграммы.
def is_anagram(str1, str2):
# Убираем пробелы, преобразуем в нижний регистр
str1_cleaned = str1.replace(" ", "").lower()
str2_cleaned = str2.replace(" ", "").lower()
# Если отсортированные строки совпадают, это анаграмма
return sorted(str1_cleaned) == sorted(str2_cleaned)
# Тестирование
print(is_anagram("listen", "silent")) # True
print(is_anagram("hello", "world")) # False
print(is_anagram("restful", "fluster")) # True
print(is_anagram("The Eyes", "They See")) # True
Объяснение
# Пример для "listen" и "silent"
str1 = "listen"
str2 = "silent"
Дни до потепления: Эффективное решение через стек
Понимание задачи
Нужно для каждого дня найти, сколько дней нужно ждать, пока придёт более тёплый день. Это классическая задача на Monotonic Stack (монотонный стек) — один из самых важных паттернов в алгоритмике.
Наивный подход O(n²) — неэффективно
def warm_days_naive(temps: list[int]) -> list[int]:
"""Перебираем каждый день, смотрим в будущее."""
n = len(temps)
result = [0] * n
for i in range(n):
for j in range(i + 1, n):
if temps[j] > temps[i]:
result[i] = j - i
break
return result
Проблема: Для 30000 дней (месяц) = 30000² / 2 = 450 млн операций. Слишком медленно.
Оптимальный подход: Monotonic Stack O(n)
Идея: идём с конца массива назад, держим в стеке индексы дней в порядке убывания температуры.
Обход дерева в ширину (BFS)
Описание
Breadth-First Search (BFS) — это алгоритм обхода графов и деревьев, который посещает узлы по уровням: сначала все узлы на уровне 1, затем на уровне 2, и так далее. Используется очередь (queue) для отслеживания узлов.
Решение 1: Классическое решение с использованием deque
from collections import deque
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def bfs(root):
"""Обход дерева в ширину."""
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft() # Извлекаем из начала
result.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
Проверка палиндрома: полный разбор
Палиндром — это строка, которая читается одинаково в обе стороны. При проверке игнорируются регистр и небуквенные символы.
Решение 1: Классический подход (Simple)
def is_palindrome_simple(s: str) -> bool:
"""
Проверяет, является ли строка палиндромом.
Игнорирует регистр и небуквенные символы.
Подход: очистка строки, затем сравнение с обратной версией.
"""
# Преобразуем в нижний регистр и оставляем только буквы
cleaned = ''.join(char.lower() for char in s if char.isalpha())
# Сравниваем с обратной версией
return cleaned == cleaned[::-1]
# Примеры
print(is_palindrome_simple("А роза упала на лапу Азора")) # True
print(is_palindrome_simple("Was it a car or a cat I saw?")) # True
print(is_palindrome_simple("hello")) # False
print(is_palindrome_simple("racecar")) # True
print(is_palindrome_simple("Madam")) # True
print(is_palindrome_simple("12321")) # True
Реализация Trie (префиксное дерево)
Trie — это древовидная структура данных для эффективного хранения и поиска строк, особенно когда нужно искать по префиксам. Каждый узел содержит ссылки на дочерние узлы для каждого символа алфавита.
Структура Trie
Вставляем слова: "apple", "app", "apricot"
root
/
a
|
p
/ \
p r
| |
l i
| |
e c
(★) |
o
|
t
(★)
Узлы с (★) отмечены как конец слова
Основная реализация
class TrieNode:
"""Узел префиксного дерева"""
def __init__(self):
self.children = {} # Ссылки на потомков {a: TrieNode, b: TrieNode, ...}
self.is_end_of_word = False # Флаг: конец ли слова в этом узле
Синхронизация данных с внешнего API
Проблема
При работе с большими объёмами данных (100К+) критичны производительность, надёжность и консистентность. Наивные подходы приводят к таймаутам, утечкам памяти и потере данных.
1. Отдельные запросы (N запросы) — почему плохо?
Проблемы:
# ❌ Плохо: N запросы
for item_id in all_ids:
response = requests.get(f"https://api.example.com/items/{item_id}")
db.update(item_id, response.json())
2. Загрузка всей таблицы в память — когда не работает?
Удаление дубликатов с сохранением порядка
Задача: Удалить дубликаты из списка, сохраняя порядок первого появления каждого элемента.
Решение 1: С использованием set и сохранением порядка (Python 3.7+)
В Python 3.7+ словари и set сохраняют порядок вставки:
def remove_duplicates(lst):
"""
Удаляет дубликаты, сохраняя порядок первого появления.
Алгоритм:
- Используем set как временное хранилище для проверки уникальности
- Проходим по списку и добавляем элементы, которые не видели ранее
- dict.fromkeys() сохраняет порядок ключей
"""
return list(dict.fromkeys(lst))
# Примеры
print(remove_duplicates([1, 2, 2, 3, 1, 4])) # [1, 2, 3, 4]
print(remove_duplicates(["a", "b", "a", "c", "b"])) # ["a", "b", "c"]
print(remove_duplicates([1, 1, 1, 1])) # [1]
print(remove_duplicates([])) # []
Результат -12 % 10 и -12 // 10
Это вопрос о том, как Python обрабатывает операции модуля и целочисленного деления с отрицательными числами. Результаты часто удивляют разработчиков, пришедших из других языков!
Правильный ответ
При выполнении:
print(-12 % 10) # 8
print(-12 // 10) # -2
Результаты:
-12 % 10 = 8-12 // 10 = -2Объяснение
После того, как // (целочисленное деление) вычисляет результат, Python обеспечивает инвариант:
a = (a // b) * b + (a % b)
Для -12 % 10 и -12 // 10:
# Сначала вычисляем целочисленное деление
-12 // 10 = -2 # Python округляет ВНИЗ (вниз по оси чисел), не к нулю!
# Затем вычисляем остаток из инварианта
-12 = (-2) * 10 + remainder
-12 = -20 + remainder
remainder = 8
# Проверка: -12 = (-2) * 10 + 8 = -20 + 8 = -12
Ключевое отличие: Floor Division
Python использует floor division (округление вниз), а не truncation (усечение в сторону нуля):
Перевод в двоичную систему
Задача: Преобразовать десятичное число в двоичное представление без встроенной функции bin().
Решение 1: Итеративный подход (классический)
Это наиболее прямолинейный способ — последовательно делим число на 2 и собираем остатки в обратном порядке:
def to_binary(n):
"""
Преобразует десятичное число в двоичное представление.
Алгоритм:
1. Пока число > 0:
- Берём остаток от деления на 2 (0 или 1)
- Добавляем его в начало строки результата
- Делим число на 2 (целочисленно)
2. Возвращаем результат
"""
if n == 0:
return "0"
binary = ""
while n > 0:
binary = str(n % 2) + binary # Остаток от деления на 2
n = n // 2 # Целочисленное деление на 2
return binary
REST API на Flask
Базовое решение
from flask import Flask, request, jsonify
from datetime import datetime
from typing import Dict, List, Tuple, Any, Optional
app = Flask(__name__)
# Хранилище задач (в памяти)
tasks_db: Dict[int, Dict[str, Any]] = {}
next_id = 1
@app.route('/tasks', methods=['GET'])
def get_tasks() -> Tuple[Dict[str, List], int]:
"""Получить список всех задач"""
return jsonify(list(tasks_db.values())), 200
@app.route('/tasks/<int:task_id>', methods=['GET'])
def get_task(task_id: int) -> Tuple[Dict[str, Any], int]:
"""Получить задачу по ID"""
task = tasks_db.get(task_id)
if not task:
return jsonify({"error": "Task not found"}), 404
return jsonify(task), 200
Факториал числа — рекурсивное решение
Факториал (обозначается n!) — это произведение всех положительных целых чисел от 1 до n включительно. Это классическая задача для демонстрации рекурсии.
Математическое определение
n! = n × (n-1) × (n-2) × ... × 1
Специальные случаи:
0! = 1 (по определению)
1! = 1
Рекурсивное решение
Идея рекурсии для факториала:
n = 0 или n = 1, возвращаем 1n! = n × (n-1)!def factorial(n):
# Базовый случай
if n == 0 or n == 1:
return 1
# Рекурсивный случай
return n * factorial(n - 1)
# Примеры использования
print(factorial(5)) # 120 (5 × 4 × 3 × 2 × 1)
print(factorial(0)) # 1
print(factorial(1)) # 1
print(factorial(10)) # 3628800
Как работает рекурсия на примере factorial(5)
Длиннейшая палиндромная подстрока
Задача
Найти самую длинную подстроку-палиндром в строке. Палиндром читается одинаково в обе стороны (например, "racecar", "noon").
Для примера:
longest_palindrome("babad") → "bab" или "aba"longest_palindrome("cbbd") → "bb"Решение 1: Expand Around Center (O(n²), оптимально)
Для каждого символа (или пары символов) как центра, расширяем вправо и влево, пока символы совпадают.
Копирование графа
Задача
Создать глубокую копию связного неориентированного графа. Каждый узел содержит значение (int) и список соседей.
Основная сложность: граф может содержать циклы, поэтому нужно отслеживать уже скопированные узлы, чтобы не зациклиться.
Решение 1: DFS с Hashmap (Рекурсивное)
Используем глубинный поиск с hashmap для отслеживания скопированных узлов.
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors else []
Контейнер с наибольшим количеством воды
Задача о контейнере (Container with Most Water) — это классический алгоритмическая задача, проверяющая умение применять метод двух указателей (Two Pointers) для оптимизации решения. На первый взгляд может показаться, что нужно проверить все пары, но существует умный линейный подход.
Понимание задачи
У нас есть массив высот. Площадь контейнера = ширина × минимальная высота из двух выбранных линий.
Массив: [1, 8, 6, 2, 5, 4, 8, 3, 7]
Индексы: 0 1 2 3 4 5 6 7 8
Если выбираем индексы 1 и 8 (высоты 8 и 7):
Ширина = 8 - 1 = 7
Высота = min(8, 7) = 7
Площадь = 7 × 7 = 49
Подход 1: Брутфорс O(n²)
Проверяем все возможные пары линий:
Реализация очереди через два стека
Очередь (Queue) работает по принципу FIFO (First In First Out) — первый вошёл, первый вышел. Стек же работает по принципу LIFO (Last In First Out). Задача требует создать очередь, используя только стеки — отличный пример алгоритмического мышления.
Идея решения
Мы используем два стека:
Когда нужно получить элемент из очереди, мы перемещаем все элементы из input_stack в output_stack (это развернёт их порядок). Благодаря этому output_stack будет содержать элементы в порядке FIFO.
Базовая реализация
Переворот связного списка
Переворот связного списка — одна из классических задач, проверяющих понимание работы с указателями и манипуляцией структурами данных. Решение требует изменения направления связей между узлами.
Подход 1: Итеративное решение (Iterative Reversal)
Итеративный подход — самый эффективный и наиболее часто используемый в production коде. Идея простая: мы проходим по списку и переворачиваем стрелки (связи) между узлами.
Алгоритм:
prev, current и nextclass ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
Проблема изменяемого аргумента по умолчанию
Это одна из самых коварных ошибок в Python, которую допускают даже опытные разработчики. Давайте разберёмся в механизме проблемы и способах её решения.
1. Поведение и вывод
def f(value, items=[]):
items.append(value)
return items
print(f(1)) # [1]
print(f(2)) # [1, 2]
print(f(3)) # [1, 2, 3]
Неожиданный вывод! Третий вызов выводит всю историю добавленных значений, а не только [3].
2. Почему это происходит?
В Python списки создаются один раз при определении функции, а не при каждом вызове.
def f(value, items=[]):
items.append(value)
return items
# Это происходит при определении функции:
# 1. Создаётся пустой список []
# 2. Этот список сохраняется как значение по умолчанию аргумента items
# 3. Этот ОДИН И ТОТ ЖЕ список используется во всех последующих вызовах
print(f.__defaults__) # ([1, 2, 3],) — список в памяти содержит [1, 2, 3]
Визуально:
Параметризованный декоратор замера времени
Декораторы — важная часть Python. Параметризованный декоратор (decorator factory) — это функция, которая принимает параметры и возвращает сам декоратор. Это задача проверяет понимание замыканий (closures) и функционального программирования.
Решение 1: Базовое
import time
import functools
from typing import Callable, Any
Пересечение двух списков
Задача: найти элементы, которые присутствуют в обоих списках. Это классическая задача обработки данных, часто встречается в алгоритмических интервью.
Решение 1: Использование множеств
def intersection(list1, list2):
"""Найти пересечение двух списков через множества."""
return list(set(list1) & set(list2))
# Примеры
print(intersection([1, 2, 3, 4], [3, 4, 5, 6])) # [3, 4]
print(intersection([1, 2], [3, 4])) # []
print(intersection([1, 1, 2, 2], [1, 2, 2, 3])) # [1, 2]
Решение 2: Сохранение порядка (list comprehension)
def intersection_v2(list1, list2):
"""Найти пересечение, сохраняя порядок из list1."""
set2 = set(list2)
return [x for x in list1 if x in set2]
# Примеры
print(intersection_v2([1, 2, 3, 4], [3, 4, 5, 6])) # [1, 2, 3, 4]
print(intersection_v2([4, 3, 2, 1], [3, 4, 5, 6])) # [4, 3]
print(intersection_v2([1, 2], [3, 4])) # []
Нахождение второго наибольшего элемента
Эта задача требует эффективного нахождения второго по величине элемента в списке. Важно понимать, что под "вторым наибольшим" может подразумеваться либо второй по значению (с учётом дубликатов), либо второй уникальный элемент. Рассмотрим оба подхода.
Простое решение: сортировка
def second_largest_simple(lst: list[int]) -> int | None:
"""
Простое решение через сортировку.
Временная сложность: O(n log n)
"""
if len(lst) < 2:
return None
sorted_lst = sorted(lst, reverse=True)
# Ищем второй уникальный элемент
for i in range(1, len(sorted_lst)):
if sorted_lst[i] < sorted_lst[0]:
return sorted_lst[i]
return None
# Тесты
print(second_largest_simple([1, 2, 3, 4, 5])) # 4
print(second_largest_simple([5, 5, 4, 3])) # 4
print(second_largest_simple([1, 1])) # None
Оптимальное решение: один проход O(n)
Поиск слова в матрице (Word Search)
Задача
Дана матрица букв и слово. Требуется проверить, можно ли найти слово в матрице, двигаясь по соседним ячейкам (вверх, вниз, влево, вправо). Каждую ячейку можно использовать только один раз.
Для примера:
board = [
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]
exist(board, "ABCCED") → True (A→B→C→C→E→D)exist(board, "SEE") → True (S→E→E)exist(board, "ABCB") → False (B повторяется)Решение: Backtracking (DFS)
Используем глубинный поиск с возвратом (backtracking). Для каждой ячейки пробуем найти слово, рекурсивно проверяя соседей.
Генерация всех перестановок (Permutations)
Это классическая задача на рекурсию и backtracking. Требует понимания комбинаторики и алгоритмов поиска.
1. Анализ проблемы
Перестановка — это переупорядочение элементов списка.
Количество перестановок: n! (факториал)
Для [1, 2, 3]: 3! = 6 перестановок
Для [1, 2, 3, 4]: 4! = 24 перестановки
Рекурсивная идея:
perms([1, 2, 3]) =
[1] + perms([2, 3])
[2] + perms([1, 3])
[3] + perms([1, 2])
2. Решение 1: Встроенная функция (самое простое)
from itertools import permutations
def get_permutations_builtin(nums: list[int]) -> list[list[int]]:
"""Использование встроенной функции itertools."""
return [list(perm) for perm in permutations(nums)]
# Тестирование
print(get_permutations_builtin([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Анализ:
Поиск дубликатов в массиве
Это классическая задача с ограничениями по памяти и времени. Даны числа в диапазоне [1, n] для массива размера n, что позволяет использовать сам массив как хеш-таблицу.
1. Наивное решение O(n) память
def find_duplicates_naive(nums: list[int]) -> list[int]:
"""Простое решение со множеством (O(n) дополнительная память)."""
seen = set()
duplicates = set()
for num in nums:
if num in seen:
duplicates.add(num)
else:
seen.add(num)
return sorted(list(duplicates))
# Тестирование
print(find_duplicates_naive([4, 3, 2, 7, 8, 2, 3, 1])) # [2, 3]
print(find_duplicates_naive([1, 1, 2])) # [1]
Анализ:
2. Оптимальное решение — использование индексов (O(1) память)
Ключевая идея: использовать сам массив как хеш-таблицу.
Решение: Контекстный Менеджер для Работы с Файлом
Контекстный менеджер — это объект, который определяет, что происходит в начале блока with (метод __enter__) и в конце (метод __exit__). Это гарантирует правильное управление ресурсами.
Подход 1: Класс с enter и exit
class FileManager:
def __init__(self, filename: str, mode: str = 'r'):
self.filename = filename
self.mode = mode
self.file = None
def __enter__(self):
print(f"Opening file: {self.filename}")
self.file = open(self.filename, self.mode)
return self.file # Это становится переменной после 'as'
def __exit__(self, exc_type, exc_val, exc_tb):
print(f"Closing file: {self.filename}")
if self.file:
self.file.close()
# Возвращаем False, чтобы пробросить исключение дальше
return False
# Использование
with FileManager("test.txt", "w") as f:
f.write("Hello, World!")
Решение: Глубокое и Поверхностное Копирование в Python
Этот вопрос тестирует понимание работы памяти, ссылок и мутируемых объектов в Python.
Предсказание Вывода
import copy
a = [[1, 2], [3, 4]]
b = copy.copy(a) # Shallow copy
c = copy.deepcopy(a) # Deep copy
a[0][0] = 100
print(b) # [[100, 2], [3, 4]] — ИЗМЕНИЛСЯ!
print(c) # [[1, 2], [3, 4]] — не изменился
Почему b Изменился?
Shallow copy копирует только верхний уровень структуры. Внутренние объекты остаются теми же самыми:
import copy
a = [[1, 2], [3, 4]]
b = copy.copy(a)
print(id(a)) # Разные объекты списков
print(id(b))
print(id(a[0])) # ❌ ОДИНАКОВЫЕ объекты подсписков
print(id(b[0]))
print(a is b) # False — разные списки
print(a[0] is b[0]) # True — один и тот же подсписок!
Диаграмма памяти:
До изменения:
a: [список1] → [[1, 2], [3, 4]]
b: [список2] → [[1, 2], [3, 4]] (копия контейнера, но NOT содержимого)
Миллион наименьших чисел
Проблема
Найти M наименьших элементов из N элементов (M = 10^6, N = 10^9), когда данные не помещаются в памяти целиком. Это классическая задача поиска k-smallest элементов.
1. Наивный подход с сортировкой — какая сложность?
Идея: Отсортировать всё, взять первые K элементов.
# ❌ Наивный подход
def naive_k_smallest(numbers, k):
return sorted(numbers)[:k]
Анализ сложности:
2. Подход с max-heap (приоритетная очередь)
Ключевая идея: Хранить только M элементов в памяти, используя max-heap.
Как работает:
Наибольший общий делитель (НОД)
Наибольший общий делитель (НОД) двух чисел — это наибольшее положительное целое число, на которое оба исходных числа делятся без остатка. Алгоритм Евклида — это древний и эффективный метод его вычисления, основанный на простой математической идее: НОД(a, b) = НОД(b, a mod b).
Алгоритм Евклида: основная идея
Алгоритм работает на принципе, что если a > b, то:
Пример:
НОД(48, 18):
48 = 18 * 2 + 12 → НОД(18, 12)
18 = 12 * 1 + 6 → НОД(12, 6)
12 = 6 * 2 + 0 → Остаток 0, значит НОД = 6
Итеративная реализация
Совершенное число
Совершенное число — это натуральное число, которое равно сумме всех своих собственных делителей (всех положительных делителей, кроме самого числа). Например, 6 = 1 + 2 + 3 и 28 = 1 + 2 + 4 + 7 + 14.
Решение 1: Наивный подход O(n)
def is_perfect_number_naive(n: int) -> bool:
"""
Проверяет, является ли число совершенным.
Временная сложность: O(n)
Пространственная сложность: O(1)
"""
if n <= 1:
return False
# Вычисляем сумму всех собственных делителей
divisor_sum = 0
for i in range(1, n):
if n % i == 0:
divisor_sum += i
return divisor_sum == n
# Тестирование
print(is_perfect_number_naive(6)) # True
print(is_perfect_number_naive(28)) # True
print(is_perfect_number_naive(12)) # False
print(is_perfect_number_naive(1)) # False
print(is_perfect_number_naive(496)) # True
Решение 2: Оптимизированный подход O(sqrt(n))
Расстояние редактирования (Левенштейн)
Задача
Найти минимальное количество операций для преобразования строки word1 в word2.
Допустимые операции:
Для примера edit_distance("horse", "ros") = 3:
Решение 1: Dynamic Programming (O(m*n))
DP — оптимальный подход. Используем матрицу где dp[i][j] = расстояние между первыми i символами word1 и первыми j символами word2.
Самая длинная возрастающая подпоследовательность (LIS)
Самая длинная возрастающая подпоследовательность (LIS) — классическая задача динамического программирования. Это одна из наиболее часто встречающихся задач на собеседованиях, так как проверяет способность распознавать структуру проблемы и применять оптимальное решение.
Подход 1: Динамическое программирование O(n²)
Это наиболее интуитивное решение. Идея: для каждой позиции i вычислить длину LIS, заканчивающуюся в этом элементе.
Алгоритм:
dp[i] = длина LIS, заканчивающаяся в элементе arr[i]def lengthOfLIS(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n # Каждый элемент — минимум подпоследовательность длины 1
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
Максимальная сумма подмассива: Алгоритм Кадане
Понимание задачи
Нужно найти непрерывный подмассив (consecutive elements) с максимальной суммой. Это одна из самых популярных задач на собеседованиях, и её можно решить за O(n) с помощью алгоритма Кадане.
Идея: ведём текущую сумму и максимальную сумму. Если текущая сумма становится отрицательной, начинаем заново.
Оптимальное решение: Динамическое программирование O(n)
Flatten вложенного списка
Проблема
Преобразовать список с произвольной глубиной вложенности в плоский список. Это классическая задача, требующая рекурсии или итерации со стеком.
1. Рекурсивное решение (самое простое)
def flatten_recursive(lst):
"""
Рекурсивное решение для flatten.
Временная сложность: O(N), где N — все элементы
Пространственная: O(D), где D — максимальная глубина (call stack)
"""
result = []
for item in lst:
if isinstance(item, list):
# Рекурсивно flatten вложенный список
result.extend(flatten_recursive(item))
else:
# Добавляем обычный элемент
result.append(item)
return result
# Примеры
print(flatten_recursive([1, [2, [3, 4], 5], 6]))
# [1, 2, 3, 4, 5, 6]
print(flatten_recursive([[1, 2], [3, [4, 5]]]))
# [1, 2, 3, 4, 5]
print(flatten_recursive([1, 2, 3]))
# [1, 2, 3]
print(flatten_recursive([[[[[1]]], 2]]))
# [1, 2]
Сериализация и десериализация (pickle)
Что такое Pickling?
Pickling — это процесс преобразования Python объекта в байтовый поток (serialization). Unpickling — обратный процесс восстановления объекта из байтов (deserialization).
Essentially, pickle позволяет сохранить состояние Python объекта и восстановить его позже, даже если программа закончилась.
1. Базовое использование pickle
import pickle
from typing import Any
# СЕРИАЛИЗАЦИЯ (pickle)
data = {"name": "Alice", "age": 30, "tags": ["python", "django"]}
# Способ 1: Сохранить в файл
with open("data.pkl", "wb") as f: # 'wb' = write binary
pickle.dump(data, f)
# Способ 2: Получить байты напрямую
bytes_data = pickle.dumps(data) # 's' = returns bytes
print(type(bytes_data)) # <class 'bytes'>
print(bytes_data[:50]) # b'\x80\x04}\x94(X\x04\x00\x00\x00name...'
Решение: Подсчёт Островов на Карте
Эта классическая задача на поиск связных компонентов в графе. Нужно подсчитать количество групп соединённых единиц в двумерном массиве, используя поиск в глубину (DFS) или ширину (BFS).
Подход 1: DFS (Глубина)
Используем рекурсивный поиск в глубину для исследования каждого острова:
Слияние интервалов
Эта классическая задача на обработку массивов часто встречается на собеседованиях. Идея решения простая: если интервалы отсортированы, то пересекающиеся интервалы будут соседними. Это позволяет решить задачу за один проход линейной сложности.
Алгоритм
Реализация
Анонимное письмо из журнала
Описание
Эта задача проверяет, можно ли составить письмо, используя символы из журнала. Каждый символ из журнала можно использовать только один раз. Это требует подсчёта частоты символов в обоих строках и сравнения их.
Решение 1: С использованием Counter из collections
from collections import Counter
def can_compose(letter, magazine):
letter_count = Counter(letter)
magazine_count = Counter(magazine)
for char, count in letter_count.items():
if magazine_count[char] < count:
return False
return True
print(can_compose("hello", "ehllo world")) # True
print(can_compose("hello", "world")) # False
Решение 2: Компактный способ с Counter
from collections import Counter
def can_compose(letter, magazine):
return not (Counter(letter) - Counter(magazine))
print(can_compose("hello", "ehllo world")) # True
print(can_compose("hello", "world")) # False
Быстрая сортировка (Quick Sort)
Быстрая сортировка (Quick Sort) — это один из самых эффективных алгоритмов сортировки, основанный на принципе "разделяй и властвуй". Он выбирает опорный элемент и разделяет массив на две части: элементы меньше опорного и больше опорного.
Простое решение
Обход дерева в глубину (DFS)
DFS (Depth-First Search) — это алгоритм обхода графа или дерева, который углубляется максимально по одной ветке перед тем, как перейти на другую. Существует три основных варианта DFS для бинарного дерева:
Определение класса узла
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
Preorder DFS (Рекурсивный)
Максимальная прибыль от акций
Это классическая задача на алгоритмический анализ потоков данных. Нужно найти пару (день покупки, день продажи) такую, что цена падает и прибыль максимальна. Ключевое ограничение: продажа только после покупки.
Подход: Один проход с отслеживанием минимума
В один проход через массив отслеживаем:
def max_profit(prices):
if not prices or len(prices) < 2:
return 0
min_price = prices[0]
max_profit = 0
for price in prices[1:]:
potential_profit = price - min_price
max_profit = max(max_profit, potential_profit)
min_price = min(min_price, price)
return max_profit
print(max_profit([7, 1, 5, 3, 6, 4])) # 5
print(max_profit([7, 6, 4, 3, 1])) # 0
Пошаговое выполнение
Массив: [7, 1, 5, 3, 6, 4]
Шаг 1: price=7 (начало)
min_price = 7, max_profit = 0