1
$\begingroup$

Design a data structure for holding numbers in two sets:

Init - initiate the DS with two empty sets. O(1)

Insert(a,S) - insert number a to set S (S could be X or Y). O(log(n)). (n is the total number of numbers in the DS)

Find - find a number a in the DS such that the number of numbers in X that are smaller than a equals the number of numbers in Y that are bigger than a, if exists such number. O(1)


My attempt is using 2 augmented balanced binary search trees, each one presents set X or Y, insert into it the new number and saving in each node information for finding what is the number of numbers in X that are smaller than this node and the number of numbers on Y that are bigger than that node.

But given that information how could I implement the Find procedure in O(1)? Or maybe someone have better design (preferably using augmented BST)?

$\endgroup$
1
$\begingroup$

Since it's your exercise, I don't want to prevent you from finding the solution on your own, but I'll give you some possible hints:

Big hint:

You can do some work during the Insert operation to make any subsequent Find run fast.

Think about that one for a while.


If you're still stuck, here are some more specific hints. I recommend you think about each one for 15 minutes or more before moving on to the next one.

Hint #2:

Suppose you wanted to implement an operation InsertAndFind(a,S), that effectively does Insert(a,S) followed by Find(). Could you make that run in O(log n) time?

Hint #3:

It would also be possible to have a single data structure (e.g., a single augmented balanced binary search tree), with some information in each node.

Hint #4:

What information would you want to keep in a node, to determine whether that node is something that could be returned in response to a future Find query?

$\endgroup$
  • $\begingroup$ In each node I can save number of numbers in X that are smaller than this node and the number of numbers on Y that are bigger than that node. But how can I find which nodes have this two numbers equal in O(logn)? And I can I update it? $\endgroup$ – po1son May 24 '17 at 6:12
  • $\begingroup$ @po1son, Good! You're making excellent progress. You're on the right track -- you're close. And those are good questions. Now go back through all of the hints. At least one of the hints addresses the two questions in your comment (arguably, two of the hints). Keep at it! $\endgroup$ – D.W. May 24 '17 at 16:33
  • $\begingroup$ I don't see it. $\endgroup$ – po1son May 24 '17 at 16:49
  • $\begingroup$ @po1son, keep trying. It's OK to augment the data structure even further. If after a few more hours of brainstorming you still can't solve it, you can edit the question to show how far you got and what approaches you considered and why you rejected them. $\endgroup$ – D.W. May 24 '17 at 16:53
  • $\begingroup$ in each node x keep a pointer to a node in its subtree (rooted at x) that has the required property? $\endgroup$ – po1son May 24 '17 at 16:56

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.