Моковое собеседование по алгоритмам на Go | Владимир Балун, Яндекс

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

Это тренировочное собеседование по алгоритмам на Go для Junior-позиции, в котором кандидат проектирует LRU-кэш с методами Put и Get. После разбора принципа вытеснения кандидат с подсказками приходит к связке map и двусвязного списка: map даёт быстрый поиск узла, а список хранит порядок недавнего использования. В кодовой части обсуждаются контракты интерфейса, поля кэша, лимит ёмкости и особенности синтаксиса Go; в конце интервьюер даёт развёрнутую обратную связь.

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

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

• В LRU-кэше при переполнении удаляется элемент, к которому дольше всего не обращались; обращение через Get должно перемещать найденный элемент в позицию самого свежего.
• Для операций близких к O(1) нужен map из ключа в узел списка и двусвязный список: начало хранит самый свежий элемент, конец — кандидат на вытеснение.
• При удалении хвоста списка необходимо также удалить соответствующий ключ из map, иначе структуры рассинхронизируются.
• При проектировании Put и Get сначала стоит проговорить инварианты, поля кэша, сигнатуры и операции над списком, а уже затем писать реализацию.
• По обратной связи интервьюера, полезно отдельно повторить LRU, связные списки и синтаксис Go: различие struct и interface, receiver методов и возвращаемые значения Get.
• Интервьюер советует не ограничивать поиск решения только встроенными структурами Go: нужную структуру данных можно спроектировать или использовать как абстракцию.