Monday, April 11, 2011

Design A DS That Support Insert, delete, Get Operation in O(1) e.g Consant Time

Design a Data Structure with following operations
1.Insert(X) -> insert X if X not present
2.Delete(X) -> delete X if X present
3.Get() -> return any element if it is present

all operations in O(1).
No memory constraint.

Init:

k=0

Insert X:

k = k+1 mod m;
A[X] = k;
B[k] = X;

Search X:

return (A[X] < m) and (B[A[X]] == X)

Delete X:

A[X] = 0;
B[k] = 0;
k = k-1;

2 comments :

S.A. said...

whats m in this?(Thanks for all ur help)

Ravindra said...

Wondering whats the use array B.

If the range of numbers is finite and its viable to have an array of that size then -

A[0-MAX] = 0;

insert X
A[X]++;

delete X
if (A[X] > 0)
A[X]--;

get X
return (A[X] > 0)