2

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?

Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
user7
  • 2,339
  • 5
  • 25
  • 29

4 Answers4

7

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.

user127.0.0.1
  • 1,337
  • 10
  • 18
  • How the search operation will be O(1) when we don't know which index the search value is residing? – cyber_raj Oct 03 '11 at 12:51
  • @cyber_raj: The array is just like any other array, except we know in O(1) time, if we are accessing an uninitialized element and in that case, we can return the default initialization value. I suggest you read point 1 in the section "Solution" in the above blog link. – user127.0.0.1 Oct 03 '11 at 16:05
  • What if at the very start, when from[] and to[] are uninitialized, they contain garbage data that fulfills the requirements necessary to assert that vec[i] has been set? It's a rare edge case, but isn't it technically possible? – John Kurlak Jul 27 '13 at 05:28
  • @JohnKurlak: You also maintain a count of how many you have set, so that count will be zero. – user127.0.0.1 Sep 10 '13 at 17:57
  • @user127.0.0.1 I'm just updating that an improved algorithm was found - it does the whole chaining (from[i]==j && to[j]==i) in-place, and doesn't need the two array allocations. It only uses 1 extra bit of memory, besides the array. I wrote about it [here](https://medium.com/p/2ab4c0335e8b). – Tom Dec 08 '20 at 14:23
1

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))
FUD
  • 5,114
  • 7
  • 39
  • 61
1

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.

DwB
  • 37,124
  • 11
  • 56
  • 82
  • I am not a Java programmer, so speaking generically a hash table is usually an array of pointers to linked lists coupled with a really good hashing function...so to delete all the elements from a hash table, one would have to first free each linked list...isn't this an O(n) operation – user7 Oct 02 '11 at 17:59
  • Note that you included "assume that there are no collisions". It depends on how it is implemented. If you have an array of stuff and use a hash function to get the index of the stuff you want and the hash function is not creating duplicates then you don't need the linked lists, just the array. – DwB Oct 02 '11 at 18:03
  • I guess you are right. Insertion, removal, and lookup should take expected O(1) time, provided that the hash function is sufficiently "random". But is initialization and deleting all elements O(1) even if there are no collisions? – user7 Oct 03 '11 at 15:12
0

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

Dharman
  • 30,962
  • 25
  • 85
  • 135