Data design Issue to find insertion deletion and getMin in O(1)

Question

As said in the title i need to define a datastructure that takes only O(1) time for insertion deletion and getMIn time.... NO SPACE CONSTRAINTS.....

I have searched SO for the same and all i have found is for insertion and deletion in O(1) time.... even a stack does. i saw previous post in stack overflow all they say is hashing...

with my analysis for getMIn in O(1) time we can use heap datastructure
for insertion and deletion in O(1) time we have stack...

so inorder to achieve my goal i think i need to tweak around heapdatastructure and stack... How will i add hashing technique to this situation ...

if i use hashtable then what should my hash function look like how to analize the situation in terms of hashing... any good references will be appreciated ...

Answer 1

This is a design problem, which means they want to see how quickly you can augment existing data-structures.

start with what you know:

• O(1) update, i.e. insertion/deletion, is screaming hashtable
• O(1) getMin is screaming hashtable too, but this time ordered.

Here, I am presenting one way of doing it. You may find something else that you prefer.

• create a HashMap, call it main, where to store all the elements
• create a LinkedHashMap (java has one), call it mins where to track the minimum values.
• the first time you insert an element into main, add it to mins as well.
• for every subsequent insert, if the new value is less than what's at the head of your mins map, add it to the map with something equivalent to addToHead.
• when you remove an element from main, also remove it from mins. 2*O(1) = O(1)
• Notice that getMin is simply peeking without deleting. So just peek at the head of mins.

EDIT:

Amortized algorithm:

(thanks to @Andrew Tomazos - Fathomling, let's have some more fun!)

We all know that the cost of insertion into a hashtable is O(1). But in fact, if you have ever built a hash table you know that you must keep doubling the size of the table to avoid overflow. Each time you double the size of a table with n elements, you must re-insert the elements and then add the new element. By this analysis it would seem that worst-case cost of adding an element to a hashtable is O(n). So why do we say it's O(1)? because not all the elements take worst-case! Indeed, only the elements where doubling occurs takes worst-case. Therefore, inserting n elements takes n+summation(2^i where i=0 to lg(n-1)) which gives n+2n = O(n) so that O(n)/n = O(1) !!!

Why not apply the same principle to the linkedHashMap? You have to reload all the elements anyway! So, each time you are doubling main, put all the elements in main in mins as well, and sort them in mins. Then for all other cases proceed as above (bullets steps).

Answer 2

in your problem statement " insertion and deletion in O(1) time we have stack..." so I am assuming deletion = pop() in that case, use another stack to track min

algo: Stack 1 -- normal stack; Stack 2 -- min stack

Insertion

push to stack 1. if stack 2 is empty or new item < stack2.peek(), push to stack 2 as well

objective: at any point of time stack2.peek() should give you min O(1)

Deletion

pop() from stack 1. if popped element equals stack2.peek(), pop() from stack 2 as well

Answer 3

If you go with your initial assumption that insertion and deletion are O(1) complexity (if you only want to insert into the top and delete/pop from the top then a stack works fine) then in order to have getMin return the minimum value in constant time you would need to store the min somehow. If you just had a member variable keep track of the min then what would happen if it was deleted off the stack? You would need the next minimum, or the minimum relative to what's left in the stack. To do this you could have your elements in a stack contain what it believes to be the minimum. The stack is represented in code by a linked list, so the struct of a node in the linked list would look something like this:

struct Node
{
  int value;
  int min;
  Node *next;
}

If you look at an example list: 7->3->1->5->2. Let's look at how this would be built. First you push in the value 2 (to an empty stack), this is the min because it's the first number, keep track of it and add it to the node when you construct it: {2, 2}. Then you push the 5 onto the stack, 5>2 so the min is the same push {5,2}, now you have {5,2}->{2,2}. Then you push 1 in, 1<2 so the new min is 1, push {1, 1}, now it's {1,1}->{5,2}->{2,2} etc. By the end you have:

{7,1}->{3,1}->{1,1}->{5,2}->{2,2}

In this implementation, if you popped off 7, 3, and 1 your new min would be 2 as it should be. And all of your operations is still in constant time because you just added a comparison and another value to the node. (You could use something like C++'s peek() or just use a pointer to the head of the list to take a look at the top of the stack and grab the min there, it'll give you the min of the stack in constant time).

A tradeoff in this implementation is that you'd have an extra integer in your nodes, and if you only have one or two mins in a very large list it is a waste of memory. If this is the case then you could keep track of the mins in a separate stack and just compare the value of the node that you're deleting to the top of this list and remove it from both lists if it matches. It's more things to keep track of so it really depends on the situation.

DISCLAIMER: This is my first post in this forum so I'm sorry if it's a bit convoluted or wordy. I'm also not saying that this is "one true answer" but it is the one that I think is the simplest and conforms to the requirements of the question. There are always tradeoffs and depending on the situation different approaches are required.

Answer 4

Strictly speaking your problem as stated is provably impossible, however consider the following:

Given a type T place an enumeration on all possible elements of that type such that value i is less than value j iff T(i) < T(j). (ie number all possible values of type T in order)

Create an array of that size.

Make the elements of the array:

struct PT
{
   T t;
   PT* next_higher;
   PT* prev_lower;
}

Insert and delete elements into the array maintaining double linked list (in order of index, and hence sorted order) storage

This will give you constant getMin and delete.

For insertition you need to find the next element in the array in constant time, so I would use a type of radix search.

If the size of the array is 2^x then maintain x "skip" arrays where element j of array i points to the nearest element of the main array to index (j << i).

This will then always require a fixed x number of lookups to update and search so this will give constant time insertion.

This uses exponential space, but this is allowed by the requirements of the question.

Answer 5

You can use a trie. A trie has O(L) complexity for both insertion, deletion, and getmin, where L is the length of the string (or whatever) you're looking for. It is of constant complexity with respect to n (number of elements).

It requires a huge amount of memory, though. As they emphasized "no space constraints", they were probably thinking of a trie. :D

Answer 6

A hashtable gives you insertion and deletion in O(1) (a stack does not because you can't have holes in a stack). But you can't have getMin in O(1) too, because ordering your elements can't be faster than O(n*Log(n)) (it is a theorem) which means O(Log(n)) for each element.

You can keep a pointer to the min to have getMin in O(1). This pointer can be updated easily for an insertion but not for the deletion of the min. But depending on how often you use deletion it can be a good idea.