Кит Галли, автор канала о Data Science, провел тренировочное техническое интервью с Кайли Йинг на позицию инженера-программиста. В ходе встречи, длившейся более часа, участники воссоздали реальные условия собеседования в крупную технологическую компанию, разделив процесс на проектирование систем (OOP) и решение алгоритмической задачи на динамическое программирование.
🏗️ Объектно-ориентированное проектирование облачного ридера 1:26
Кит Галли предложил Кайли спроектировать архитектуру приложения для чтения коротких рассказов, аналогичного Amazon Kindle . Основные требования включали управление библиотекой книг, поддержку активного состояния книги, сохранение прогресса чтения и отображение текста постранично.
Для решения Кайли выделила две основные сущности:
- Класс Book: содержит метаданные (название), контент (текст по страницам) и состояние (последняя прочитанная страница).
- Класс Library: управляет коллекцией объектов Book и хранит идентификатор (ID) текущей активной книги.
В ходе обсуждения Кайли выбрала List[String] для хранения контента, где каждый элемент — это страница . Она аргументировала выбор списка тем, что он сохраняет порядок страниц и обеспечивает быстрый доступ по индексу, в отличие от множеств (Sets) или словарей (Dictionaries).
Для идентификации книг Кайли изначально хотела использовать названия, но Кит Галли указал на риск коллизий . В итоге было решено использовать уникальные ID, генерируемые счетчиком внутри библиотеки, что делает систему более устойчивой к дубликатам названий.
📏 Обработка изменения размера шрифта и многопользовательского доступа 24:40
Кит Галли усложнил задачу, предложив внедрить настройку размера шрифта. Кайли отметила, что в этом случае статическое разделение на страницы (хранение в списке) становится неэффективным, так как изменение шрифта меняет объем текста на экране .
Она предложила рефакторинг:
- Хранить контент как одну длинную строку.
- Рассчитывать количество символов на страницу (
characters_per_page) динамически на основе размера шрифта . - Использовать индексы среза строки для отображения нужного фрагмента текста.
При обсуждении масштабирования системы на несколько пользователей, Кайли предложила вынести общие данные книг в SQL-таблицы . По ее мнению, контент и заголовок должны быть общими, а личные настройки (прогресс чтения, шрифт) — храниться в отдельной таблице связей между пользователем и книгой.
🧠 Алгоритмическая задача: поиск плагиата через динамическое программирование 32:21
Вторая часть интервью была посвящена поиску самой длинной общей подпоследовательности (Longest Common Subsequence) в двух текстах для выявления плагиата. Кит Галли уточнил, что искомая последовательность не обязательно должна быть непрерывной, важен лишь порядок символов .
Кайли прошла через три этапа решения:
- Наивное решение: перебор всех возможных комбинаций подстрок, что было отброшено из-за экспоненциальной сложности .
- Двухуказательный подход: попытка итерироваться по обоим строкам и находить совпадения, что привело бы к сложности $O(N \cdot M)$ в лучшем случае, но не гарантировало бы оптимальности без рекурсии .
- Динамическое программирование: использование рекурсивной функции с мемоизацией .
В ходе реализации Кайли создала таблицу (двумерный массив) для хранения результатов подзадач, чтобы избежать повторных вычислений. Она определила базовые случаи: если символы под индексами $i$ и $j$ совпадают, результат равен $1 + \text{рекурсивный вызов для } (i+1, j+1)$; если нет — берется максимум от сдвига одного из указателей .
📊 Ретроспектива и обратная связь 56:35
Кит Галли оценил интервью как успешное, выделив привычку Кайли проговаривать мысли вслух . Однако он указал на области для роста:
- Декомпозиция: Кит Галли предложил выделить логику отображения в отдельный класс
Display, чтобы не перегружать классBookрасчетами интерфейса . - Наследование: для многопользовательской версии Кит Галли рекомендовал использовать подклассы, например
UserBook, который наследует метаданные базовой книги, но добавляет поля прогресса . - Самостоятельность в ДП: интервьюер отметил, что Кайли потребовалось больше подсказок для формулирования рекуррентного соотношения в задаче на динамическое программирование .
Кайли подчеркнула важность тестирования. Даже если время на кодинг ограничено, упоминание граничных случаев (пустые строки, отсутствие совпадений) и стратегии тестирования дает положительный сигнал нанимателю . Также участники обсудили тактику «письма после интервью»: Кит Галли считает, что присланное решение задачи, которую кандидат не успел дожать на встрече, может продемонстрировать лояльность и настойчивость .
