Interview Question: Max Stack
Vložit
- čas přidán 13. 09. 2024
- Coding interview question from www.byte-by-byt....
In this video, I show how to create a stack that with push(), pop(), and max() functions.
Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We've helped thousands of students improve their interviewing and we can help you too.
Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com
Need an interview coach? Send in an application: www.byte-by-byte.com/coaching
You can also find me on
Twitter: / bytebybyteblog
Facebook: / bytebybyteblog
Email: sam@byte-by-byte.com
Dude, the quality of these videos are in SANE.
good job dude!
thank yoU!!
Awesome approach till now i used 2nd stack to keep hold of max operation.
Dont you think your 2nd stack approach is better, as you are using limited space. Here if u have a billion elements, then that much space is being wasted in this approach?
Instead of storing pointer to oldMax, can we just store the value in oldMax and not the reference to node containing oldMax ?
there's one missing bit here. in `pop()` when `null == stack` -> `max = null`
MaxStack yet another data structure worth knowing :)
the best way is just save the max for every push, meaning we just keep a max stack that you push there the max up to the latest push/pop
Superb video :). Could please use dark theme editor as this white background is quite hard on the eyes. Thanks
Whats kind of interesting about this problem is that it wouldn't work with a Queue because the you could derive a test case where the oldmax value was no longer correct. In the case of a Queue, I think you'd need to also maintain a heap of items. Would be another fun problem!
Yeah hadn't even thought of that. interesting point!
the "x1 ..x2...x3..x4" expression was funny. :)
What if you pop and there's only 1 element in the stack? You're not changing the max value in this case. Will it still be the value that you popped? Shouldn't you set max to null in this case?
Is there any difference between Approach1 and Approach2 in terms of appropriateness of memory handling?
In both the approaches I have removed throwing null pointer exception part of the code.
Approach1 (Sam's approach):
-----------------------
int pop() {
Node n=stack;
stack=n.next;
if(n.oldMax!=null) max=n.oldMax;
return n.value;
}
Above approach is able to signal that Node n is going out of scope hence we have a way to signal that destructor has to be called. I am thinking C++ way here.
Approach2 (My approach):
-----------------------
int pop() {
int value = stack.value;
if(stack.oldMax!=null) max=stack.oldMax;
stack=stack.next;
return value;
}
Above approach completely relies on the intelligence of garbage colelctor to decide that the earlier "stack" node is dangling now and has to be collected and free'd.
Nice .. thanks from INDIA
Great solution, but I think there's a very likely case that isn't handled by this implementation. If I push 3, 2, then 1, stack will be 1->2->3->null, and max will be 3->null. Once you pop once, there are still elements in the stack, but there's no longer a max. The problem is that any time an element is pushed that's not the max, but also not the min, it won't be registered as a candidate for max later. I don't think this bug can be solved while maintaining constant time.
If you pop 1 or 2, 3 is still the max. It's only if you pop 3 or push on something larger than 3 that the max changes
Byte By Byte Ah thank you, I see it now.
In pop method if condition add this condition
if(stack==null || n.oldMax!=null)
Hi, for the pop part. you have taken care of the case if the element that is popped is the max value and so we assign max to the next. what if the element popped is not the max value in the stack? Shouldn't you check for the case if the element that is popped is actually the max value in stack?
if we pop one that isn't the max then nothing changes because the max is still the same
hey i have a doubt run this test case
1.push
2.pop
3.max
test case:-
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3
your code gives wrong output for maximum always gives 97 even though it is not present
bcz you have not handled the case if oldmax is null for the node . got it?
Or simply try this :
1 97
2
3
what is maximum according to Your code is 97 .But it should be zero since 97 is popped out.
As you havenot updated max for the case if oldmax=null
Yep, you're right we need to fix how we update oldmax. Fixed it in the blog post
Thanks For helping Out.
The change You made in code is still incorrect
try this:--->
1 97
1 120
1 25
2
3
According to your updated code it comes to be zero but in actual it is 120
got it?
Aashish Kalia 😅 thanks for raising bro ..... BytebyByte will resolve it out
shouldn't your value, next, oldMax be public and not private?
Hey Sam, one question How come link list node are pointing to old max .as soon as we change the max value the node will start pointing to new max. As same copy of max will be modified in memory.
because the stack might contain duplicate values as you pop values off the stack, if you have two or more maximum values in the stack (One on top and the other somewhere else) then you need to be sure that you don't remove the maximum value until the rest of the same maximum values are removed.
Cool video!
thanks!
+to u at least because u're using a mic! ( unlike half of video which a dying due to poor sound )))
what are the chances of this being asked in an interview?
This exact problem? not likely, but it is a reasonable problem someone could ask
thank you!
If the stack is null you would get a NullPointerException. You don't need to explicitly throw it.
True. In this case I do like explicitly defining it, though, because it makes it much easier to read the code. You could also come up with some alternate way to handle that situation instead of a NPE
Stack is by definition LIFO.
We can record max_yet on the node of all of the nodes encountered yet. Like so:
class Node:
def __init__(self, val=None):
self.val = val
self.next = None
# holds the maximum val encountered yet!
self.max_yet = None
def __str__(self):
return f"Node"
class Stack:
def __init__(self):
self.head = None
def push(self, val) -> None:
if self.head is None:
self.head = Node(val)
self.head.max_yet = val
else:
old_head = self.head
self.head = Node(val)
self.head.next = old_head
self.head.max_yet = max(old_head.max_yet, val)
def pop(self) -> Node:
if self.head is None:
raise KeyError("Nothing to pop")
old_head = self.head
self.head = self.head.next
return old_head
def max(self) -> int:
if self.head is None:
raise KeyError("No items in the stack")
return self.head.max_yet
s = Stack()
s.push(1)
s.push(2)
s.push(3)
assert s.max() == 3
s.push(2)
assert s.max() == 3
s.push(1)
assert s.max() == 3
s.pop()
assert s.max() == 3
s.pop()
assert s.max() == 3
s.pop()
assert s.max() == 2
s.push(5)
s.push(4)
assert s.max() == 5
assert s.head.next.max_yet == 5
This implementation doesn't working because pop() always sets max to oldMax but push() doesn't always set oldMax
push(2) // max points to 2
push(1) // max points to 2 but 1.oldMax is null
pop() // max is set to 1.oldMax which is null
max() // NullPointerExceptions
public int pop() {
if (stack == null) throw new NullPointerException;
Node n = stack;
stack = n.next;
if (stack == null || n.oldMax != null) //
There's already a throw new NullPointerException when stack == null in the beginning of the pop()