Как оптимизировать работу с коллекциями для линейной сложности

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

Умеете ли вы заменить квадратичный алгоритм линейным подбором структуры данных. Это самая частая практическая оптимизация в прикладном коде.

Как отвечать

Основной приём: заменить поиск в списке на поиск по хешу.

// квадратично: contains по списку внутри цикла
for (Order o : orders) if (blockedIds.contains(o.userId())) ...   // список

// линейно: тот же код, но множество
Set<Long> blocked = new HashSet<>(blockedIds);
for (Order o : orders) if (blocked.contains(o.userId())) ...

Другие типовые случаи:

• соединение двух списков по ключу: вместо вложенных циклов построить Map из одного списка за один проход и пройти по второму. Было произведение размеров, стало сумма;
• группировка: Collectors.groupingBy вместо ручного перебора с поиском группы;
• подсчёт вхождений: Map<K, Integer> с merge или Collectors.counting;
• проверка дубликатов: добавление в множество с проверкой результата вместо повторного поиска;
• доступ по индексу: ArrayList вместо LinkedList, потому что у связного списка это линейная операция, и цикл с get(i) превращается в квадратичный.

Полезно назвать и цену: множество и карта требуют корректных equals и hashCode, тратят память под служебные структуры, а порядок в HashSet не сохраняется. Если порядок нужен, берут LinkedHashSet или LinkedHashMap.

И оговорку про размер: на десяти элементах список быстрее множества за счёт локальности данных, поэтому оптимизация имеет смысл там, где объёмы реально велики.

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

Оставляют contains по списку внутри цикла и получают квадратичное время на десятках тысяч элементов.

Кладут в множество объекты без корректных equals и hashCode и получают дубликаты или потерянные элементы.

Считают LinkedList быстрым на вставку, забывая, что позицию сначала надо найти проходом.