Публичное собеседование по алгоритмам • Сергей Милимко vs Иван Лещёв

Коротко о видео

В публичном стриме коллеги проводят учебное алгоритмическое собеседование и обсуждают, зачем разработчику знать алгоритмы. Первая задача посвящена поиску M наибольших значений во входном потоке с помощью min-heap: разбираются замена минимума, сложность O(N log M) и ограничение памяти O(M). Во второй задаче участник строит преобразование AST арифметического выражения в PHP-код с минимально необходимыми скобками, учитывая приоритеты, унарные операции и особые случаи вычитания; после отладки тесты проходят, до третьей задачи не доходят.

Затронутые темы

Что взять на заметку

• Для потока, который нельзя целиком держать в памяти, M наибольших значений удобно поддерживать в min-heap размера M: новый элемент заменяет вершину только если он больше текущего минимума.
• Такой алгоритм требует O(M) памяти и O(N log M) времени; выгрузка элементов из кучи даёт отсортированный результат.
• В PHP для этой задачи можно опираться на SPLMinHeap, а не реализовывать кучу вручную.
• При оценке решения важно отличать обычную стоимость операций с кучей от худшего случая расширения динамического массива: расширение линейно, но в среднем анализируют амортизированную стоимость.
• Для генерации выражения из AST нужно рекурсивно различать число, унарную операцию и операцию с несколькими операндами; первый элемент списка задаёт оператор.
• Минимальные скобки определяются сравнением приоритетов внешней и вложенной операций; при равном приоритете отдельно обрабатывают вычитание и непервый операнд.
• В PHP два минуса подряд перед числом могут быть прочитаны как декремент, поэтому для такого случая нужны скобки или иная безопасная форма записи.