Here's beginner question that can end up being surprisingly deep. It seems extremely simple, but I couldn't get the bonus on my own, so I'm doing an obnoxiously thorough case study:
Implement a stack, with push
, pop
, and getMax
methods. push
should push a single item to the top of the stack and return the length of the stack. pop
should remove the last item of the stack and return the removed item. getMax
should return the highest value out of the numbers stored on the stack.
Bonus: getMax should compute in O(1) time.
So, the stack itself is fairly easy. I'll avoid using arrays and native array methods, so that I at least have to build it myself.
Here's what the constructor itself might look like:
function Stack(){
this.storage = {},
this.length = 0
}
Pretty straightforward, right? We've got 0 items in our stack, so our length is 0 and our storage has nothing in it.
We want to be able to store stuff in our stack, so let's add a push
method to our Stack()
constructor's prototype. We expect our push
to store a single item at the top of our stack. This means two things:
- we'll be taking a single argument
- we need to keep track of the order our items are in
We can basically steal ideas from arrays as a strategy for keeping our items in the correct order. We'll create key/value pairs on our storage
object that correspond with the index that they would have if it were an array.
Luckily, we'll know that the next item on our stack will exist at the index of our length
. This is to say, when we have a length of 0 (0 items in the storage), the next item we'll add will be the '0th' index item. When we've got one item in the storage, our length will be 1, and our next item will be an item at index 1.
So, our strategy is to take the length of the array, use it as a key in our storage
and store the value of the item we're pushing. After that, we'll increment our length
value to keep it up to date with our storage. Finally, we'll return our length
, just to keep it up to spec.
Our file will look like this:
function Stack(){
this.storage = {},
this.length = 0
}
Stack.prototype.push = function(item){
this.storage[this.length] = item;
this.length = this.length + 1;
return this.length;
}
Next, we'll add the pop
method. This will simply delete the top item from our object, update our length
to stay accurate, and return the item that we deleted.
So here's how we're gonna do that:
- decrement our
length
by 1 - save the value of storage at
length
to a separate variable, since it'll be the last item in our storage - delete that item from our storage (we saved it to a separate variable)
- return the saved item using our saved variable
And here it is:
function Stack(){
this.storage = {},
this.length = 0
}
Stack.prototype.push = function(item){
this.storage[this.length] = item;
this.length = this.length + 1;
return this.length;
}
Stack.prototype.pop = function(){
this.length = this.length - 1;
const output = this.storage[this.length]; //our stored value
delete this.storage[this.length];
return output;
}
Finally, the real work, which is our getMax
function. There's an obvious way to do it, which would just mean taking the values from our storage
and invoking Math.max() on them.
function Stack(){
this.storage = {},
this.length = 0
}
Stack.prototype.push = function(item){
this.storage[this.length] = item;
this.length = this.length + 1;
return this.length;
}
Stack.prototype.pop = function(){
this.length = this.length - 1;
const output = this.storage[this.length]; //our stored value
delete this.storage[this.length];
return output;
}
Stack.prototype.getMax = function(){
return Math.max(Object.values(this.store));
}
This is a decent solution to grabbing a max
value, but it's not perfect by any means. It operates in O(n) time, since Math.max()
needs to look at all of the values in our stack before it can definitively know what the highest number is.
All of the fun starts in part 2, where we'll actually finesse our getMax
to operate in the holy grail of time complexities, O(1) time.
Top comments (0)