Data structure that supports the following in O(1) time: initialization, insertion, deletion, finding an element, deleting all elements

Interview Question:

Propose a data structure that holds elements from 0 to n − 1 and supports all of the following operations in O(1) time: initialization, insertion of an element, deletion of an element, finding an element, deleting all elements.

A开发者_JS百科 hash table (assume there are no collisions i.e the best case) would support insertion and search in O(1). I am not sure about deletion though...any ideas?

Very interesting question!

Assuming memory allocation and dealloaction is O(1), then an O(1) is possible for all.

For this we use the trick by Hopcroft and Ullman which allows us to use arrays of size n, without having to spend Omega(n) time in actually initializing them.

See here: http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/

On insert, we just use the above array and set it to 1. On a search, if we find that the array element is not initialized, we return 0. On a delete, we set it to 0.

On a delete all, we free the datastructure and use a new one.

OK i think if the N is within rage you can just declare an array of N elements

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))

Hash Table can be O(1) for delete.

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

Edit: the code is a possible implementation of the data stored for the Hash Table.

I was looking for solution to the same question!

And I found a post where they achieved constant time complexity for insertion,deletion and search operations using hashing and maps. During insertion along with inserting element(key) store the index too as value of key.

You can see here:

https://www.geeksforgeeks.org/design-a-data-structure-that-supports-insert-delete-search-and-getrandom-in-constant-time/

https://www.geeksforgeeks.org/design-a-data-structure-that-supports-insert-delete-getrandom-in-o1-with-duplicates/

And also boolean array would do the same operations in O(1).