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

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

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

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

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

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

G>>O( min(n, m) )

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

Если Вы внимательно перечитаете условие, то увидите, что обычный HashSet<T> и его аналоги дадут константное время.