Как классифицировать выдачу нового или старого идентификатора

Что проверяют

Умеете ли вы уточнить короткую формулировку и выбрать простое решение. Обычно имеется в виду поток событий или таблица, где для каждой записи нужно пометить: идентификатор встречается впервые или уже появлялся раньше. Следом спрашивают, что делать, если идентификаторов сотни миллионов и в память они не помещаются.

Как отвечать

Проговорите, что это детерминированная задача, а не задача для модели. Правило «видели раньше или нет» вычисляется точно, и логистическая регрессия тут только добавит ошибок.

Дальше варианты по масштабу:

• множество в памяти: проходите по событиям в порядке времени, is_new = id not in seen, затем seen.add(id). Проверка в среднем O(1), весь проход O(n);
• pandas: отсортировать по времени и взять ~df.duplicated("user_id"), первая встреча получит True. То же даёт df.groupby("user_id").cumcount() == 0;
• SQL или Spark: ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY ts) = 1, либо сравнение ts с MIN(ts) в том же окне;
• монотонные идентификаторы: если ID выдаются автоинкрементом, новый это тот, что больше максимума, виденного до сих пор. Память O(1);
• фильтр Блума: для огромных потоков. Ложноотрицательных ответов нет, зато бывают ложноположительные: новый ID изредка примут за старый. Долю ошибок задаёте размером фильтра.

Если флаг пойдёт в признаки модели, скажите про утечку: «новый» считается только по прошлому относительно момента события, иначе при обучении признак будет знать будущее.

Где спотыкаются

Сразу строят пайплайн с One-Hot Encoding и Random Forest. Интервьюер ждёт вопроса «что считается старым?» и множества, а не классификатора.

Забывают про порядок. Без сортировки по времени duplicated пометит первой случайную запись, и разметка получится неверной.

Держат сотни миллионов ID в питоновском set. Каждый элемент там отдельный объект с накладными расходами, и память кончается гораздо раньше, чем кажется. На таком объёме нужен фильтр Блума, внешнее хранилище или уникальный индекс в базе.