You will be given a stream of integers to process, We have to design a data structure which supports Operations like Insertion and Deletion and should work in O(log(n)) time.
And Also we have to find the (MIN GAP) minimum absolute difference between any two integers processed before in O(1) i.e constant time.
We have to design a data structure that supports the above operations.
For Eg. If we have the data 2, 5, 7, 8, Here min gap is 1 (8-7).
But After deletion of 8, the data becomes — 2, 5, 7 and now the Min gap is 2 (7-5) .
And After deletion of 5, the data becomes 2, 7 and now Min Gap is 5.
Note For deletion will be given a key as a parameter, We have to find that key value if present and delete it.
It can be solved with Decart tree
sorry, mistake
Uhm, one set<> for storing the given integers, another for storing their differences?
Can you Please briefly explain your approach?
I already did :D
Store the integers given to you in one set S, use another (multi)set D for storing differences between adjacent elements in S. If you're given a new integer a, find the nearest smaller and larger integer in S (m and M), remove M - m from D, insert M - a and a - m to D. If you should delete a instead, remove M - a, a - m from D and insert M - m. Fidning the min. gap is just taking the smallest element from D. If you can have identical integers on the input, the simplest modification is to make S a map for counting occurrences of each input integer and do nothing to D if you're adding/removing an integer with more than 1 occurrence after/before the given operation.
Maybe I'm misunderstanding the problem, but that's really simple.
Hmm... sorry, misread the question.
We have to design a data structure which supports Operations like Insertion and Deletion ...