go_rob's blog

Tricky Problem
By go_rob, history, 8 years ago, In English

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.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it -10 Vote: I do not like it

It can be solved with Decart tree

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Uhm, one set<> for storing the given integers, another for storing their differences?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Can you Please briefly explain your approach?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 8   Vote: I like it -10 Vote: I do not like it

        Hmm... sorry, misread the question.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +24 Vote: I do not like it

          We have to design a data structure which supports Operations like Insertion and Deletion ...

          → Reply