Какая алгоритмическая сложность операции группировки студентов по группе?

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

Умеете ли вы оценить реальный код: один проход с хэш-таблицей, стрим с groupingBy или вложенные циклы. Интервьюер хочет услышать O(n) и объяснение, от чего это зависит. Следом спрашивают, что изменится, если группы нужны отсортированными, или как посчитать только размеры групп.

Как отвечать

Обозначьте переменные: n студентов, k различных групп. Дальше по способам:

• HashMap и один проход: computeIfAbsent(s.group(), g -> new ArrayList<>()).add(s) на каждого студента. Вставка в хэш-таблицу и добавление в ArrayList амортизированно O(1), итого O(n) по времени и O(n) по памяти;
• Collectors.groupingBy(Student::group): та же сложность и тот же приём внутри. Тип карты и списков спецификация не гарантирует, на практике это HashMap и ArrayList;
• отсортированные группы: groupingBy(Student::group, TreeMap::new, Collectors.toList()). Каждая вставка в красно-чёрное дерево стоит O(log k), итого O(n log k);
• через сортировку: отсортировать по группе и разрезать на отрезки. Это O(n log n), имеет смысл, если данные уже отсортированы или нужен порядок внутри групп;
• наивно: для каждой группы пройти весь список, это O(n·k), а при группе на каждого студента уже квадрат.

Про худший случай HashMap скажите аккуратно: когда в корзине набирается больше восьми элементов и таблица не меньше 64 ячеек, корзина превращается в дерево. Для строковых ключей деградация ограничена O(log k) на операцию, а не O(k).

Если нужен только подсчёт, groupingBy(Student::group, Collectors.counting()) не хранит сами списки. А если данные лежат в базе, быстрее сделать GROUP BY там, чем тащить строки в память.

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

Используют Collectors.toMap(Student::group, s -> s). На первой же повторной группе он бросит IllegalStateException из-за дубля ключа.

Делают ключом свой класс Group без переопределённых equals и hashCode. Каждый экземпляр становится отдельной группой, и результат выглядит правдоподобно, но неверен.

Путают «в среднем O(n)» с гарантией на каждую операцию. Хэш-таблица периодически расширяется, и отдельная вставка при ресайзе стоит O(k), просто эта цена размазывается по всем вставкам.