514 lines
21 KiB
Markdown
514 lines
21 KiB
Markdown
# 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:** Систематизированный курс
|
||
|
||
**Совет:** Решайте задачи по паттернам, а не в случайном порядке. После каждой задачи записывайте паттерн и подход к решению в свой конспект. |