Здравствуйте, Grozo, Вы писали:

G>Здравствуйте, BulatZiganshin, Вы писали:

BZ>>Здравствуйте, Grozo, Вы писали:

G>>>Сами интервьюверы предлагали иногда (ну один раз) решение послабее оптимального, например в задачке о поиске одинаковых элементов в двух списках целых чисел без повторений предложили далеко не оптимальное решение с сортировкой и "мержем" обоих, дающее O(n log(n) + m log(m)) сложность, когда там есть O(n+m) решение.

BZ>>... требующее сколько памяти?

G>O( min(n, m) )

А какая структура данных с таким потреблением памяти обеспечит константное время доступа к элементам?
Если время будет неконстантным, то O(n+m) не получается.