we have to think of all possible DS that can do some of the operation in desired complexity then we can come up with some combinations of Data structure so that we can get what question is asking for :)
So its clear O(1) lookup implies a hashed data structure.
By comparison:
* O(1) insert/delete with O(N) lookup implies a linked list.
* O(1) insert, O(N) delete, and O(N) lookup implies an array-backed list
* O(logN) insert/delete/lookup implies a tree(BST) or heap.
we basically need to find out some kind of combinations from above DS .
First I thought About Doubly Linked List instead of Array but soon realized that we won't get desired complexity isn't it ? even we can achieve some of operation in O(1) but how u will make sure all will be done in O(1) ??
so lets Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.
here can be possible way to achieve the desired time complexity
1. insert(value): append the value to array and let i be it's index in A. Set H[value]=i.
2. remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.
3. contains(value): return H.contains(value) no doubt in this :)
4. getRandomElement(): let r=random(current size of A). return A[r].
e.g. index=random()%size of current array will generate index in range & then we can return element at given index . this will make sure that this function will generate the random number from present elements of data structure only.
Time Complexity Will be O(1)
Space Complexity O(N) , N is size of hashtable
So its clear O(1) lookup implies a hashed data structure.
By comparison:
* O(1) insert/delete with O(N) lookup implies a linked list.
* O(1) insert, O(N) delete, and O(N) lookup implies an array-backed list
* O(logN) insert/delete/lookup implies a tree(BST) or heap.
we basically need to find out some kind of combinations from above DS .
First I thought About Doubly Linked List instead of Array but soon realized that we won't get desired complexity isn't it ? even we can achieve some of operation in O(1) but how u will make sure all will be done in O(1) ??
so lets Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.
here can be possible way to achieve the desired time complexity
1. insert(value): append the value to array and let i be it's index in A. Set H[value]=i.
2. remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.
3. contains(value): return H.contains(value) no doubt in this :)
4. getRandomElement(): let r=random(current size of A). return A[r].
e.g. index=random()%size of current array will generate index in range & then we can return element at given index . this will make sure that this function will generate the random number from present elements of data structure only.
Time Complexity Will be O(1)
Space Complexity O(N) , N is size of hashtable
No comments :
Post a Comment