• 2

Country: India

Comment hidden because of low score. Click to expand.
2
of 4 vote

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).
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

My answer is messy, but you can drop insertion to O(k); there's no need to keep the full sort.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

Can you explain how you are planning to keep the array sorted in O(n) time?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

"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 :)

Comment hidden because of low score. Click to expand.
0

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...

Comment hidden because of low score. Click to expand.
0

@deepanshu: this solution wouldn't work as the search is 0(n) but according to question it should be 0(1)

Comment hidden because of low score. Click to expand.
0

You can preserve delete constant it you keep stack of those arrays. In addition, if element of this stack correspond to original stack, the duplicates concerns will be addressed.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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).

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

I think in the first part we actually need 2 variable (max, secondMax) to track the maximum.
The second part is exactly solution from the book with an additional stack. You can query for kth element of the stack to get kth max.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>>(){{
}});
}});
}});
}};

//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){
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;
List<TopKNode<T>> topK;

public KStack(int k){
count = 0;
topKCount = 0;
this.k = k;
topK = new ArrayList<TopKNode<T>>();
}

public void push(T t){
count++;
KStackNode<T> newNode = new KStackNode<T>(t);

if(topK.size() == 0){
topKCount++;
return;
}

for(int i = topK.size() - 1; i >= 0; i--){
if(t.compareTo(topK.get(i).getT()) == 0){
topKCount++;
break;
}

else if(t.compareTo(topK.get(i).getT()) < 0){
if(i != k - 1){
topKCount += 1;
if(topK.size() > k){
topKCount -= topK.get(k).getCount();
topK.remove(k);
}
}
break;
}

if(i == 0){
topKCount++;
if(topK.size() > k){
topKCount -= topK.get(k).getCount();
topK.remove(k);
}
}
}
}

public T pop(){
return null;
}

count--;
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);
}
else{
topKCount--;
}
break;
}
else if(comp == 0){
topKCount--;
if(topK.get(i).remove()){
topK.remove(i);
}
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){
}
top -= topK.get(i).getCount();
}

return null;
}

if(topKCount < count){
T max = null;
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++;
}
}

@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";
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;
}

num += 1;
}

public int getCount(){
return num;
}

//Returns true if reduced to 0.
boolean remove(){
return --num == 0;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

HOMEWORK!?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.