World's most popular travel blog for travel bloggers.

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

, ,
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?

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.