Алгоритмы

Алгоритмические задачи награждают распознавание паттерна раньше, чем заучивание реализации. Sorting и searching требуют preconditions — sorted input, monotonic predicate или unweighted edges. Two pointers и sliding window убирают повторные проходы при монотонном движении. Prefix sums превращают range query в O(1) разность. Recursion и backtracking исследуют дерево выборов. Dynamic programming применим при overlapping subproblems и optimal substructure. Greedy работает только с доказательством.

На интервью: назовите паттерн, preconditions, время и память, сравните с альтернативой.

Типовые ошибки: форсировать DP, когда хватит hash map или greedy; код до формулировки инвариантов; игнорировать глубину стека у рекурсии.

Чеклист:

• Определите семейство паттерна.
• Докажите preconditions.
• Оцените время и память.
• Углубляйтесь через дочерние темы.