CODEWITHSUNDEEP
data-structureslanguage-agnosticbig-ocomplexity-theory
user7
user7

Reputation: 2389

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

Upvotes: 2

Views: 7858

Answers (4)

user13116294
user13116294

Reputation:

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

Upvotes: 0

user127.0.0.1
user127.0.0.1

Reputation: 1337

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.

Upvotes: 7

DwB
DwB

Reputation: 38300

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.

Upvotes: 1

FUD
FUD

Reputation: 5184

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

Upvotes: 1

Related Questions