# 20 задач для подготовки к алгоритмическому собеседованию JavaScript

## Уровень D (Базовый) - 1-4 задачи

### Задача 1: Валидация email адресов в базе пользователей
**Сложность:** D  
**Проверяемые навыки:**
- Структура данных: Array (Массив)
- Алгоритм: Линейный поиск с условием
- Сложность: O(n) время, O(1) память

**Описание:**  
У вас есть массив email-адресов пользователей. Нужно найти и вернуть все валидные email-адреса (содержат '@' и '.'). 

**Прикладное применение:** Очистка пользовательских данных перед отправкой рассылки.

```javascript
// Входные данные
const emails = ["user@mail.com", "invalid.email", "test@domain.org", "bad@"];

// Ожидаемый результат
// ["user@mail.com", "test@domain.org"]
```

---

### Задача 2: Подсчет частоты просмотров страниц
**Сложность:** D  
**Проверяемые навыки:**
- Структура данных: Hash Table (Map/Object)
- Алгоритм: Хеширование
- Сложность: O(n) время, O(k) память, где k - уникальные элементы

**Описание:**  
Дан массив с URL страниц, которые посещал пользователь. Вернуть объект с количеством посещений каждой страницы.

**Прикладное применение:** Аналитика поведения пользователей на сайте.

```javascript
// Входные данные
const visits = ["/home", "/about", "/home", "/contact", "/home"];

// Ожидаемый результат
// { "/home": 3, "/about": 1, "/contact": 1 }
```

---

### Задача 3: Поиск пользователя по ID в отсортированном списке
**Сложность:** D+  
**Проверяемые навыки:**
- Структура данных: Sorted Array (Отсортированный массив)
- Алгоритм: Binary Search (Бинарный поиск)
- Сложность: O(log n) время, O(1) память

**Описание:**  
Дан отсортированный массив ID пользователей. Найти индекс пользователя с заданным ID или вернуть -1.

**Прикладное применение:** Быстрый поиск в большой базе пользователей.

```javascript
// Входные данные
const userIds = [101, 205, 309, 412, 518, 624];
const targetId = 412;

// Ожидаемый результат: 3
```

---

### Задача 4: Удаление дубликатов из списка товаров
**Сложность:** D+  
**Проверяемые навыки:**
- Структура данных: Set (Множество)
- Алгоритм: Использование хеш-структуры
- Сложность: O(n) время, O(n) память

**Описание:**  
Дан массив артикулов товаров, может содержать дубликаты. Вернуть массив уникальных артикулов в исходном порядке.

**Прикладное применение:** Очистка списка товаров в корзине.

```javascript
// Входные данные
const products = ["SKU001", "SKU002", "SKU001", "SKU003", "SKU002"];

// Ожидаемый результат
// ["SKU001", "SKU002", "SKU003"]
```

---

## Уровень C (Средний) - 5-9 задачи

### Задача 5: Поиск пары товаров на заданную сумму
**Сложность:** C  
**Проверяемые навыки:**
- Структура данных: Hash Table
- Алгоритм: Two Sum Pattern
- Паттерн: Hash Map для комплементов
- Сложность: O(n) время, O(n) память

**Описание:**  
Дан массив цен товаров и бюджет покупателя. Найти индексы двух товаров, сумма которых равна бюджету.

**Прикладное применение:** Рекомендация товаров в интернет-магазине.

```javascript
// Входные данные
const prices = [50, 120, 30, 80, 150];
const budget = 180;

// Ожидаемый результат: [1, 4] (120 + 60 = 180)
```

---

### Задача 6: Максимальная выручка за период (скользящее окно)
**Сложность:** C  
**Проверяемые навыки:**
- Структура данных: Array
- Алгоритм: Sliding Window (Скользящее окно)
- Паттерн: Fixed Window
- Сложность: O(n) время, O(1) память

**Описание:**  
Дан массив ежедневной выручки магазина. Найти максимальную выручку за любые k последовательных дней.

**Прикладное применение:** Анализ продаж для определения лучшего периода.

```javascript
// Входные данные
const dailyRevenue = [100, 200, 300, 400, 100];
const k = 3; // 3 дня

// Ожидаемый результат: 900 (дни 1-3: 200+300+400)
```

---

### Задача 7: Проверка валидности скобок в коде
**Сложность:** C  
**Проверяемые навыки:**
- Структура данных: Stack (Стек)
- Алгоритм: Matching Parentheses
- Паттерн: Stack для парных элементов
- Сложность: O(n) время, O(n) память

**Описание:**  
Дана строка с различными скобками. Проверить, все ли скобки правильно закрыты и вложены.

**Прикладное применение:** Валидация синтаксиса кода в IDE.

```javascript
// Входные данные
const code1 = "{[()]}";  // true
const code2 = "{[(])}";  // false
```

---

### Задача 8: Реверс связного списка заказов
**Сложность:** C+  
**Проверяемые навыки:**
- Структура данных: Linked List (Связный список)
- Алгоритм: In-place Reversal
- Паттерн: Три указателя (prev, current, next)
- Сложность: O(n) время, O(1) память

**Описание:**  
Дан связный список заказов. Развернуть список так, чтобы последний заказ стал первым.

**Прикладное применение:** Изменение приоритета обработки заказов.

```javascript
// Входные данные
// 1 -> 2 -> 3 -> 4 -> null

// Ожидаемый результат
// 4 -> 3 -> 2 -> 1 -> null
```

---

### Задача 9: Поиск цикла в цепочке редиректов
**Сложность:** C+  
**Проверяемые навыки:**
- Структура данных: Linked List
- Алгоритм: Floyd's Cycle Detection (Fast & Slow Pointers)
- Паттерн: Два указателя разной скорости
- Сложность: O(n) время, O(1) память

**Описание:**  
Дана цепочка URL редиректов. Определить, есть ли циклический редирект (бесконечный цикл).

**Прикладное применение:** Проверка корректности настройки редиректов на сайте.

```javascript
// Входные данные
// A -> B -> C -> D -> B (есть цикл)

// Ожидаемый результат: true
```

---

## Уровень B (Продвинутый) - 10-14 задачи

### Задача 10: Слияние интервалов рабочего времени
**Сложность:** B  
**Проверяемые навыки:**
- Структура данных: Array of Intervals
- Алгоритм: Merge Intervals Pattern
- Паттерн: Сортировка + слияние пересекающихся интервалов
- Сложность: O(n log n) время, O(n) память

**Описание:**  
Даны интервалы рабочих смен сотрудников. Объединить пересекающиеся смены для оптимизации расписания.

**Прикладное применение:** Составление графика работы и определение нагрузки.

```javascript
// Входные данные
const shifts = [[1, 3], [2, 6], [8, 10], [9, 12], [15, 18]];

// Ожидаемый результат
// [[1, 6], [8, 12], [15, 18]]
```

---

### Задача 11: Обход дерева категорий товаров (BFS)
**Сложность:** B  
**Проверяемые навыки:**
- Структура данных: Tree (Дерево)
- Алгоритм: Breadth-First Search (BFS)
- Паттерн: Level-order traversal с очередью
- Сложность: O(n) время, O(w) память, где w - ширина дерева

**Описание:**  
Дано дерево категорий товаров. Вывести все категории по уровням (сначала главные, затем подкатегории).

**Прикладное применение:** Построение навигационного меню магазина.

```javascript
// Входные данные
//       Электроника
//      /           \
//   Ноутбуки    Телефоны
//   /     \        |
// Apple  Dell   Samsung

// Ожидаемый результат
// [["Электроника"], ["Ноутбуки", "Телефоны"], ["Apple", "Dell", "Samsung"]]
```

---

### Задача 12: Поиск похожих товаров (DFS)
**Сложность:** B  
**Проверяемые навыки:**
- Структура данных: Tree/Graph
- Алгоритм: Depth-First Search (DFS)
- Паттерн: Рекурсивный обход дерева
- Сложность: O(n) время, O(h) память, где h - высота

**Описание:**  
Дано дерево связанных товаров. Найти все товары в категории, используя глубинный поиск.

**Прикладное применение:** Система рекомендаций "Похожие товары".

```javascript
// Найти все товары в подкатегории "Ноутбуки"
```

---

### Задача 13: K самых популярных товаров
**Сложность:** B+  
**Проверяемые навыки:**
- Структура данных: Heap (Min-Heap)
- Алгоритм: Top K Elements Pattern
- Паттерн: Использование кучи для K наибольших элементов
- Сложность: O(n log k) время, O(k) память

**Описание:**  
Дан список товаров с количеством покупок. Найти K самых популярных товаров.

**Прикладное применение:** Блок "Хиты продаж" на главной странице.

```javascript
// Входные данные
const purchases = {
  "iPhone": 150,
  "Samsung": 120,
  "Xiaomi": 200,
  "Huawei": 80
};
const k = 2;

// Ожидаемый результат
// ["Xiaomi", "iPhone"]
```

---

### Задача 14: Объединение отсортированных списков товаров
**Сложность:** B+  
**Проверяемые навыки:**
- Структура данных: Multiple Sorted Lists + Heap
- Алгоритм: K-way Merge Pattern
- Паттерн: Min-Heap для слияния k списков
- Сложность: O(n log k) время, где n - всего элементов

**Описание:**  
Даны отсортированные списки товаров от разных поставщиков. Объединить в один отсортированный список.

**Прикладное применение:** Агрегация товаров от нескольких поставщиков.

```javascript
// Входные данные
const supplier1 = [10, 50, 100];
const supplier2 = [20, 40, 80];
const supplier3 = [5, 35, 90];

// Ожидаемый результат
// [5, 10, 20, 35, 40, 50, 80, 90, 100]
```

---

## Уровень A (Экспертный) - 15-20 задачи

### Задача 15: Максимальная прибыль от продажи акций
**Сложность:** A-  
**Проверяемые навыки:**
- Структура данных: Array
- Алгоритм: Dynamic Programming (Kadane's Algorithm вариант)
- Паттерн: DP с отслеживанием минимума
- Сложность: O(n) время, O(1) память

**Описание:**  
Дан массив цен акций по дням. Найти максимальную прибыль от одной покупки и продажи.

**Прикладное применение:** Анализ торговых стратегий.

```javascript
// Входные данные
const prices = [7, 1, 5, 3, 6, 4];

// Ожидаемый результат: 5 (купить за 1, продать за 6)
```

---

### Задача 16: Количество способов доставки заказа
**Сложность:** A-  
**Проверяемые навыки:**
- Структура данных: Array для DP-таблицы
- Алгоритм: Dynamic Programming (Climbing Stairs вариант)
- Паттерн: Bottom-up DP
- Сложность: O(n) время, O(n) или O(1) память

**Описание:**  
Курьер может доставить 1 или 2 заказа за раз. Найти количество способов доставить n заказов.

**Прикладное применение:** Оптимизация логистики доставки.

```javascript
// Входные данные
const n = 5; // 5 заказов

// Ожидаемый результат: 8 способов
// (1+1+1+1+1, 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2, 2+2+1, 2+1+2, 1+2+2)
```

---

### Задача 17: Поиск подстроки продуктов (генерация подмножеств)
**Сложность:** A  
**Проверяемые навыки:**
- Структура данных: Array
- Алгоритм: Backtracking (Subsets Pattern)
- Паттерн: Рекурсивная генерация всех подмножеств
- Сложность: O(2^n) время, O(n) память (стек рекурсии)

**Описание:**  
Дан набор характеристик товара. Сгенерировать все возможные комбинации характеристик для фильтров.

**Прикладное применение:** Генерация всех вариантов фильтров в каталоге.

```javascript
// Входные данные
const features = ["цвет", "размер", "материал"];

// Ожидаемый результат
// [[], ["цвет"], ["размер"], ["материал"], 
//  ["цвет", "размер"], ["цвет", "материал"], 
//  ["размер", "материал"], ["цвет", "размер", "материал"]]
```

---

### Задача 18: Поиск кратчайшего пути доставки
**Сложность:** A  
**Проверяемые навыки:**
- Структура данных: Graph (Граф)
- Алгоритм: BFS для невзвешенного графа / Dijkstra для взвешенного
- Паттерн: Обход графа с отслеживанием расстояний
- Сложность: O(V + E) время для BFS, O((V + E) log V) для Dijkstra

**Описание:**  
Дана карта города (граф) с пунктами выдачи. Найти кратчайший путь от склада до клиента.

**Прикладное применение:** Оптимизация маршрутов курьерской доставки.

```javascript
// Входные данные
const cityMap = {
  "Склад": ["Пункт1", "Пункт2"],
  "Пункт1": ["Пункт3"],
  "Пункт2": ["Пункт3", "Клиент"],
  "Пункт3": ["Клиент"]
};

// Найти кратчайший путь от "Склад" до "Клиент"
// Ожидаемый результат: ["Склад", "Пункт2", "Клиент"]
```

---

### Задача 19: Определение порядка сборки продукта
**Сложность:** A+  
**Проверяемые навыки:**
- Структура данных: Directed Graph (Ориентированный граф)
- Алгоритм: Topological Sort (Kahn's Algorithm или DFS)
- Паттерн: Обработка зависимостей
- Сложность: O(V + E) время, O(V) память

**Описание:**  
Даны этапы сборки продукта с зависимостями. Определить правильный порядок выполнения этапов.

**Прикладное применение:** Планирование производственного процесса.

```javascript
// Входные данные
const stages = ["подготовка", "сборка", "упаковка", "отгрузка"];
const dependencies = [
  ["подготовка", "сборка"],
  ["сборка", "упаковка"],
  ["упаковка", "отгрузка"]
];

// Ожидаемый результат
// ["подготовка", "сборка", "упаковка", "отгрузка"]
```

---

### Задача 20: Оптимальное распределение задач между серверами
**Сложность:** A+  
**Проверяемые навыки:**
- Структура данных: Array + Heap
- Алгоритм: Dynamic Programming + Greedy + Two Heaps
- Паттерн: Минимизация максимальной нагрузки
- Сложность: O(n log n) время, O(n) память

**Описание:**  
Даны задачи с временем выполнения и k серверов. Распределить задачи так, чтобы минимизировать максимальное время работы любого сервера.

**Прикладное применение:** Балансировка нагрузки в облачной инфраструктуре.

```javascript
// Входные данные
const tasks = [3, 5, 2, 7, 4, 1]; // время выполнения в минутах
const servers = 3;

// Ожидаемый результат
// Сервер 1: [7, 1] = 8 минут
// Сервер 2: [5, 3] = 8 минут
// Сервер 3: [4, 2] = 6 минут
// Максимальное время: 8 минут
```

---

## Рекомендации по подготовке

### План изучения:
1. **Неделя 1-2:** Задачи D уровня (освоение базовых структур)
2. **Неделя 3-4:** Задачи C уровня (паттерны Two Pointers, Sliding Window, Stack)
3. **Неделя 5-6:** Задачи B уровня (Trees, Heaps, продвинутые паттерны)
4. **Неделя 7-8:** Задачи A уровня (DP, Graphs, комплексные задачи)

### Ключевые структуры данных для приоритетного изучения:
✅ **Критичные:** Array, Hash Table, Stack, Queue  
✅ **Важные:** Linked List, Binary Tree, Heap  
✅ **Продвинутые:** Graph, Trie

### Основные паттерны (в порядке важности):
1. Two Pointers / Sliding Window
2. Hash Table для быстрого поиска
3. BFS/DFS для деревьев и графов
4. Dynamic Programming
5. Binary Search
6. Backtracking

### Полезные ресурсы:
- **LeetCode:** Практика задач по паттернам
- **NeetCode:** Видеоразборы популярных задач
- **GreatFrontEnd:** Специально для фронтенд-разработчиков
- **Educative - Grokking the Coding Interview:** Систематизированный курс

**Совет:** Решайте задачи по паттернам, а не в случайном порядке. После каждой задачи записывайте паттерн и подход к решению в свой конспект.