Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
class MinStack <T> {
public push(T val) {
m_data.push(val);
if (val > m_mins.top()) {
m_mins.push(m_mins.top());
} else {
m_mins.push(val);
}
}
public T pop() {
m_mins.pop();
return m_data.pop();
}
public T min() {
return m_mins.top();
}
private Stack<T> m_data;
private Stack<T> m_mins;
}
Answer is stack. Push and Pop is O(1). For find_min, you can maintain a seperate stack which stores the min element so far and you can pop the element from this stack if the element is popped from the main stack..
- arsragavan March 05, 2014