unknown Interview Question
Software DevelopersCountry: United States
Stack with an internal node that maintains a link (lets call it 'High') to the current highest value node in the stack.
Each time we push in a new node, we compare the new value to the 'High' in the top element. and we choose the higher value for the new node 'High'.
With this, we maintain the 'High' value in O(1) in push and in pop.
----
----
Push O(1)
Pop O(1)
PeekHigh O(1)
----
----
//schematic code, not full code
public class Stack<T> {
private class Node {
T value;
Node next;
Node high;
}
private Node top;
public void push(T value) {
top = new Node(value,top);
if (top.next != null && top.value.compareTo(top.next.value) < 0) {
top.high = top.next;
} else {
top.high = top;
}
}
public T peekHigh() {
return top.high.value;
}
}
Similar to Gils idea but each item on the stack records the max value at time it was added.
Push, Pop, Peek all O(1)
Space complexity is 2n
function StackEx() {
this.items = [];
}
StackEx.prototype.push = function (val) {
if (this.items.length === 0) {
this.items.push(new StackExItem(val, val))
} else {
var maxVal = Math.max(this.items[this.count() - 1].maxValue, val);
this.items.push(new StackExItem(val, maxVal));
}
}
StackEx.prototype.pop = function () {
return this.items.pop().value;
}
StackEx.prototype.peekHighest = function () {
return this.items[this.items.length - 1].maxValue;
}
StackEx.prototype.count = function () {
return this.items.length;
}
function StackExItem(val, maxValue) {
this.value = val;
this.maxValue = maxValue;
}
max stack (consist of:
- rrreeeyyy May 09, 2015stack1: regular stack
stack2: max stack
)
push(x){
stack1.push(x)
if (stack2.top<=x) stack2.push(x)
}
pop(){
stack1.pop
if (stack2.top==x) stack2.pop
}
all operations are O(1).