CareerCup

You can use a stack and an array which holds elements in sorted order. The only problem is the insertion and deletion complexity will be O(n), but finding maximum or kth maximum will always be O(1).

public class Stack{
int[] elements;
int top;
int[] sortedElements;

public void push(int ele){
//here just have to insert in the array "sortedElement" also. which will take O(n).
}
public int pop(int ele){
//here just have to delete from the array "sortedElement" also. which will take O(n).
}
}

Use 2 stacks one for normal push and pop(call it as main_stack) , and other for finding the max(call this as max_stack) of the earlier created stack.
Suppose you are pushing the data onto the main_stack , check if the top of the stack is greater or lesser than the new element that you are trying to insert. If the new element is greater then push the element on the max_stack , or pop the top element of the max_stack , push the new element into the stack and push the poped element. Thus max element is always at the top of the stack.

Now normal push and pop operation can be done on main stack where as finding the max can be done on max_stack(if we pop the element from the max_stack we will get the max element and now if we do pop for the 2nd time from the max_stack the 2nd max can be found out).

The first part is straight from Crack the Coding Interview book. The idea is to maintain 2 more stacks to record the info about the min and max in the stack before pushing an element. Here is an implementation with a few test cases:

#include <iostream>
#include <stack>
#define val first
#define id second
using namespace std;
template<class T>
class MinMaxStack{
	int id;
	stack<pair<T,int> > val_s , min_s , max_s;
public:
	MinMaxStack():id(1){}
	void push(T obj){
		++id;
		pair<T,int> x = make_pair(obj , id);
		val_s.push(x);
		
		if(min_s.empty() || obj<min_s.top().val){
			min_s.push(x);
		}
		
		if(max_s.empty() || obj>max_s.top().val){
			max_s.push(x);
		}
	}
	T top(){
		return val_s.top().val;
	}
	T max(){
		return max_s.top().val;
	}
	T min(){
		return min_s.top().val;
	}
	void pop(){
		pair<T,int> x = val_s.top();
		val_s.pop();
		
		if(x.id==max_s.top().id){
			max_s.pop();
		}
		
		if(x.id==min_s.top().id){
			return min_s.pop();
		}
	}
};
int main() {
	MinMaxStack<int> s;
	
	s.push(1);
	cout<<s.top()<<" "<<s.max()<<" "<<s.min()<<endl;
	
	s.push(4);
	cout<<s.top()<<" "<<s.max()<<" "<<s.min()<<endl;
	
	s.push(2);
	cout<<s.top()<<" "<<s.max()<<" "<<s.min()<<endl;
	
	s.push(3);
	cout<<s.top()<<" "<<s.max()<<" "<<s.min()<<endl;
	
	s.push(10);
	cout<<s.top()<<" "<<s.max()<<" "<<s.min()<<endl;
	
	s.pop();
	cout<<s.top()<<" "<<s.max()<<" "<<s.min()<<endl;
	
	s.pop();
	cout<<s.top()<<" "<<s.max()<<" "<<s.min()<<endl;
	
	s.pop();
	cout<<s.top()<<" "<<s.max()<<" "<<s.min()<<endl;
	
	s.pop();
	cout<<s.top()<<" "<<s.max()<<" "<<s.min()<<endl;
	return 0;
}

The second part though is unclear about k. Is it a constant? or is it a variable provided with the query. If it is a constant then satisfying the query in O(1) time is possible using BST (set in STL). push and pop become O(logn). Here is an implementation

#include <iostream>
#include <stack>
#include <set>
using namespace std;
template <class T>
class KMedianStack{
	stack<T> val_s;
	multiset<T> prev , next;
	int k;
public:
	KMedianStack(int x):k(x){}
	void push(T obj){
		val_s.push(obj);
		if(prev.size()<k){
			prev.insert(obj);
			return;
		}
		if(obj>*(prev.rbegin())){
			next.insert(obj);
		}else{
			next.insert(*(prev.rbegin()));
			prev.erase(prev.find( *(prev.rbegin()) ));
			prev.insert(obj);
		}
	}
	T top(){
		return val_s.top();
	}
	T get_kth(){
		return *prev.rbegin();
	}
	void pop(){
		T obj = val_s.top();
		val_s.pop();
		
		if(prev.size()<k){
			prev.erase(prev.find(obj));
			return;
		}
		if(obj>*(prev.rbegin())){
			next.erase(next.find(obj));
		}else{
			prev.insert(*(next.begin()));
			next.erase(next.begin());
			prev.erase(prev.find(obj));
		}
	}
};
int main() {
	KMedianStack<int> s(2);
	s.push(3);
	s.push(2);
	
	cout<<s.top()<<" "<<s.get_kth()<<endl;
	
	s.push(6);
	cout<<s.top()<<" "<<s.get_kth()<<endl;
	
	s.push(1);
	cout<<s.top()<<" "<<s.get_kth()<<endl;
	
	s.pop();
	cout<<s.top()<<" "<<s.get_kth()<<endl;
	
	s.pop();
	cout<<s.top()<<" "<<s.get_kth()<<endl;
	
	return 0;
}

If however, k is given as a variable with the query, I cannot really think of a way to satisfy the query in O(1) time. However , doing that in O(k) time is possible by using BST (set in STL). Here is an implementation:

#include <iostream>
#include <stack>
#include <set>
using namespace std;
template<class T>
class MedianStack{
	int id;
	stack<T> val_s;
	multiset<T> order;
public:
	MedianStack():id(1){}
	void push(T obj){
		val_s.push(obj);
		order.insert(obj);
	}
	T top(){
		return val_s.top();	
	}
	void pop(){
		order.erase(order.find(val_s.top()));
		val_s.pop();
	}
	T get_kth(int k){
		typename multiset<T>::iterator it = order.begin();
		for(int i=0;i<k-1;++i){
			++it;
		}
		return *it;
	}
};
int main() {
	MedianStack<int> s;
	
	s.push(3);
	cout<<s.top()<<" "<<s.get_kth(1)<<endl;
	
	s.push(1);
	cout<<s.top()<<" "<<s.get_kth(1)<<" "<<s.get_kth(2)<<endl;
	
	s.push(4);
	cout<<s.top()<<" "<<s.get_kth(1)<<" "<<s.get_kth(2)<<" "<<s.get_kth(3)<<endl;
	
	s.pop();
	cout<<s.top()<<" "<<s.get_kth(1)<<" "<<s.get_kth(2)<<endl;
	
	s.pop();
	cout<<s.top()<<" "<<s.get_kth(1)<<endl;
	
	return 0;
}

Instead of storing elements in stack, you can store objects in the stack with the structure below. Any time you insert you need to compare with the element on top in stack (peep) with the inserted values and fill the object with max value. this will allow O(1) time. you do the same for kth max but then stack is not right data-structure to use because of the requirement.

customdata{
int data;
int[] max; --> store max, second max until K in order
}

So, getTop([1 .. k)] is order k; this is constant if you fix k = 1, 2, etc.
Push (O(k)).
Pop(O(k + n)) - you hit the n on replacement.

There are a hundred optimizations that you could make to this; among them, I think you could get the getTop() to a true constant (not dependent on k) by maintaining a hashmap from index to node in the topK data structure.

However, this problem escalated for me; I'm so finished with it. ; )

Works, but messy; real interview, I would try cleaning up some more. I wasn't going to publish here, but seeing that there are no other code answers, I feel obliged to provide my input.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class Main{
	
	static final private Random rand = new Random();
	
	public static void main(String[] args){
		
		int k = 3;
		
		Set<List<Integer>> testCases = new HashSet<List<Integer>>(){{
			add(new ArrayList<Integer>(){{
				add(1);
				add(2);
				add(3);
				add(4);
			}});
			add(new ArrayList<Integer>(){{
				add(1);
				add(2);
				add(2);
				add(2);
				add(0);
				add(3);
				add(4);
				add(-3);
				add(-2);
				add(1);
				add(4);
				add(0);
				add(0);
				add(-1);
				add(-1);
				add(-1);
				add(-1);
				add(-1);
				add(-1);
				add(-1);
			}});
			add(new ArrayList<Integer>(){{
				add(-1);
				add(-5);
				add(3);
				add(4);
			}});
		}};
		
		//TODO: pop
		int index = 0;
		for(List<Integer> testCase : testCases){
			System.out.println("Running test case: " + ++index);
			KStack<Integer> stack = new KStack<Integer>(k);
			for(int i : testCase){
				if(i >= 0){
				System.out.println("Adding " + i);
					stack.push(i);
				}
				else{
					System.out.println("Popping");
					stack.pop();
				}
				System.out.println(stack);
				int kIndex = rand.nextInt(k) + 1;
				System.out.println("top " + kIndex + ": " + stack.getTop(kIndex) + "\n"); 
			}
		}
		 
		
		
	}
	
	public static class KStack<T extends Comparable<T>>{
		int k;
		int count;
		int topKCount;
		KStackNode<T> head;
		List<TopKNode<T>> topK;
		
		public KStack(int k){
			count = 0;
			topKCount = 0;
			this.k = k;
			this.head = null;
			topK = new ArrayList<TopKNode<T>>();
		}
		
		public void push(T t){
			count++;
			KStackNode<T> newNode = new KStackNode<T>(t);
			newNode.setChild(head);
			this.head = newNode;
			
			if(topK.size() == 0){
				topKCount++;
				topK.add(new TopKNode(t));
				return;
			}
			
			for(int i = topK.size() - 1; i >= 0; i--){
				if(t.compareTo(topK.get(i).getT()) == 0){
					topK.get(i).add();
					topKCount++;
					break;
				}
				
				else if(t.compareTo(topK.get(i).getT()) < 0){
					if(i != k - 1){
						topK.add(i + 1, new TopKNode<T>(t));
						topKCount += 1;
						if(topK.size() > k){
							topKCount -= topK.get(k).getCount();
							topK.remove(k);
						}
					}
					break;
				}
				
				if(i == 0){
					topK.add(0, new TopKNode<T>(t));
					topKCount++;
					if(topK.size() > k){
						topKCount -= topK.get(k).getCount();
						topK.remove(k);
					}
				}
			}
		}
		
		public T pop(){
			if(head == null){
				return null;
			}
			
			count--;
			KStackNode top = head;
			head = head.getChild();
			T val = (T) top.getT();
			
			for(int i = topK.size() - 1; i >= 0; i--){
				int comp = val.compareTo(topK.get(i).getT());
				if(comp < 0){
					if(i == topK.size() - 1){
						break;
					}
					else if(topK.get(i + 1).remove()){
						topK.remove(i + 1);
						addToTopK();
					}
					else{
						topKCount--;
					}
					break;
				}
				else if(comp == 0){
					topKCount--;
					if(topK.get(i).remove()){
						topK.remove(i);
						addToTopK();
					}
					break;
				}
			}
			
			return val;
		}
		
		public T getTop(int top){
			if(top > k || top < 1 || top > count){
				return null;
			}
			for(int i = 0; i < topK.size(); i++){
				if(topK.get(i).getCount() >= top){
					return topK.get(i).getT();
				}
				top -= topK.get(i).getCount();
			}
			
			return null;
		}
		
		private void addToTopK(){		
			if(topKCount < count){
				T max = null;
				KStackNode node = head;
				T minInTop = topK.get(topK.size() - 1).getT();
				while(node != null){
					if(((T)node.getT()).compareTo(minInTop) < 0 &&(max == null || ((T) node.getT()).compareTo(max) > 0)){
						max = (T) node.getT();
					}
					node = node.getChild();
				}
				topKCount++;
				topK.add(new TopKNode<T>(max));
			}
		}
		
		@Override
		public String toString(){
			return printTopK() + printData() + "\nInTopK: " + topKCount + " / " + count;
		}
		
		private String printTopK(){
			String ret = "\n";
			for(TopKNode<T> n : topK){
				ret += "(" + n.getT() + " , " + n.getCount() + ") ";
			}
			
			return ret;
		}
		
		private String printData(){
			String ret = "\n";
			KStackNode cur = head;
			while(cur != null){
				ret += cur.getT() + " ";
				cur = cur.getChild();
			}
			
			return ret;
		}
	}
	
	public static class KStackNode<T>{
		T t;
		KStackNode child;
		
		KStackNode(T t){
			this.t = t;
			child = null;
		}
		
		public T getT(){
			return t;
		}
		
		public KStackNode getChild(){
			return child;
		}
		
		public void setChild(KStackNode child){
			this.child = child;
		}
	}
	
	private static class TopKNode<T>{
		int num;
		T t;
		
		public TopKNode(T t){
			this.t = t;
			this.num = 1;
		}
		
		public T getT(){
			return t;
		}
		
		public void add(){
			num += 1;
		}
		
		public int getCount(){
			return num;
		}
		
		//Returns true if reduced to 0.
		boolean remove(){
			return --num == 0;
		}
	}
}

I am mentioning 3 possible ways for having max() and secondMax() to be fetched in O(1) time. First 2 are non scalable to kth Max, but push and pop are better than the 3rd but scalable solution.

1) Save max and secondMax in each node. So create the node as follows:
struct Node {
int data;
int max,
int secondMax;
}
Struct Stack {
Node *top;
void push(int data);
int pop();
bool isEmpty() const {return top == NULL;}
int max(); // this is peek operation
int secondMax(); // this is peek operation
in peek(); // peek the top most data
}

a). Initially, the stack is empty. No max, no secondMax
b). When first element is inserted, the max element is the data itself. There is no secondMax element.
c). When an element is pushed, write following code:
int maxItem = max(), secondMaxItem = secondMax();
if(currItem > maxItem) { secondMaxItem = maxItem; maxItem = currItem; }
else if(currItem > secondMaxItem) secondMaxItem = currItem;
Node *newNode = new Node(currItem, maxItem, secondMaxItem);
newNode->next = top;
top = newNode;
}

The disadvantage is that the space requirement is 3 times. And it is not scalable to kth Max.

2) Another non scalable solution is to have an auxiliary stack:

So push will be as follows:
void push(int currItem) {
node *newNode = node(currITem);
if(stack.empty()) {
top = newNode;
auxStack.push(currItem);
}
else {
if(currItem > auxStack.peek())
auxStack.push(currItem);
newNode->next = top;
top = newNode;
}
else {
std::pair<int, int> top2Items = auxStack.peek2Items();
int secondMax = top2Items.second;
if(currItem > secondMax)
{ int max = auxStack.pop();
auxStack.push(currItem);
auxStack.push(max);
}
}

In this second case, the space requirement is just 2N where N is the size of stack at any given point of time.

3) A scalable solution is to have a dynamic array (i.e. vector) in the stack, which will save items in order. Push will take at the most O(n) for insertion sort. Pop will also take O(n) in worst case to remove the nth element in the dynamic array.

We can also think of a max heap, but push and pop could take O(log n) time to heapify. This solution is applicable to getting max and second max. As the max will be root and secondMax will be one of its children. Also kthMax() is slightly more than O(1) (will have to check k-1 levels)

We can sort the stack using mergesort in O(nlogn) in decreasing order.After sorting the:
max = stack[0]
secmax = stack[1]

and for kth max element : kthmax = stack[k-1]
all these are in O(1) time.

HOMEWORK!?

public class Stack extends Stack<Integer> {
Stack<Integer> maxStack = new Stack<Integer>;

void push(int n){
if(maxStack.peek() < n){
maxStack.push(n);
}
super.push(n);
}

int pop(){
int value = super.pop();
if(maxStack.peek() == value){
maxStack.pop();
}
return value;
}
}

In my oppnion, using a vector to hold the sorted elements may be a good solution. When the amount of elements is too big to put in a vector, I think this will be another quetion. Here is my implementation. I am new to careercup and hope to discuss with all of you. Thanks so much.

#include <cstdio>
#include <stack>
#include <vector>
#include <iostream>
using namespace std;

typedef pair<int, int> pii;
typedef vector<int>::iterator vit;
vector<int> sorted_ele;

vit binary_search(vit begin, vit end, int ele){
    int len = end - begin;
    while(len>0){
        int half = len>>1;
        vit mid = begin+half;
        if(*mid<ele){
            begin = mid+1;
            len -= half+1;
        }else{
            len = half;
        }
    }
    return begin;
}

void insert(int ele, int len){
    int pos = binary_search(sorted_ele.begin(), sorted_ele.end()-1, ele)-sorted_ele.begin();
    for(int i=len;i>pos;--i){
        sorted_ele[i] = sorted_ele[i-1];
    }
    sorted_ele[pos] = ele;
}

void push(stack<int> &s, int ele){
    s.push(ele);
    sorted_ele.resize(sorted_ele.size()+1);
    insert(ele, sorted_ele.size()-1);
}

void pop(stack<int> &s){
    if(s.empty())   return;
    int x = s.top();
    s.pop();
    vit pos = binary_search(sorted_ele.begin(), sorted_ele.end(), x);
    sorted_ele.erase(pos);
}


/*state:
0:success;
1:index<=0;
2:index exceed the amount of elements
*/
pii get(int i){
    if(i<=0) return pii(1, -1);
    else if(i>sorted_ele.size())    return pii(2, -1);
    int len = sorted_ele.size();
    return pii(0, sorted_ele[len-i]);
}

int main(){
     stack<int> s;
     for(int i=0;i<10;++i)  push(s, i);
     pii p = get(5);
     printf("state: %d\tres: %d\n", p.first, p.second);
     for(int i=0;i<5;++i)   pop(s);
     p = get(10);
     printf("state: %d\tres: %d\n", p.first, p.second);
     p = get(3);
     printf("state: %d\tres: %d\n", p.first, p.second);
     p = get(0);
     printf("state: %d\tres: %d\n", p.first, p.second);
}

C++ solution for max and second max part

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;
struct ValueAndIndex {
    int value;
    size_t index;
    ValueAndIndex(int v, size_t i):value(v),index(i){}
};

class MyStack {
public:
    void pop();
    int top();
    MyStack& push(int i);
    int max();
    int secondMax();
    MyStack() {
        maxS.push({INT32_MIN, 0});
        secondS.push({INT32_MIN, 0});
    }
private:
    stack<int> mainS;
    stack<ValueAndIndex> maxS;
    stack<ValueAndIndex> secondS;
};
MyStack& MyStack::push(int i) {
    ValueAndIndex max = maxS.top();
    if(max.value < i) {
        maxS.pop();
        secondS.push(max);
        maxS.push({i, mainS.size()});
    } else {
        auto sMax = secondS.top();
        if(i > sMax.value) {
            secondS.push({i, mainS.size()});
        }
    }
    mainS.push(i);
    return *this;
}
void MyStack::pop() {
    mainS.pop();
    ValueAndIndex max = maxS.top();
    if(max.index == mainS.size()) {
        maxS.pop();
        auto second = secondS.top();
        secondS.pop();
        maxS.push(second);
    } else {
        auto second = secondS.top();
        if(second.index == mainS.size()) {
            secondS.pop();
        }
    }
}
int MyStack::top() {
    return mainS.top();
}
int MyStack::max() {
    return maxS.top().value;
}

int MyStack::secondMax() {
    return secondS.top().value;
}
int main(int argc, const char * argv[])
{
    MyStack s;
    s.push(-3).push(4).push(5).push(1).push(8);
    s.pop();s.pop();
    s.push(-3).push(4).push(5);
    cout << "Max = " << s.max() << "; Second max = " << s.secondMax() << endl;
    return 0;
}