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.

Advertisements

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: