Можно ли получить квадратичную сложность при использовании Set для проверки уникальности?

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

Умеете ли вы считать сложность по тому, что реально выполняется, а не по названию структуры. Ответ «нет, у множества это константа» закрывает тему в минус: константа у хеш-таблицы держится не всегда.

Как отвечать

Да, и как минимум тремя способами.

Первый: плохой hashCode. Константа в среднем случае предполагает равномерное распределение. Если метод возвращает одно значение или различает слишком мало вариантов, элементы оседают в одной корзине, каждая проверка становится линейной, и n вставок дают квадрат. В современных версиях длинная цепочка в корзине перестраивается в дерево, что снижает худший случай одной операции до логарифма, но только если ключи сравнимы между собой.

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

Set<String> seen = new HashSet<>();
for (String s : items) {
    if (!seen.add(s)) return false; // add сам вернёт false на дубликате
}

Третий: дорогие equals и hashCode. Для длинных строк или вложенных коллекций каждая операция стоит линейно от размера ключа, и эта цена умножается на число элементов.

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

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

Второе: считают хеш по полю с малым числом значений, например по статусу или флагу. Формально метод корректен и согласован с равенством, а на практике корзин получается три штуки на миллион записей.

Третье: меняют поле, участвующее в хеше, уже после вставки. Элемент остаётся в старой корзине, проверка наличия возвращает ложь, штатно удалить его нельзя, и множество потихоньку растёт дубликатами.