Uber Interview Question
Senior Software Development EngineersCountry: India
Interview Type: Phone Interview
There are three primary methods
1) add
2) delete
3) peekMinDifference
I would first ask which operation would get called the most. That gives us an idea for what we should optimize for. For example if peek gets called rarely then we can simply make add and delete O(1) operation and make peek nlogn with simple sort and adjacent dif check.
Another option is to use min heap. That would make add/delete constant and peek logn operation but building that in interview might not be as easy as option A.
Use BST to keep integers in sorted format.
- krbchd August 16, 2017And use a stack to keep min difference also a metadata regarding which nodes contribute to it.
When you add a node in BST.
Check, its in order successor and predecessor to compute min diffs and if it is less the current top of stack , update the stack.
When you delete a node in BST, delete it . And keep popping the stack until the top of stack does not utilize the said node (maximum two pops)
Complexity->
Add -> logN
Get Min - O(1)
Delete -> log N