0
$\begingroup$

This is an interview question. I need to implement a data structure that supports the following operations:

  1. Insertion of an integer in $O(1)$

  2. Deletion of an integer (for example, if we call delete(7), then 7 is deleted from the data structure, if the integer 7 exists in it) in $O(1)$.

  3. Return maximum integer in the data structure (without deleting it) in $O(1)$.

You can also use up to $O(n)$ space.

I thought of something similar to this question, but here we have $O(\mathrm{log}\ n)$.

Do you know how can we implement these operations in $O(1)$?

Edit: forgot important thing - you can assume the numbers that will be inserted are integers in the range $[0,n]$.

$\endgroup$
  • $\begingroup$ (Retrun?) (the purpose here proposition?) Is this to be a set or a multiset / bag (insert 7 twice, delete it once: still in)? $\endgroup$ – greybeard Oct 1 '18 at 22:17
  • $\begingroup$ @greybeard, it's a multi-set. Nothing to return in the insertion and deletion, only at the maximum operation. $\endgroup$ – John Oct 2 '18 at 14:31
5
$\begingroup$

Suppose we have such data structure. We can find in $O(1)$ the max, delete the max in $O(1)$ and repeat it $n$ times. Hence, we can sort $n$ numbers in $O(n)$. Therefore, constructing such data structure must take $\Omega(n\log(n))$ (like sorting, in general, can't be done better than $n\log(n)$. Hence, you might have some constraint on data). Also, as deleting is in $O(1)$, means it must be found. Hence, Searching and Finding is in $O(1)$.

Therefore, you must know the position of each value (something like counting sort, but with this constraint that $max <= n$ to take the $O(n)$ space!). Hence, you can act like a counting sort by saving the max value in a variable besides the array, by accepting some constraint on data (not in general).

$\endgroup$
  • $\begingroup$ Thanks, indeed I forgot an assumption about the integers and edited the post. However, I still don't find a way to implement the operations as needed. Can you elaborate more on how you can do this with something that is similar to counting sort (thought of counting array, but it doesn't help by itself)? $\endgroup$ – John Oct 2 '18 at 14:26
  • $\begingroup$ @John my pleasure. By the new assumption, it's exactly the same as counting sort plus a variable to store max and update after each inserition. read more counting sort on Wikipedia. $\endgroup$ – OmG Oct 2 '18 at 14:41
  • $\begingroup$ how do you update the maximum when you delete an element from the data structure? in this case I see only wallking backward in the counting array till I find a number with is not zero (and that isn't O(1) ) $\endgroup$ – John Oct 2 '18 at 14:48
  • $\begingroup$ @John you don't need this. As I've said, you've stored the max in constructing time, in a variable. When you delete a number, just check with the value of maximum in that varible and do the proper act in $O(1)$, $\endgroup$ – OmG Oct 2 '18 at 14:57
  • 2
    $\begingroup$ @OmG, I agree with smart28 - don't see it as well. Can you please describe in your post a pseudo code of how you implement these operations in O(1)? $\endgroup$ – John Oct 3 '18 at 12:01
0
$\begingroup$

You can implement first 2 ops easily by creating an array from 0 to max and store counts of added/removed items there. Regarding the maximum....

I think the question is just little tricky. Since max is constant, you can iterate whole array and it would be also in O(1).

$\endgroup$
  • $\begingroup$ How can you iterate the whole array in O(1)? $\endgroup$ – John Oct 11 '18 at 11:55
  • $\begingroup$ "you can assume the numbers that will be inserted are integers in the range [0, N]" - N is constant, no matter how many items are inserted. Just think how it would work if N=1. Clear? $\endgroup$ – smrt28 Oct 11 '18 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.