Профессия:
Решение
Базовый запрос: Топ-5 по выручке
SELECT
product_name,
SUM(quantity * price) AS total_revenue
FROM sales
GROUP BY product_name
ORDER BY total_revenue DESC
LIMIT 5;
Объяснение:
SUM(quantity * price) — рассчитываем выручку как произведение количества и ценыGROUP BY product_name — группируем данные по названию продуктаORDER BY total_revenue DESC — сортируем по выручке в убывающем порядкеLIMIT 5 — берём только первые 5 строкВариант 2: С дополнительной статистикой
Часто нужна не только выручка, но и другие метрики:
SELECT
product_name,
COUNT(*) AS number_of_sales,
SUM(quantity) AS total_quantity,
ROUND(AVG(price), 2) AS avg_price,
SUM(quantity * price) AS total_revenue,
ROW_NUMBER() OVER (ORDER BY SUM(quantity * price) DESC) AS rank
FROM sales
GROUP BY product_name
ORDER BY total_revenue DESC
LIMIT 5;
Решение: EDA на датасете клиентов банка
1. Описательная статистика
Начинаем с базового анализа данных:
import pandas as pd
import numpy as np
# Загрузка данных
df = pd.read_csv("bank_clients.csv")
# Основная информация
print(df.info())
print(df.shape)
print(df.describe())
# Пропуски
print(df.isnull().sum())
print(df.isnull().sum() / len(df) * 100) # % пропусков
Ключевые метрики:
2. Распределения признаков
import matplotlib.pyplot as plt
import seaborn as sns
# Числовые признаки
numerical_cols = df.select_dtypes(include=[np.number]).columns
fig, axes = plt.subplots(3, 3, figsize=(15, 12))
for idx, col in enumerate(numerical_cols):
ax = axes[idx // 3, idx % 3]
df[col].hist(bins=30, ax=ax, edgecolor="black")
ax.set_title(f"Распределение {col}")
ax.set_ylabel("Частота")
SQL решение
Условие задачи
Нужно выбрать названия и цены анализов, которые продавались с 5 февраля 2020 года на протяжении всей следующей недели (5-11 февраля 2020 включительно).
SQL запрос
SELECT
name,
price
FROM sales
WHERE sale_date >= "2020-02-05"
AND sale_date <= "2020-02-11"
ORDER BY sale_date, name;
Альтернативный вариант с BETWEEN
SELECT
name,
price
FROM sales
WHERE sale_date BETWEEN "2020-02-05" AND "2020-02-11"
ORDER BY sale_date, name;
Объяснение
Фильтр по датам: Условие sale_date >= "2020-02-05" AND sale_date <= "2020-02-11" отбирает все записи в диапазоне от 5 февраля (начало недели) по 11 февраля включительно (конец недели).
BETWEEN оператор: Эквивалентный способ записи более компактен и читаемый. BETWEEN включает оба граничных значения.
Выбранные столбцы: name (название анализа) и price (цена) — ровно то, что требует задача.
Доверительный интервал для доли: 95% CI
Условие задачи
Найти 95% доверительный интервал для истинной доли положительных ответов в популяции.
Решение
Шаг 1: Вычисляем выборочную долю
p̂ = x / n = 520 / 1000 = 0.52 = 52%
Шаг 2: Вычисляем стандартную ошибку (SE)
SE = sqrt(p̂ × (1 - p̂) / n)
= sqrt(0.52 × 0.48 / 1000)
= sqrt(0.2496 / 1000)
= sqrt(0.0002496)
≈ 0.01580
Шаг 3: Определяем критическое значение
Для 95% доверительного уровня используем z-распределение (нормальное приближение):
z = 1.96 (для 95% доверия)
Шаг 4: Вычисляем границы интервала
Маржа ошибки (ME) = z × SE
= 1.96 × 0.01580
≈ 0.0309
Нижняя граница = p̂ - ME = 0.52 - 0.0309 ≈ 0.4891
Верхняя граница = p̂ + ME = 0.52 + 0.0309 ≈ 0.5509
Ответ
95% Доверительный интервал: [0.4891, 0.5509] или [48.91%, 55.09%]
Решение
Для предсказания оттока клиентов из транзакционных данных предлагаю 10 информативных признаков:
1. Average Transaction Amount (Средняя сумма транзакции)
df['avg_transaction_amount'] = df.groupby('customer_id')['amount'].transform('mean')
Почему информативно: Клиенты с низкими средними суммами могут быть более чувствительны к комиссиям и процентам. Высокие суммы указывают на лояльность банку (не переходят в конкурентов).
Интерпретация: avg < 100 → высокий риск оттока (75% вероятность), avg > 1000 → низкий риск (15% вероятность).
2. Transaction Frequency (Частота транзакций в месяц)
df['date'] = pd.to_datetime(df['date'])
df['year_month'] = df['date'].dt.to_period('M')
tx_per_month = df.groupby(['customer_id', 'year_month']).size().reset_index(name='count')
df['avg_monthly_transactions'] = tx_per_month.groupby('customer_id')['count'].transform('mean')
A/B тест: Анализ результатов эксперимента
1. Расчёт конверсионных показателей
Группа A (контроль):
Группа B (тест):
Прирост: (380 - 320) / 320 = 18.75% относительное улучшение
2. Проверка статистической значимости (двухвыборочный z-тест)
Нулевая гипотеза H₀: Конверсии групп одинаковы (p_A = p_B) Альтернативная гипотеза H₁: Конверсии различаются (p_A ≠ p_B)
Расчёт:
Вывод: p-value > 0.05, различие НЕ статистически значимо на уровне 5%.
3. Доверительный интервал (95%)
Для разницы пропорций: Δp ± z₀.₀₂₅ × SE_diff
Вероятность суммы при бросании двух костей
Условие задачи
Бросаем две игральные кости (d6). Найти вероятность сумм 4 и 8.
Основной принцип
Всего возможных исходов = 6 × 6 = 36
Вероятность = (Количество благоприятных исходов) / 36
Вопрос 1: Вероятность суммы = 4
Чтобы получить сумму 4, нужны пары:
Всего 3 благоприятных исхода.
P(Сумма = 4) = 3 / 36 = 1 / 12 ≈ 0.0833 ≈ 8.33%
| Кость 1 | Кость 2 | Сумма |
|---|---|---|
| 1 | 3 | 4 |
| 2 | 2 | 4 |
| 3 | 1 | 4 |
Вопрос 2: Вероятность суммы = 8
Чтобы получить сумму 8, нужны пары:
Решение
Пайплайн очистки данных на Pandas
Создам полный пайплайн с объяснением каждого шага обработки грязного датасета. Это критически важный этап, так как данные низкого качества приводят к неверным выводам.
Загрузка и инициальная диагностика
import pandas as pd
import numpy as np
from scipy import stats
import warnings
warnings.filterwarnings('ignore')
# Загрузка датасета
df = pd.read_csv('dirty_data.csv')
# Инициальная диагностика
print(f"Размер датасета: {df.shape}")
print(f"\nТипы данных:\n{df.dtypes}")
print(f"\nПропущенные значения:\n{df.isnull().sum()}")
print(f"\nПроцент пропусков:\n{df.isnull().sum() / len(df) * 100}")
print(f"\nОсновная статистика:\n{df.describe()}")
# Проверка дубликатов
print(f"\nДубликаты: {df.duplicated().sum()}")
Почему это важно: Диагностика показывает масштаб проблем и помогает выбрать оптимальные методы обработки.
Обработка типов данных
ML System Design: Система обнаружения мошенничества
1. Признаки и данные
Основные источники данных:
Транзакционные данные:
Историческая информация пользователя:
Гео-данные:
Time Series: Прогнозирование продаж
1. Анализ временного ряда (EDA)
Декомпозиция временного ряда:
import pandas as pd
from statsmodels.tsa.seasonal import seasonal_decompose
# Загрузка данных
df = pd.read_csv('sales.csv', parse_dates=['date'], index_col='date')
# Декомпозиция
decomposition = seasonal_decompose(df['sales'], model='additive', period=12)
trend = decomposition.trend
seasonal = decomposition.seasonal
residual = decomposition.resid
decomposition.plot()
Компоненты:
Статистический анализ:
from statsmodels.tsa.stattools import adfuller
Скользящее среднее дохода за 3 месяца
Условие задачи
Рассчитать скользящее среднее (moving average) дохода за текущий месяц и два предыдущих месяца (окно размером 3 месяца). Это позволяет сгладить сезонные колебания и увидеть тренд.
Основной SQL запрос
SELECT
EXTRACT(YEAR FROM date) AS year,
EXTRACT(MONTH FROM date) AS month,
SUM(revenue) AS monthly_revenue,
AVG(SUM(revenue)) OVER (
ORDER BY EXTRACT(YEAR FROM date), EXTRACT(MONTH FROM date)
ROWS BETWEEN 2 PRECEDING AND CURRENT ROW
) AS moving_avg_3months
FROM transactions
GROUP BY
EXTRACT(YEAR FROM date),
EXTRACT(MONTH FROM date)
ORDER BY year, month;
Пошаговое объяснение
1. Агрегирование по месяцам:
GROUP BY EXTRACT(YEAR FROM date), EXTRACT(MONTH FROM date)
SUM(revenue) AS monthly_revenue
Сначала вычисляем общий доход за каждый месяц.
Решение: Decision Tree классификатор с нуля
Структура: 2 класса (Node, DecisionTree)
Gini = 1 - sum(p_i^2)
IG = Gini(parent) - (N_left/N * Gini(left) + N_right/N * Gini(right))
Выше IG → лучше разбиение.
Базовый случай (листовой узел):
Рекурсивный случай:
Для каждого объекта:
Решение: Анализ падения конверсии на 15%
1. Структура анализа
Шаг 1: Подтвердить тренд (5 мин)
SELECT
DATE(created_at) as date,
COUNT(DISTINCT user_id) as users,
ROUND(100.0 * COUNT(CASE WHEN action='purchase' THEN 1 END) / COUNT(*), 2) as conv_rate
FROM events
WHERE created_at >= NOW() - INTERVAL 14 days
GROUP BY DATE(created_at)
ORDER BY date DESC;
Шаг 2: Найти где упало в воронке (10 мин)
Если упало на Purchase → проблема с платежами. Если на Checkout → проблема с формой оформления. Если везде одинаково → проблема с трафиком.
2. Гипотезы (приоритизированные)
ВЫСОКИЙ ПРИОРИТЕТ (проверить сразу):
Решение
Способ 1: Встроенный метод duplicated()
Самый простой и быстрый способ — использовать встроенный метод duplicated():
import pandas as pd
# Создание примера датасета
df = pd.DataFrame({
"id": [1, 2, 3, 2, 4, 1],
"name": ["Alice", "Bob", "Charlie", "Bob", "David", "Alice"],
"age": [25, 30, 35, 30, 28, 25]
})
# Способ 1: Найти все дубликаты (не обозначает первое появление)
duplicates = df[df.duplicated()]
print("Дубликаты (keep=False):")
print(df[df.duplicated(keep=False)].sort_values(by="id"))
# Вариант 1a: Сохранить первое появление
duplicates_first = df[df.duplicated(keep="first")]
print("\nДубликаты (keep=first):")
print(duplicates_first)
# Вариант 1b: Сохранить последнее появление
duplicates_last = df[df.duplicated(keep="last")]
print("\nДубликаты (keep=last):")
print(duplicates_last)
Способ 2: Поиск дубликатов по конкретным столбцам
Часто нужно найти дубликаты только по определённым колонкам:
Решение: Найти пользователей без заказов
Способ 1: LEFT JOIN (стандартный и быстрый)
SELECT u.user_id, u.name, u.email
FROM users u
LEFT JOIN orders o ON u.user_id = o.user_id
WHERE o.user_id IS NULL;
Логика: LEFT JOIN соединяет таблицы, пользователи без заказов имеют NULL в полях orders. Фильтруем WHERE o.user_id IS NULL.
Производительность: O(n log n), использует индекс на orders.user_id
Преимущества:
Способ 2: NOT EXISTS (для больших таблиц)
SELECT u.user_id, u.name, u.email
FROM users u
WHERE NOT EXISTS (
SELECT 1
FROM orders o
WHERE o.user_id = u.user_id
);
Логика: Для каждого пользователя проверяем, существует ли хотя бы один заказ. NOT EXISTS вернёт true если подзапрос не вернул ни одной строки.
Преимущества:
Нарастающий итог продаж по месяцам
Условие задачи
Рассчитать нарастающий итог (cumulative sum) количества проданных товаров по месяцам каждого года с разбивкой по группам товаров.
Основной SQL запрос
SELECT
EXTRACT(YEAR FROM sale_date) AS year,
EXTRACT(MONTH FROM sale_date) AS month,
group_name,
SUM(quantity) AS monthly_quantity,
SUM(SUM(quantity)) OVER (
PARTITION BY EXTRACT(YEAR FROM sale_date), group_name
ORDER BY EXTRACT(MONTH FROM sale_date)
) AS cumulative_quantity
FROM sales
GROUP BY
EXTRACT(YEAR FROM sale_date),
EXTRACT(MONTH FROM sale_date),
group_name
ORDER BY year, group_name, month;
Пошаговое объяснение
1. Выделение года и месяца:
EXTRACT(YEAR FROM sale_date) AS year,
EXTRACT(MONTH FROM sale_date) AS month
2. Агрегирование по месяцам и группам:
GROUP BY EXTRACT(YEAR FROM sale_date), EXTRACT(MONTH FROM sale_date), group_name
SQL: Найти второго по зарплате сотрудника
Условие
Дана таблица employees:
CREATE TABLE employees (
id INT PRIMARY KEY,
name VARCHAR(100),
salary DECIMAL(10, 2),
department_id INT
);
Нужно найти второго по зарплате сотрудника в каждом департаменте.
Решение 1: Оконная функция ROW_NUMBER()
-- Самое простое и рекомендуемое решение
WITH ranked_employees AS (
SELECT
id,
name,
salary,
department_id,
ROW_NUMBER() OVER (PARTITION BY department_id ORDER BY salary DESC) AS rank
FROM employees
)
SELECT
id,
name,
salary,
department_id
FROM ranked_employees
WHERE rank = 2;
Решение
1. Аналитическое решение (Нормальное уравнение)
import numpy as np
import matplotlib.pyplot as plt
ML System Design: Поисковая выдача (Search Ranking)
1. Архитектура: Retrieval → Ranking
Двухэтапная архитектура:
User Query
↓
[RETRIEVAL STAGE] ← Быстро, низкая точность
- ElasticSearch / Solr
- BM25 ranking
- ~1000 документов
↓
[RANKING STAGE] ← Медленнее, высокая точность
- ML модель (Learning to Rank)
- ~100 документов (top k)
↓
Final Results (10 документов)
Почему два этапа?
2. Feature Engineering
Query Features (зависят только от запроса):
Решение
1. Sigmoid функция и Binary Cross-Entropy Loss
import numpy as np
import matplotlib.pyplot as plt
Решение
1. Предобработка текста
import pandas as pd
import numpy as np
import re
from nltk.corpus import stopwords
from nltk.tokenize import word_tokenize
from nltk.stem import SnowballStemmer, WordNetLemmatizer
import nltk
# Загрузить необходимые ресурсы
nltk.download('punkt')
nltk.download('stopwords')
nltk.download('wordnet')
# Загрузка данных
df = pd.read_csv('reviews.csv')
print(f"Размер датасета: {df.shape}")
print(f"\nПримеры отзывов:")
print(df['text'].head())
# === ШАГ 1: БАЗОВАЯ ОЧИСТКА ===
def preprocess_text(text):
# Приведение к нижнему регистру
text = text.lower()
# Удаление URL
text = re.sub(r'http\S+|www.\S+', '', text)
# Удаление email
text = re.sub(r'\S+@\S+', '', text)
# Удаление специальных символов (сохраняем букву, цифру, пробел)
text = re.sub(r'[^a-zA-Zа-яА-Я0-9\s]', '', text)
# Удаление лишних пробелов
text = re.sub(r'\s+', ' ', text).strip()
return text
Удаление дубликатов без создания новой таблицы
Условие задачи
Полные дубликаты (абсолютно идентичные строки) появились в таблице. Нужно удалить их без создания новой таблицы и без потери оригинальных данных.
Оптимальный подход: используем оконную функцию ROW_NUMBER()
Ключевая идея: присваиваем каждой строке номер в рамках группы дубликатов. Первой копии присваиваем 1, остальным — 2, 3, ... и удаляем все строки с номером > 1.
Решение 1: Используя CTE и ROW_NUMBER (РЕКОМЕНДУЕТСЯ)
WITH duplicates AS (
SELECT
*,
ROW_NUMBER() OVER (PARTITION BY col1, col2, col3, ... ORDER BY rowid) AS rn
FROM your_table
)
DELETE FROM your_table
WHERE rowid IN (
SELECT rowid FROM duplicates WHERE rn > 1
);
Решение 2: Если есть id столбец
DELETE FROM your_table
WHERE id NOT IN (
SELECT MIN(id)
FROM your_table
GROUP BY col1, col2, col3, ...
);
SQL: Retention пользователей по когортам
Определения
Когорта — группа пользователей, объединённых по дате первого события (обычно месяц регистрации)
Retention — процент пользователей из когорты, вернувшихся в конкретный период
Retention по месяцам:
SQL Решение
Шаг 1: Создание таблицы данных
CREATE TABLE user_events (
user_id INT,
event_date DATE,
event_type VARCHAR(50)
);
INSERT INTO user_events VALUES
(1, '2024-01-05', 'signup'),
(1, '2024-01-15', 'purchase'),
(1, '2024-02-10', 'login'),
(2, '2024-01-10', 'signup'),
(2, '2024-01-20', 'login'),
(3, '2024-02-01', 'signup'),
(3, '2024-02-15', 'purchase'),
(3, '2024-03-05', 'login'),
(4, '2024-02-05', 'signup'),
(4, '2024-03-10', 'purchase');
Шаг 2: Полный SQL запрос
Решение
1. Необходимые данные
Для эффективной рекомендательной системы нужны:
Базовые данные:
Метаданные:
2. Подходы к рекомендациям
Основана на предположении: если пользователи A и B похоже покупали раньше, им понравятся одни и те же товары.
from sklearn.metrics.pairwise import cosine_similarity
import numpy as np
Положительная прогностическая ценность (PPV): диагностический тест
Условие задачи
Тест положительный. Какова вероятность, что человек действительно болен?
Определения
Чувствительность (TPR - True Positive Rate):
P(+ | Болен) = 0.99
Вероятность положительного теста при наличии болезни.
Специфичность (TNR - True Negative Rate):
P(- | Не болен) = 0.95
Или: P(+ | Не болен) = 1 - 0.95 = 0.05
Вероятность отрицательного теста при отсутствии болезни.
Распространённость:
P(Болен) = 0.01
P(Не болен) = 0.99
Положительная прогностическая ценность (PPV)
Формула:
PPV = P(Болен | +) = P(+ | Болен) × P(Болен) / P(+)
Решение по теореме Байеса
Шаг 1: Определяем основные вероятности
P(Болен) = 0.01
P(Не болен) = 0.99
P(+ | Болен) = 0.99
P(+ | Не болен) = 0.05
Распределение Пуассона: пассажиры в автобусе
Условие задачи
Поток пассажиров в автобус: λ = 3 пассажира в минуту
Найти вероятность того, что за 2 минуты зайдёт ровно 10 пассажиров.
Распределение Пуассона
Формула:
P(X = k) = (e^(-λ) × λ^k) / k!
где:
- λ (lambda) = параметр распределения (среднее количество событий)
- k = количество событий
- e ≈ 2.71828
- k! = факториал k
Шаг 1: Определяем параметр λ для нашего случая
Поток: 3 пассажира в минуту Время: 2 минуты
λ = 3 × 2 = 6 пассажиров
Поскольку события происходят независимо, параметр Пуассона пропорционален времени.
Шаг 2: Применяем формулу Пуассона
Нужна вероятность k = 10 пассажиров:
P(X = 10) = (e^(-6) × 6^10) / 10!
Шаг 3: Вычисляем компоненты
e^(-6):
e^(-6) ≈ 0.002479
6^10:
6^10 = 60,466,176
10! (факториал):
10! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10
= 3,628,800
Шаг 4: Финальный расчёт
Алгоритм: Найти общих предков в дереве (LCA)
Определение и примеры
LCA (Lowest Common Ancestor) - наименьший общий предок двух узлов. Это узел, который находится на наибольшей глубине и является предком обоих узлов.
Пример дерева:
3
/ \
5 1
/ \
6 2
/ \
7 4
LCA(5, 1) = 3
LCA(5, 4) = 3
LCA(6, 2) = 5
LCA(2, 4) = 2
Решение 1: Рекурсивный поиск (DFS)
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
Python: Реализовать k-means clustering
Полная реализация k-means
import numpy as np
from typing import Tuple, List
import matplotlib.pyplot as plt
Решение
1. Выбор признаков для скоринга
Решение: k ближайших точек к origin
Задача
Даны точки на 2D плоскости и начало координат (origin). Найти K ближайших точек используя heap.
Решение: Max-Heap O(n log k)
Ключевая идея:
import heapq
from typing import List
Вероятность карты из первой коробки: теорема Байеса
Условие задачи
Коробка 1: 5 красных + 3 синих (всего 8 карт) Коробка 2: 4 красных + 6 синих (всего 10 карт)
Выбираем коробку случайно, достаём красную карту. Какова вероятность, что это была коробка 1?
Теорема Байеса
P(Коробка1 | Красная) = P(Красная | Коробка1) × P(Коробка1) / P(Красная)
Шаг 1: Априорные вероятности выбора коробки
P(Коробка1) = 1/2 = 0.5
P(Коробка2) = 1/2 = 0.5
Шаг 2: Вероятность вытащить красную карту из каждой коробки
Из коробки 1:
P(Красная | Коробка1) = 5/8 = 0.625
Из коробки 2:
P(Красная | Коробка2) = 4/10 = 0.4
Шаг 3: Полная вероятность вытащить красную карту
P(Красная) = P(Красная|Коробка1) × P(Коробка1) + P(Красная|Коробка2) × P(Коробка2)
P(Красная) = (5/8) × (1/2) + (4/10) × (1/2)
= 5/16 + 4/20
= 5/16 + 2/10
= 0.3125 + 0.2
= 0.5125
Вероятность нечестной монеты: решение теоремой Байеса
Условие задачи
Берём 1 монету из 100 (99 честных + 1 нечестная). Подбрасываем 10 раз → 10 орлов подряд. Какова вероятность, что это нечестная монета?
Решение с использованием теоремы Байеса
Теорема Байеса:
P(A|B) = P(B|A) × P(A) / P(B)
Где:
Шаг 1: Определяем априорные вероятности
P(A) = P(нечестная) = 1/100 = 0.01
P(¬A) = P(честная) = 99/100 = 0.99
Шаг 2: Вероятность 10 орлов для каждого типа монеты
Если монета честная:
P(10 орлов | честная) = (1/2)^10 = 1/1024 ≈ 0.000977
Если монета нечестная:
P(10 орлов | нечестная) = 1^10 = 1
Шаг 3: Вычисляем полную вероятность наблюдаемого события
P(10 орлов) = P(10 орлов|нечестная)×P(нечестная) + P(10 орлов|честная)×P(честная)
P(10 орлов) = 1 × 0.01 + (1/1024) × 0.99
= 0.01 + 0.000967
= 0.010967
Решение: Metrics Design для e-commerce
1. Ключевые бизнес-метрики
North Star: Gross Merchandise Value (GMV) в месяц
Guardrail:
2. Продуктовые метрики
Воронка: Sessions → Views → Cart → Checkout → Order
Метрики:
Сегментация: device, source, geo
3. Технические метрики
Performance:
Availability:
4. Мониторинг
Дашборды:
Стек: Prometheus, DataDog, ELK, Jaeger
Алерты:
Решение
1. Выбор архитектуры нейросети
| Архитектура | Скорость | Точность | Размер | Рекомендация |
|---|---|---|---|---|
| MobileNet v3 | Отличная | 75% | 5 МБ | Мобильные приложения |
| ResNet-50 | Хорошая | 80% | 100 МБ | Баланс параметров |
| EfficientNet-B0 | Отличная | 80% | 30 МБ | Лучший выбор |
| ViT (Vision Transformer) | Средняя | 85%+ | 300 МБ | Research, большие данные |
| DenseNet-121 | Средняя | 78% | 30 МБ | Компактная, быстрая |
| Inception v3 | Медленная | 80% | 100 МБ | Legacy |
Рекомендация: EfficientNet-B0 — оптимальное соотношение скорости и точности.
import torch
import torch.nn as nn
from torchvision import models
from torchvision.models import EfficientNet_B0_Weights
Решение
Реализация механизма внимания в PyTorch.
1. Scaled Dot-Product Attention
import torch
import torch.nn as nn
import torch.nn.functional as F
import math
Решение: Топ-K частых элементов за O(n log k)
Задача
Найти K наиболее часто встречающихся элементов в массиве за время O(n log k) с использованием heap.
Основной подход: Min-Heap (O(n log k))
Алгоритм:
Примеры
Анализ сложности
Альтернативные подходы
Max-Heap (O(n log n)): Меньше эффективен, но проще когда K близко к количеству уникальных элементов.
Bucket Sort (O(n)): Используем индекс = частота, получаем O(n) временно. Требует O(n) дополнительной памяти.
Практическое применение