Interview Question
Java DevelopersCountry: United States
Interview Type: Written Test
class SuperStack{
public:
stack<int> st;
unordered_map<int,int> inc_hm;
int cur_inc;
void push(int v){
st.push(v);
cur_inc = 0;
print_top();
}
void pop(){
if(inc_hm.find(st.size())!=inc_hm.end()) {
cur_inc = inc_hm[st.size()];
if(st.size()-1) inc_hm[st.size()-1] += inc_hm[st.size()];
inc_hm.erase(st.size());
}
st.pop();
print_top();
}
int inc(int h,int v){
if(h > st.size()) h = st.size();
inc_hm[h] += v;
print_top();
}
void print_top(){
if(!st.empty()) cout<<st.top() + inc_hm[st.size()]<<endl;
else cout<<"EMPTY"<<endl;
}
};
class SuperStack{
public:
stack<int> st;
unordered_map<int,int> inc_hm;
int cur_inc;
void push(int v){
st.push(v);
cur_inc = 0;
print_top();
}
void pop(){
if(inc_hm.find(st.size())!=inc_hm.end()) {
cur_inc = inc_hm[st.size()];
if(st.size()-1) inc_hm[st.size()-1] += inc_hm[st.size()];
inc_hm.erase(st.size());
}
st.pop();
print_top();
}
int inc(int h,int v){
if(h > st.size()) h = st.size();
inc_hm[h] += v;
print_top();
}
void print_top(){
if(!st.empty()) cout<<st.top() + inc_hm[st.size()]<<endl;
else cout<<"EMPTY"<<endl;
}
};
A vector (in C++) or an ArrayList (in Java) can be used to implement such a Stack, where push operations append to the end of the vector (e.g. with push_back), pop operations remove from the end (e.g. with pop_back) and inc operations perform updates starting from the 0 index (start of the vector)
Just a Linked list should be fine to handle all these cases. Also, have a variable size to execute the include x y test case. pop() and push in O(1). and include operation in O(n) time.
- Anonymous June 14, 2018