📌 Алгоритмы и структуры данных

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

Стратегии масштабирования:

1. Горизонтальное шардирование транзакций по user_id

2. Кэширование горячих данных в Redis (TTL 5-15 минут)

3. Репликация для чтения (1 мастер, N реплик)

4. Асинхронная обработка через очереди:

   • Отправка email-уведомлений
   • Обновление аналитики
   • Индексация для поиска

5. 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)
• Мониторинг и логирование

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

1. Говорите вслух - интервьюеры хотят видеть ход ваших мыслей
2. Задавайте уточняющие вопросы перед решением задачи
3. Начинайте с простого решения, затем оптимизируйте
4. Тестируйте свои решения на граничных случаях
5. Знайте сложность своего алгоритма (Big O)
6. Объясняйте trade-offs в архитектурных решениях

Удачи на собеседовании! Помните - практика и понимание фундаментальных концепций ключевые.