# Этап 1: Алгоритмическое интервью — Yandex Codenv

**Формат:** 1 час, 2 задачи. Остаток времени — обсуждение опыта + вопросы интервьюеру.
**Язык:** Ruby (основной язык, решаем на нём)
**Статус:** готовимся

## Приоритеты подготовки (Must Have — дали они сами)

### 1. Two Pointers
| Задача | Сложность | Ключевой приём |
|--------|-----------|----------------|
| [Container With Most Water](https://leetcode.com/problems/container-with-most-water/) | Medium | Два указателя с краёв, двигать меньшую высоту |
| [Partition Labels](https://leetcode.com/problems/partition-labels/) | Medium | Last occurrence hash + два указателя |
| [Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/) | Easy | Два указателя с краёв (отрицательные → квадрат) |
| [Summary Ranges](https://leetcode.com/problems/summary-ranges/) | Easy | Один проход с началом диапазона |

### 2. Hash Table
| Задача | Сложность | Ключевой приём |
|--------|-----------|----------------|
| [Two Sum](https://leetcode.com/problems/two-sum/) | Easy | `Hash` — значение → индекс, один проход |
| [Valid Anagram](https://leetcode.com/problems/valid-anagram/) | Easy | `Array.new(26, 0)` — фиксированный массив под буквы, либо `tally` |
| [Group Anagrams](https://leetcode.com/problems/group-anagrams/) | Medium | Отсортированная строка как ключ, либо `chars.tally` |
| [Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/) | Medium | Префикс-суммы + `Hash.new(0)` (count) |
| [Find All Anagrams in a String](https://leetcode.com/problems/find-all-anagrams-in-a-string/) | Medium | Скользящее окно + hash/Array[26] |
| [Permutation in String](https://leetcode.com/problems/permutation-in-string/) | Medium | То же, что анаграммы, окно фиксированной длины |
| [Single Number](https://leetcode.com/problems/single-number/) | Easy | **Важно: O(1) по памяти → XOR**. Не hash! `reduce(:^)` |

### 3. Sort
| Задача | Сложность | Ключевой приём |
|--------|-----------|----------------|
| [Merge Intervals](https://leetcode.com/problems/merge-intervals/) | Medium | `sort_by(&:first)`, затем слияние |

### 4. Queue / Stack
| Задача | Сложность | Ключевой приём |
|--------|-----------|----------------|
| [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) | Easy | Массив как стек: `stack << c` / `stack.pop` |

### 5. Sliding Window (самые сложные)
| Задача | Сложность | Ключевой приём |
|--------|-----------|----------------|
| [Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/) | Hard | **Монотонная deque** (по убыванию). В Ruby — массив + ручная реализация очереди с двух концов |
| [Sliding Window Median](https://leetcode.com/problems/sliding-window-median/) | Hard | Две кучи через `Containers::MaxHeap/MinHeap` из гема `algorithms`, либо отсортированный массив + бинарный поиск для вставки/удаления. **Уточни у интервьюера, можно ли `algorithms` gem.** Если нет — sorted array + `bsearch_index` |

### 6. Iterator
| Задача | Сложность | Ключевой приём |
|--------|-----------|----------------|
| [Peeking Iterator](https://leetcode.com/problems/peeking-iterator/) | Medium | Кэшировать следующий элемент: поле `@next_val` и флаг `@has_next` |

### 7. Greedy
| Задача | Сложность | Ключевой приём |
|--------|-----------|----------------|
| [Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/) | Easy | Один проход: `min_price` + `max_profit` |
| [Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/) | Medium | Суммировать все `max(0, prices[i] - prices[i-1])` |
| [Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/) | Medium | DP с двумя состояниями: `hold`, `cash` |

---

## Дополнительная тренировка («для набора формы»)

| Тема | Задачи | Сложность |
|------|--------|-----------|
| Linked Lists | Merge K Sorted Lists, Reverse Linked List | Medium / Easy |
| DFS/BFS | Number of Islands, Remove Invalid Parentheses | Medium / Hard |
| Heap/Hash | Top K Frequent Words | Medium |
| Binary Search | Binary Search | Easy |
| Tree | Same Tree, Symmetric Tree, Subtree of Another Tree, Find Duplicate Subtrees | Easy-Medium |
| Math/String | Add Binary, Add Strings, Multiply Strings | Easy-Medium |

---

## Стратегия на интервью

### Тайм-менеджмент (60 минут)
- **0–5 мин:** понять первую задачу, задать уточняющие вопросы (ограничения, типы данных, edge cases)
- **5–10 мин:** обсудить подход вслух, предложить brute-force → оптимизацию
- **10–20 мин:** написать код
- **20–25 мин:** прогнать тестовый пример, проверить edge cases
- **25–30 мин:** вторая задача — тот же цикл
- **55–60 мин:** вопросы интервьюеру

### Коммуникация (важнее идеального кода!)
- ❌ Не молчать, пока пишешь
- ✅ Проговаривать: «я думаю о подходе X, потому что ограничения такие-то»
- ✅ Если застрял: «давайте подумаю вслух, что мне известно...»
- ✅ После написания: «давайте пройдём по примеру вручную»

### Ruby-специфика
1. **LeetCode Ruby** — методы немного отличаются от чистого Ruby (например, `String#chars` работает, но `each_char` надёжнее). Проверь в их редакторе.
2. **Enumerable** — твой главный инструмент: `each_with_index`, `each_cons`, `reduce`, `tally`, `chunk_while`
3. **Hash.new(0)** — для счётчиков с дефолтным значением
4. **bsearch / bsearch_index** — бинарный поиск в отсортированном массиве
5. **Стек/очередь** — массив: `push << x`, `pop`, `shift` (O(n) для shift — в редких задачах может быть критично)

---

## План подготовки (порядок)

### День 1–2: Must Have — базовые (6 задач)
Two Sum, Valid Anagram, Single Number (XOR!), Valid Parentheses, Squares of a Sorted Array, Summary Ranges
- **Цель:** размяться, вспомнить LeetCode Ruby

### День 3–4: Must Have — средние (8 задач)
Container With Most Water, Partition Labels, Group Anagrams, Subarray Sum Equals K, Merge Intervals, Find All Anagrams, Permutation in String, Peeking Iterator

### День 5: Must Have — greedy (3 задачи)
Best Time to Buy/Sell I, II, with Transaction Fee

### День 6: Must Have — Hard (2 задачи)
Sliding Window Maximum, Sliding Window Median
- **Это самые вероятные на «вторую, сложную» задачу**
- Для Median: реши через sorted array + `bsearch_index` (без гемов) — универсально

### День 7: Дополнительные (по остаточному времени)
Binary Search, Merge K Sorted Lists, Reverse Linked List, Number of Islands, Top K Frequent Words, Same Tree

### День 8: Пробный прогон
- 2 случайные задачи из списка, 1 час. Без подсказок.
- Повтори 2–3 раза.

---

## Ruby-шпаргалка (повторить перед интервью)

```ruby
# XOR для Single Number — O(1) memory
nums.reduce(:^)

# Два указателя
l, r = 0, nums.length - 1
while l < r
  # ...
  l += 1  # или r -= 1
end

# Hash с дефолтным значением (счётчик)
count = Hash.new(0)
count[key] += 1

# Hash с проверкой наличия
if map.key?(target)
  return [map[target], i]
end

# Префикс-суммы + Hash (Subarray Sum Equals K)
prefix = Hash.new(0)
prefix[0] = 1  # ← базовый случай! Без него — ошибка
sum = 0
count = 0
nums.each do |n|
  sum += n
  count += prefix[sum - k]
  prefix[sum] += 1
end

# Стек через массив
stack = []
stack << '('             # push
top = stack.last         # peek
stack.pop                # pop

# Сортировка
intervals.sort_by!(&:first)
# или
nums.sort!

# Скользящее окно фиксированного размера
(0...s.length).each do |i|
  # добавить s[i] в окно
  if i >= window_size
    # удалить s[i - window_size]
  end
  if i >= window_size - 1
    # окно готово — обработать
  end
end

# Бинарный поиск в отсортированном массиве
idx = arr.bsearch_index { |x| x >= target }

# Enumerable — удобные методы
chars = s.each_char.to_a
counts = s.each_char.tally        # Hash с частотами
s.each_char.with_index do |ch, i| # с индексом
prices.each_cons(2) do |a, b|     # скользящие пары

# Массив фиксированного размера для букв
freq = Array.new(26, 0)
freq[ch.ord - 'a'.ord] += 1

# DP: два состояния
hold = -Float::INFINITY
cash = 0
prices.each do |price|
  prev_cash = cash
  cash = [cash, hold + price].max
  hold = [hold, prev_cash - price - fee].max
end
```