Задачи LeetCode

Top interview 150 — начатый личный трекер. Разобранные задачи должны хранить не только финальный код, но и восстановимый ход решения.

Карточка разбора

Контракт:
- что означает вход;
- можно ли менять данные;
- что вернуть при пустом входе;
- есть ли дубликаты/overflow.
 
Brute force:
- простое корректное решение;
- время и память.
 
Улучшение:
- какой повтор работы устраняем;
- инвариант цикла/структуры;
- почему решение завершается.
 
Проверки:
- empty / one;
- duplicates;
- min/max;
- already sorted / reverse.

Узнаваемые шаблоны

Сигнал в условии	Проверить
отсортированный массив	binary search, two pointers
непрерывный подмассив	sliding window, prefix sum
пары/частоты	hash map
top K	heap
вложенная структура	DFS/BFS
все варианты	backtracking
оптимум из повторных подзадач	dynamic programming

Пример слияния двух указателей: Merge sorted array.

На собеседовании

• С чего начать после чтения задачи? Пересказать контракт и edge cases.
• Зачем сначала brute force? Зафиксировать корректность и точку оптимизации.
• Что объяснять вместе с кодом? Инвариант и сложность.
• Когда hash map не бесплатна? Есть память O(n), hashing и worst-case/коллизии.