Какие вопросы задают на собеседовании в HFLabs (backend, middle)?

Question

Маяк · Accepted Answer

1. Задача на лайвкодинг: дан массив статистики по дням (для каждого дня — список пользователей с количеством шагов). Найти «чемпионов» — пользователей, которые участвовали во всех днях соревнования и набрали максимальное суммарное количество шагов; вернуть структуру результата со списком их id и количеством шагов (чемпионов может быть несколько).
2. Как думаешь, что можно улучшить/оптимизировать в твоём решении первой задачи?
3. У тебя два цикла по одной и той же мапе — два раза пробегаешь по одним и тем же данным. Можно ли сделать это в одном цикле (схлопнуть последние три цикла в один, проверяя оба условия чемпионства за одну операцию)?
4. Оцени своё решение первой задачи по асимптотической сложности (big O) по времени.
5. Оцени решение первой задачи по дополнительной памяти (входные данные не считаем): какие дополнительные структуры заводишь и сколько памяти они занимают?
6. Задача на лайвкодинг: на рынке размещено множество товаров, каждый представлен числом; у каждого покупателя есть потребность, тоже выраженная числом. Если точного товара нет, покупатель берёт ближайший по значению, что вызывает неудовлетворённость, равную разнице между желаемым и полученным. Количество каждого товара не ограничено. Рассчитать суммарную неудовлетворённость всех покупателей.
7. Как хочешь искать тот товар, который покупатель будет покупать (ближайший по значению)?
8. Решение рабочее, но тяжёлое: как его можно оптимизировать, если покупателей мало, а товаров миллионы (полный перебор будет очень долгим)?
9. А как именно сортировка поможет в данном случае? Если товары идут от 1 до 100 млн, а нужно найти 99-миллионный — всё равно придётся пробежаться почти по всему массиву?
10. Можешь рассказать, как работает бинарный поиск (в теории)?
11. Не хочешь попробовать написать бинарный поиск (реализовать его в коде)?
12. Оцени текущее решение второй задачи (полный перебор) по сложности.
13. Назови три алгоритма сортировки и расскажи, какая у них сложность в среднем (и в худшем) случае.