Структура данных, которая поддерживает следующие за O (1) время: инициализация, вставка, удаление, поиск элемента, удаление всех элементов

Question

Интервью Вопрос:

Предложить структуру данных, которая содержит элементы от 0 до n - 1 и поддерживает все следующие операции за время O (1): инициализация, вставка элемента, удаление элемента, поиск элемента, удаление всех элементов.

Хеш-таблица (предположим, что нет коллизий, т.е. в лучшем случае) будет поддерживать вставку и поиск в O (1). Я не уверен насчет удаления, хотя ... есть идеи?

Answer 1

Очень интересный вопрос!

Предполагая, что выделение памяти и освобождение от операции - O (1), тогда O (1) возможен для всех.

Для этого мы используем трюк Хопкрофта и Уллмана, который позволяет нам использовать массивы размера n без необходимости тратить время Omega (n) на их фактическую инициализацию.

Смотрите здесь: http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/

При вставке мы просто используем указанный выше массив и устанавливаем его в 1. При поиске, если мы обнаруживаем, что элемент массива не инициализирован, мы возвращаем 0. При удалении мы устанавливаем его в 0.

При удалении всех мы освобождаем структуру данных и используем новую.

Answer 2

Хэш-таблица может быть O (1) для удаления.

List<Object> hashTableData = new ArrayList<Object>();

Редактировать: код является возможной реализацией данных, хранящихся для хэш-таблицы.

Answer 3

ОК, я думаю, что если N находится в пределах ярости, вы можете просто объявить массив из N элементов

0)Initialize
memset(A,0,sizeof(A))

1) Insert i
A[i] = 1

2) Remove i
A[i] = 0

3) Find i 
if( A[i] )

4) Delete All
memset(A,0,sizeof(A))