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.

Pages: 1 2

4 Responses to “A Common Interview Question”

  1. Vivek said

    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.

  2. programmingpraxis said

    @vivek: This doesn’t work. There is no way to delete an arbitrary element from all three stacks in constant time.

  3. Scott said

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: