Cheap and Secure Web Hosting Provider : See Now

Implement opposite() method to tell if there are two opposite numbers, (x,-x)

, , No Comments
Problem Detail: 

Let a dictionary with the operations insert(), delete() and search(). Each one of them has time complexity of $O(logn)$. Implement (efficiently) opposite() operation which return true if there are two opposite numbers in the dictionary (i.e. $5$ and $(-5)$)

I advised to use another data structure.

I thought about a binary search tree. We maintain a binary search tree and for every insert() we also insert the item into the tree.

What do you think?

Asked By : AlonAlon
Answered By : Yuval Filmus

Here is what they intended you to do. You keep a counter of the number of opposite elements, which starts at zero. When inserting an element $x$, you insert both the true element $x$ and the dummy element $-x$; if $-x$ was already there, then you increase your counter of opposite elements. Similarly, when deleting $x$ you delete both $x$ and $-x$, and possibly decrease the counter.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33432

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback