Как проходить литкод. Пост на основе опыта мок собеседований с ребятами.

Структура правильного прохождения литкод собеседования примерно такая:
1. Внимательно читаем условие. Обсуждаем с интервьюером, убеждаемся, что правильно поняли задание.
2. Задаем интервьюеру вопросы. Проясняем все ограничения. Может ли на входе быть пустой массив и все такое прочее.
3. Пишем тест кейсы. Буквально assert func(input) == output на все входы, которые можете придумать. Во-первых, это позволяет понять, какие ситуации надо обрабатывать. Во-вторых, в некоторых компаниях пишет кандидат тесты или нет это критерий оценки.
4. Не пишем код пока интервьюер не сказал: "хорошо, давай приступим к коду"! Худшее, что можно сделать, это броситься писать первое пришедшее в голову решение, а потом застрять в середине: "Ой, эм, блин, не сработало."
5. Устно предлагаем решение и обсуждаем его с интервьюером. Обсуждаем сложность по скорости и по памяти в терминах O(n) нотации. Получаем добро писать код. Просим подсказки, если необходимо.
6. Спокойно пишем код. Особенно внимательно обрабатываем базовые кейсы. Частая глупая ошибка это забыть базовый кейс в рекурсивном решении или нечто подобное.
7. Проверяем свой код после написания! Запускаем интерпретатор Python 3.10 у себя в голове и исполняем код для всех написанных ранее тест кейсов. У вас гарантированно найдутся ошибки. Часто забывают поставить какой-нибудь return, но бывает получается отловить и ошибку в логике.

Важное:
* Лучше брутфорс решение, чем никакого. Если придумали брутфорс решение и знаете, что оно не оптимально, то можно заработать немного очков указав место, где надо оптимизировать: "мы считаем вот эту штуку дважды, можно как-то лучше, но нет времени придумать как, кажется какое-нибудь дерево помогло бы".
* Вы должны узнавать все типичные классы задач (хеш таблицы, сортировка, поиск, деревья, графы, связанные списки, кучи, динамическое программирование, возможно что-то еще забыл) и уметь написать для них брутфорс решение. Минимальная подготовка: заходим на Leetcode, выбираем Easy задачи и решаем одну на каждую тему.
* Главное рассуждать. В небольших компаниях можно пройти собеседование даже решив задачу брутфорсом, если убедительно показать, что вы системно рассуждаете. В больших компаниях не решил == не прошел, а если решил брутфорсом == грейд джуна.

Оптимизация цен на товары: прогноз спроса

Фундаментальная задача везде, но вокруг неё так много мифов! Давайте начнём разбираться с базы

Q = Q(P) - спрос в штуках, зависит от цены
P - цена
C - издержки на 1 штуку товара

Базово задача - максимизировать прибыль:
Q(P) * (P - C) --> max

И самое сложное - смоделировать зависимость Q(P)

Экономисты предполагают, что спрос складывается из многих таких выборов между продавцами, товарами и тд. Поэтому
Важна не абсолютная цена (79 руб), а относительная (Р/ P_competitor = +2% к цене конкурента, P / P_analogue = -5% к цене товара-аналога, P/ P_yesterday = +3% к вчерашней цене этого же товара)

Поэтому функция спроса на товары
Q = f(P/ P_competitor, P / P_analogue, ...)

Вообще, теоретически, на этом можно остановиться и применять наш любимый ML для прогноза Q с фичами на относительные цены. Но в реальности все сложнее 😅

Об этом - в следующих постах

Как проходить ML system design.

Если литкод собеседование устроено по очень строгим и понятным правилам, то system design сложнее. Здесь главное показать, что вы можете разложить проблему на составляющие и наметить решение.

Как правило вам задают открытый вопрос вида: "Как бы вы сделали систему прогнозирования спроса в супермаркете?" От вас не ждут, что вы эксперт в прогнозировании спроса, хотя если у вас есть релевантные знания это плюс. Просто представьте, что вы уже на работе и вам задают такой вопрос.

Главная ошибка, которую здесь совершают: пытаются натянуть свой прошлый опыт на проблему и закапываются в детали. Надо спрогнозировать спрос, а человек начинает рассказывать, как он бы тюнил градиентный бустинг. Это собеседование не про ваш опыт, а про совместное решение кейса.

Моя личная структура решения таких кейсов:
* В-о-п-р-о-с-ы. Первым делом надо было задавать как можно больше вопросов. Какие есть данные? Сколько данных? Какое качество модели нас устроит? Какое время на предсказания? Какие ошибки для нас страшнее: false positive или false negative?
* Обозначить план работ. Не надо сразу закапываться в какие-то детали. Как правило порядок примерно такой: изучение проблемы -> сбор данных -> бейзлайн -> деплой -> A/B тест -> следующая итерация с более умным решением.
* Придумываем откуда взять данные. Например, если мы в кейсе делаем блок рекомендаций на сайте, то запускаем блок со случайными рекомендациями, смотрим на что кликают и получаем шумные лейблы. Потом делаем умнее: показываем в блоке половину популярных товаров и половину случайных.
* Изучаем данные. Обозначаем интервьюеру, что мы ищем. На этом этапе интервьюер даст еще дополнительных вводных, связанных с доменной информацией. Например, насколько в спросе на типичные товары много сезонности? Можем ли мы отделить покупки товаров со скидками от покупок товаров без скидок, чтобы это не вносило шум в датасет?
* Делаем глупое бейзлайн решение. Помню байку, что Avito нужно было сделать алгоритм, который выберет лучшее фото для объявления. Никто не смог побить бейзлайн "выбрать самое квадратное фото."
* Деплоим глупое решение, запускаем A/B тест, придумываем, как оценивать было улучшение или нет. На этом этапе мы отрабатываем весь пайплайн, чтобы потом встраивать в него более хорошие решения. Здесь можно уже говорить про архитектуру: будем делать предсказания в батч режиме (периодической крон джобой) или онлайн?
* Переходим к ML. Здесь надо первым делом сформулировать задачу в терминах оптимизации. Что на входе, что на выходе. Это классификация, регрессия, ранжирование или что-то еще? Что мы будем минимизировать/максимизировать?
* Выбираем оффлайн метрики для оценки моделей. Например, задачу ранжирования можно свести к классификации. Но выбирать F1 score не стоит, потому что эта метрика не учитывает положение примера в выдаче. Метрика должна быть тем больше, чем выше релевантный элемент и ниже нерелевантный. Например MAP@R. Но знать ее не обязательно, важнее обозначить ее необходимость интервьюеру.
* Описываем как будем принимать решение, достаточно ли новая модель хороша, чтобы ее деплоить. Здесь чаще всего разговор про кросс-валидацию и про то, как связаны наши ML метрики с бизнесовыми.
* Делаем первую простейшую ML модель. Не сложнее логистической регрессии. Деплоим.
* Делаем модель посложнее и итерируемся.
(UPD: как сказали в комментариях, очень хорошая идея поговорить про мониторинг, дообучение и в целом поддержку решения)

Не претендую на универсальность этого подхода, но я пока не получил ни одного отказа после System Design собеседования, так что такая структура явно лучше, чем ничего.