A Common Interview Question
September 13, 2016
I’ve seen this question two or three times recently on message boards that provide interview questions, so I guess we ought to add it to our collection:
Create and implement a data structure that provides
- insert
- delete
- find min
- find max
- delete min
- delete max
all in O(1) time, regardless of the type of the underlying data.
Your task is to create and implement that data structure. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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.