A Common Interview Question
September 13, 2016
It’s a trick question, and a naughty one for someone who doesn’t already know the answer.
There is no such data structure. There can’t be, in a general sense, because if there was, you could perform a series of insertions in O(1), then a series of find min in O(1), each accompanied by a delete min in O(1), and thereby sort an array in O(n), which is impossible.
Even though there is no general solution to the problem, it is possible in some restrictive cases to provide that data structure. For instance, if the problem domain permits only positive integers less than a hundred, you can use a data structure based on bucket sort to provide those operations in O(1). But that’s far from a general solution.
I suppose such a question might be amusing for a sadistic interviewer with an unwitting subject, but I don’t think I would want to work for him.
Programming Praxis 
:(
This problem can be solved by having 3 stacks – min, max and normal to keep the values. Whenever insert(push) is performed, after pushing the value in to normal stack, also validate the input value and push it in to either min or max stacks.
@vivek: This doesn’t work. There is no way to delete an arbitrary element from all three stacks in constant time.
Is this a trick question? Constant time deletion implies constant time search right? And if you want to search for something efficiently, you have to maintain order somewhere, which means you have to do work (presumably upon insertion) to keep elements ordered/sorted. It seems that these constraints are mutually exclusive. And if there was such a data structure that could satisfy them, wouldn’t it be extremely well known and taught in data structure courses? That being said, I would love for someone to prove me wrong.