← Назад к курсу
Подготовка к IT-собеседованию: Python, алгоритмы, system design
📌 Алгоритмы и структуры данных
1. Алгоритмы сортировки
QuickSort (важный для собеседований):
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Или in-place версия (чаще спрашивают):
def quicksort_inplace(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pi = partition(arr, low, high)
quicksort_inplace(arr, low, pi - 1)
quicksort_inplace(arr, pi + 1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
MergeSort:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
merge_sort(left)
merge_sort(right)
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
Важные характеристики:
- QuickSort: в среднем O(n log n), худший случай O(n²), не стабильный
- MergeSort: всегда O(n log n), требует O(n) дополнительной памяти, стабильный
- TimSort (в Python): гибридный, O(n log n), стабильный
🐍 Python: Декораторы
1. Базовые декораторы
# Простейший декоратор
def my_decorator(func):
def wrapper():
print("До вызова функции")
func()
print("После вызова функции")
return wrapper
@my_decorator
def say_hello():
print("Привет!")
# Декоратор с аргументами функции
def decorator_with_args(func):
def wrapper(*args, **kwargs):
print(f"Вызвана функция {func.__name__}")
result = func(*args, **kwargs)
print(f"Функция завершилась")
return result
return wrapper
# Декоратор с собственными аргументами
def repeat(num_times):
def decorator_repeat(func):
def wrapper(*args, **kwargs):
for _ in range(num_times):
result = func(*args, **kwargs)
return result
return wrapper
return decorator_repeat
@repeat(num_times=3)
def greet(name):
print(f"Привет, {name}!")
2. Полезные декораторы
import time
from functools import wraps
# Декоратор для измерения времени
def timer(func):
@wraps(func) # сохраняем метаданные функции
def wrapper(*args, **kwargs):
start_time = time.time()
result = func(*args, **kwargs)
end_time = time.time()
print(f"{func.__name__} выполнилась за {end_time - start_time:.4f} секунд")
return result
return wrapper
# Декоратор для кэширования (мемоизация)
def cache(func):
cached_results = {}
@wraps(func)
def wrapper(*args):
if args in cached_results:
return cached_results[args]
result = func(*args)
cached_results[args] = result
return result
return wrapper
# Декоратор для логирования
def log_execution(func):
@wraps(func)
def wrapper(*args, **kwargs):
print(f"[LOG] Выполняется {func.__name__} с args={args}, kwargs={kwargs}")
try:
result = func(*args, **kwargs)
print(f"[LOG] {func.__name__} завершилась успешно")
return result
except Exception as e:
print(f"[LOG] {func.__name__} вызвала исключение: {e}")
raise
return wrapper
3. Классовые декораторы
class CountCalls:
def __init__(self, func):
self.func = func
self.num_calls = 0
def __call__(self, *args, **kwargs):
self.num_calls += 1
print(f"Вызов #{self.num_calls} функции {self.func.__name__}")
return self.func(*args, **kwargs)
@CountCalls
def say_hello():
print("Hello!")
🏗️ System Design: Система учета покупок
1. Требования
- Учет покупок пользователей
- Хранение истории транзакций
- Аналитика и отчеты
- 10M пользователей, 100 транзакций/сек пиковой нагрузки
2. Высокоуровневая архитектура
┌─────────────────────────────────────────────────────────────┐
│ Клиентские приложения │
│ (Web, Mobile Apps, API Clients) │
└─────────────────┬───────────────────────────────────────────┘
│ HTTPS/WebSocket
┌─────────────────▼───────────────────────────────────────────┐
│ API Gateway │
│ • Authentication & Authorization │
│ • Rate Limiting │
│ • Request Routing │
└──────────────┬────────────────┬─────────────────────────────┘
│ │
┌──────────▼──────┐ ┌─────▼──────────┐
│ Микросервис │ │ Микросервис │
│ Пользователи │ │ Транзакции │
│ • CRUD операц.│ │ • Создание │
│ • Профили │ │ • Валидация │
│ │ │ • История │
└──────────┬──────┘ └─────┬──────────┘
│ │
┌──────────▼──────┐ ┌─────▼──────────┐
│ PostgreSQL │ │ Cassandra/ │
│ (пользователи)│ │ MongoDB │
│ • ACID транз. │ │ (транзакции) │
│ • Индексы │ │ • Высокая │
│ │ │ запись │
└─────────────────┘ └────────────────┘
│ │
┌──────────▼────────────────▼──────────┐
│ Кэш (Redis) │
│ • Сессии │
│ • Частые запросы │
└─────────────────┬────────────────────┘
│
┌─────────────────▼────────────────────┐
│ Аналитика (ClickHouse) │
│ • Агрегация данных │
│ • Отчеты │
└─────────────────┬────────────────────┘
│
┌─────────────────▼────────────────────┐
│ Очереди (Kafka/RabbitMQ) │
│ • Асинхронная обработка │
│ • Нотификации │
└──────────────────────────────────────┘
3. Схема базы данных
PostgreSQL (пользователи и продукты):
-- Пользователи
CREATE TABLE users (
id SERIAL PRIMARY KEY,
uuid UUID UNIQUE NOT NULL,
email VARCHAR(255) UNIQUE NOT NULL,
name VARCHAR(100),
created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
updated_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);
-- Продукты/Услуги
CREATE TABLE products (
id SERIAL PRIMARY KEY,
sku VARCHAR(50) UNIQUE NOT NULL,
name VARCHAR(255) NOT NULL,
price DECIMAL(10, 2) NOT NULL,
category VARCHAR(100),
in_stock BOOLEAN DEFAULT true,
metadata JSONB
);
-- Транзакции (оптимизированная таблица)
CREATE TABLE transactions (
id BIGSERIAL PRIMARY KEY,
transaction_id UUID UNIQUE NOT NULL,
user_id UUID NOT NULL,
product_id INTEGER NOT NULL,
amount DECIMAL(10, 2) NOT NULL,
quantity INTEGER DEFAULT 1,
status VARCHAR(20) CHECK (status IN ('pending', 'completed', 'failed', 'refunded')),
payment_method VARCHAR(50),
created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
INDEX idx_user_created (user_id, created_at),
INDEX idx_status_created (status, created_at)
);
-- Материализованное представление для отчетов
CREATE MATERIALIZED VIEW daily_sales AS
SELECT
DATE(created_at) as sale_date,
COUNT(*) as transactions_count,
SUM(amount) as total_amount,
COUNT(DISTINCT user_id) as unique_customers
FROM transactions
WHERE status = 'completed'
GROUP BY DATE(created_at);
4. Оценка нагрузки и масштабирование
Расчеты:
- 10M пользователей
- 100 транзакций/сек пик = 8.64M транзакций/день
- Размер транзакции: ~1KB
- Ежедневный объем данных: ~8.64 GB
- Годовой объем: ~3.15 TB
Стратегии масштабирования:
-
Горизонтальное шардирование транзакций по user_id
-
Кэширование горячих данных в Redis (TTL 5-15 минут)
-
Репликация для чтения (1 мастер, N реплик)
-
Асинхронная обработка через очереди:
- Отправка email-уведомлений
- Обновление аналитики
- Индексация для поиска
-
CDN для статики (изображения продуктов)
5. API эндпоинты
# Пример FastAPI эндпоинтов
from fastapi import FastAPI, HTTPException
from pydantic import BaseModel
from typing import List
app = FastAPI()
class TransactionCreate(BaseModel):
user_id: str
product_id: int
quantity: int = 1
payment_method: str
@app.post("/api/v1/transactions")
async def create_transaction(transaction: TransactionCreate):
"""
Создание новой транзакции
"""
# Валидация, проверка баланса, создание в БД
# Асинхронная обработка нотификаций
pass
@app.get("/api/v1/users/{user_id}/transactions")
async def get_user_transactions(
user_id: str,
page: int = 1,
limit: int = 50
):
"""
Получение истории транзакций пользователя
с пагинацией
"""
pass
@app.get("/api/v1/analytics/daily")
async def get_daily_analytics(date: str):
"""
Аналитика за день
"""
# Используем материализованное представление
pass
📚 Дополнительные темы для подготовки
Python:
- Генераторы и итераторы
- Контекстные менеджеры
- Многопоточность vs многопроцессность
- GIL (Global Interpreter Lock)
- ABC (Abstract Base Classes)
Алгоритмы:
- Поиск в ширину/глубину (BFS/DFS)
- Деревья (бинарные, красно-черные, AVL)
- Хэш-таблицы
- Динамическое программирование
- Жадные алгоритмы
Базы данных:
- Индексы (B-tree, hash, покрывающие)
- Транзакции (ACID, уровни изоляции)
- Оптимизация запросов (EXPLAIN ANALYZE)
- Репликация и шардирование
System Design:
- Паттерны: CQRS, Event Sourcing, Saga
- Кэширование стратегии (LRU, LFU)
- Message queues (pub/sub, point-to-point)
- Мониторинг и логирование
💡 Советы для собеседования
- Говорите вслух - интервьюеры хотят видеть ход ваших мыслей
- Задавайте уточняющие вопросы перед решением задачи
- Начинайте с простого решения, затем оптимизируйте
- Тестируйте свои решения на граничных случаях
- Знайте сложность своего алгоритма (Big O)
- Объясняйте trade-offs в архитектурных решениях
Удачи на собеседовании! Помните - практика и понимание фундаментальных концепций ключевые.