Google Interview Question
Country: India
My answer is messy, but you can drop insertion to O(k); there's no need to keep the full sort.
I guess k will be provided at run time. So the user can ask any maximum and for that we have to keep the full array sorted. But yeah, for constant k, your solution looks right.
As I have mentioned that the insertion and deletion(push & pop) complexity will be O(n). So whenever a new element is pushed just insert the same element in the array also in sorted order(search for the position to insert and then shift the rest of the elements by one position), which will take O(n), and whenever an element is popped just delete is from the array also, which will also take O(n).
If you run into array size being small issues just use the dynamic growing array approach which will also not increase the complexity.
"If you run into array size being small issues just use the dynamic growing array approach which will also not increase the complexity."
Actually, this solution also has limitation of size. (What if you have millions of entries? You can't have an array of the same size, right?). So, its better to implement both the array and the stack using doubly linked list. Parallelly, keep track of the number of elements currently inserted, by using a count variable.
If count >=k then store the kth node in some temp variable.("as soon as you insert the kth node the above statement evaluates to true and hence temp=last node. O(1)" ).Now accessing kth max would be an O(1) operation.
Coming to insertion, if you insert an element whose position <= k then shift the temp to its previous node else continue.( O(n) )
Deletion, if you delete an element whose position < k then shift temp to its next node else continue.( O(n) ).
Correct me if I am wrong. Thanks :)
Harsha,
Your solution works only when k is constant. But, as far as I understand "k" will be passed at run time. And for that we have to use a sorted array to access the kth maximum element in O(1). Also, the amortized time for inserting into the dynamically growing the array is also O(1). Hope this helps...
@deepanshu: this solution wouldn't work as the search is 0(n) but according to question it should be 0(1)
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)
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;
}
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).
- deepanshu November 09, 2014