1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.