# Разбор технического интервью Кайли Йинг: от проектирования ридера до поиска плагиата через ДП

Источник: https://www.youtube.com/watch?v=1qw5ITr3k9E
Канал: freeCodeCamp.org
Опубликовано: 29.03.2023

---

Кит Галли, автор канала о Data Science, провел тренировочное техническое интервью с Кайли Йинг на позицию инженера-программиста. В ходе встречи, длившейся более часа, участники воссоздали реальные условия собеседования в крупную технологическую компанию, разделив процесс на проектирование систем (OOP) и решение алгоритмической задачи на динамическое программирование.

## 🏗️ Объектно-ориентированное проектирование облачного ридера
[[JUMP:01:26]]

Кит Галли предложил Кайли спроектировать архитектуру приложения для чтения коротких рассказов, аналогичного Amazon Kindle [03:25]. Основные требования включали управление библиотекой книг, поддержку активного состояния книги, сохранение прогресса чтения и отображение текста постранично.

Для решения Кайли выделила две основные сущности:

*   **Класс Book**: содержит метаданные (название), контент (текст по страницам) и состояние (последняя прочитанная страница).
*   **Класс Library**: управляет коллекцией объектов Book и хранит идентификатор (ID) текущей активной книги.

В ходе обсуждения Кайли выбрала `List[String]` для хранения контента, где каждый элемент — это страница [09:15]. Она аргументировала выбор списка тем, что он сохраняет порядок страниц и обеспечивает быстрый доступ по индексу, в отличие от множеств (Sets) или словарей (Dictionaries).

Для идентификации книг Кайли изначально хотела использовать названия, но Кит Галли указал на риск коллизий [12:53]. В итоге было решено использовать уникальные ID, генерируемые счетчиком внутри библиотеки, что делает систему более устойчивой к дубликатам названий.

## 📏 Обработка изменения размера шрифта и многопользовательского доступа
[[JUMP:24:40]]

Кит Галли усложнил задачу, предложив внедрить настройку размера шрифта. Кайли отметила, что в этом случае статическое разделение на страницы (хранение в списке) становится неэффективным, так как изменение шрифта меняет объем текста на экране [25:34].

Она предложила рефакторинг:

1.  Хранить контент как одну длинную строку.
2.  Рассчитывать количество символов на страницу (`characters_per_page`) динамически на основе размера шрифта [26:28].
3.  Использовать индексы среза строки для отображения нужного фрагмента текста.

При обсуждении масштабирования системы на несколько пользователей, Кайли предложила вынести общие данные книг в SQL-таблицы [30:51]. По ее мнению, контент и заголовок должны быть общими, а личные настройки (прогресс чтения, шрифт) — храниться в отдельной таблице связей между пользователем и книгой.

## 🧠 Алгоритмическая задача: поиск плагиата через динамическое программирование
[[JUMP:32:21]]

Вторая часть интервью была посвящена поиску самой длинной общей подпоследовательности (Longest Common Subsequence) в двух текстах для выявления плагиата. Кит Галли уточнил, что искомая последовательность не обязательно должна быть непрерывной, важен лишь порядок символов [33:31].

Кайли прошла через три этапа решения:

1.  **Наивное решение**: перебор всех возможных комбинаций подстрок, что было отброшено из-за экспоненциальной сложности [35:47].
2.  **Двухуказательный подход**: попытка итерироваться по обоим строкам и находить совпадения, что привело бы к сложности $O(N \cdot M)$ в лучшем случае, но не гарантировало бы оптимальности без рекурсии [39:17].
3.  **Динамическое программирование**: использование рекурсивной функции с мемоизацией [50:38].

В ходе реализации Кайли создала таблицу (двумерный массив) для хранения результатов подзадач, чтобы избежать повторных вычислений. Она определила базовые случаи: если символы под индексами $i$ и $j$ совпадают, результат равен $1 + \text{рекурсивный вызов для } (i+1, j+1)$; если нет — берется максимум от сдвига одного из указателей [49:15].

## 📊 Ретроспектива и обратная связь
[[JUMP:56:35]]

Кит Галли оценил интервью как успешное, выделив привычку Кайли проговаривать мысли вслух [1:02:15]. Однако он указал на области для роста:

*   **Декомпозиция**: Кит Галли предложил выделить логику отображения в отдельный класс `Display`, чтобы не перегружать класс `Book` расчетами интерфейса [58:04].
*   **Наследование**: для многопользовательской версии Кит Галли рекомендовал использовать подклассы, например `UserBook`, который наследует метаданные базовой книги, но добавляет поля прогресса [1:01:25].
*   **Самостоятельность в ДП**: интервьюер отметил, что Кайли потребовалось больше подсказок для формулирования рекуррентного соотношения в задаче на динамическое программирование [1:03:58].

Кайли подчеркнула важность тестирования. Даже если время на кодинг ограничено, упоминание граничных случаев (пустые строки, отсутствие совпадений) и стратегии тестирования дает положительный сигнал нанимателю [1:08:23]. Также участники обсудили тактику «письма после интервью»: Кит Галли считает, что присланное решение задачи, которую кандидат не успел дожать на встрече, может продемонстрировать лояльность и настойчивость [1:10:36].