Golang собеседования для тех, кто хочет научиться решать алгоритмы

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

Показано публичное тренировочное Go-собеседование: кандидату предлагают спроектировать LRU-кэш с методами Put и Get при ограниченной ёмкости. Собеседующий разбирает, почему поиск самого давно использованного элемента перебором даёт O(n), и подводит к сочетанию map для быстрого поиска и двусвязного списка для поддержания порядка использования. Затем участники пытаются описать контракты и поля реализации на Go, а в конце собеседующий даёт развёрнутую обратную связь о сильных сторонах и пробелах кандидата.

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

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

• Для LRU-кэша нужно явно держать инвариант: в начале списка находится самый недавно использованный элемент, в конце — самый давно использованный.
• Get должен находить узел по ключу через map, возвращать значение и переносить найденный узел в начало списка.
• При заполненном кэше Put должен удалить хвост списка как LRU-элемент, удалить его ключ из map и добавить новый узел в начало.
• Связка map «ключ → узел списка» и двусвязный список позволяет выполнять поиск, удаление известного узла и перенос в начало без линейного обхода.
• Нужно уметь отличать поля структуры от контрактов интерфейса и записывать корректные сигнатуры методов Go, включая возвращаемое значение Get.
• Для подготовки полезно отдельно практиковать двусвязные списки, базовую задачу LRU и написание кода без привычной IDE; это рекомендации собеседующего по итогам разбора.