O(1) stack operations.

Design a datastructure to implement a stack such that ALL of push(), pop() and getMax() functions work in O(1) time. You have infinite memory at your disposal.
Also note that function getMax() just returns the element with maximum value in the stack and NOT delete it from the stack like what pop() does.

Insight : compress the information using diff

PUSH :
if stack empty
push(elem)
push(elem)
else
min = pop()
push(elem-min)
push(min)

POP :
min = pop()
elem = pop()
if elem is -ve
   push(min-elem) // earlier min  
    return min
else
   push(min)
    return elem + min 

MIN :
min = pop()
push(min)
return min 

O(n+1) space and  constant operations for pop push min !! 

Continue

Inorder successor ?

This is one of the nasty ones, if you don’t fully understand what “Inorder successor” is. The inorder successor is the next value in an inorder traversal of a binary search tree. So how do you find the inorder successor for the node U ?

Algorithm : If node U has a right sub-tree, then the successor is the left most descendent of the right sub-tree. Otherwise, find the first ancestor that has node U in the left sub-tree.

Pseudocode :

if(node->right)
if( ! node->right->left)
return node->right;
else
{
tmp = node->right->left;
while(tmp->left)
tmp = tmp->left;
return tmp;
}

Continue