Data structure that supports the following in O(1)

问题:

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

回答1:

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.

回答2:

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

回答3:

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.