Stack Problem
I recently had a phone interview with a company and was asked a question about stacks that I didn't know how to properly s...
For further actions, you may consider blocking this person and/or reporting abuse
Some stack implementations or definitions have a
peek()methos that reads the last element without popping it.You could just have a single variable that holds the maximum value where when an element is pushed to the stack, you check if its greater than the existing, if so replace, and when an element is popped, peek the stack to check if the max value is still higher than the last.
This of course is through a modified stack implementation. I also interpreted the problem to be creating a function that takes in a stack (data set already) and returns a max value.
I'd still try to use the idea I mentioned above of a max value variable, but traversing a stack is the interesting part here, I believe.
My flow would be as follows:
Hi Beautus,
Thank you for reading!
I did implement the peek method in my stack to see the last value in the array.
I'm not sure if I am understanding your implementation right, but I think the way you're thinking about the problem is the way I originally thought of it as well. However say you have this stack
[1, 2, 1, 3]. In this case, 3 would be your current stored Max. Now if you pop 3 off and just peek the last element, your code would assume the new max is 1, however it's actually 2.This is why using another stack is helpful. With my code, the max stack would look like this `[1, 2, 2, 3]'. Now when 3 is popped off the stack, my code will also pop the last value of the max stack. Now we have:
//current stack
[1, 2, 1]
//max stack
[1, 2, 2]
Now all we have to do is peek the last element of the max stack and know that the current max is 2.
Thanks for your input and let me know if I cleared it up a bit.
No no, I do understand your solution fully. What I didn't make clear though is that my solution assumes that a stack is already hydrated when it gets the max value, and your solution is perfect for getting the max value without traversing the stack each time max is required. I'm not sure if you get me
Oh I see. I did misunderstand at first, I apologize for that. So your solution is a loop, but with pushing to a holding stack while comparing values? This also assumes that no new values are added to the stack. Am I understanding it correctly?
Yes that definitely it
I find these type of interview questions to be stress inducing and inefficient in screening for candidates that are worth working with (imho).
FWIW, the answer depends on the underlying data structure used to implement the stack.
If using linked lists, then the solution would involve iterating from head to tail and returning the max value found
If using arrays, then both
Math.max(...stack)orstack.sort((a, b) => b - a)[0]will workIf using a tree, then the solution would require either traversing or using a self-balancing tree
In all cases, the implementation can also just keep an invariant with the current maximum value, but then it would need to be checked/ updated with every pop and push.
Hi Joaquim,
Thank you for reading!
I agree these questions can be stressful. I have been trying to look at them more as practice and a fun exercise to learn something new.
Thank you for your input! From my conversation with the interviewer, it was obvious he didn't want to have to re-check with a loop every time a new value was added or removed. He was hinting at using another data structure. In this blog, I took that to mean another stack. This method of getting the current max is nice in that you only have to look at the end of the maxValue stack to know the current max.
Once again thank you for reading and for your input!
Tweet from @j_larrieux: @thepracticaldev I think giving more context around the problem would help. I am assuming the question was about keeping track of current max in the stack as new numbers get popped or pushed in the stack. This is not entirely clear from your description.
I love solving interview questions 😀
Hi Sean,
I think you're right and I should have clarified the problem more.
I was trying to write about the problem in the way it was asked of me which wasn't super clear. Originally he just asked how I would write a function to find max in the stack. However after mentioning looping through, he then mentioned potentially using another data structure to store the max, so that I wouldn't have to loop multiple times.
This led me to believe, as you have mentioned that he wanted to keep track of the current max. This is when I started to think about linked lists to store the current and previous max. However, I think this solution is a lot more elegant even if it comes with the use of more memory.
Let me know if I cleared it up a bit. Thank you again!
Good solution, it saves having to look up the max after each push/pop.
This reminded me of Priority Queues: algs4.cs.princeton.edu/24pq/
Not sure if it fits the criteria of your interview question, but you might find it interesting anyway.
"Priority queues are characterized by the remove the maximum and insert operations"
Thank you for reading!
Priority Queues sound very interesting. I'm definitely going to look those up. Thank you for the input!
I'm glad you enjoyed it!
I come from a non-traditional CS background and didn't get a chance to practice these problems in a classroom. I really appreciate the input.
That implementation on stack overflow is really nice. It's very useful to be able to find the current min and max all in the same step. Thank you for sharing!
Hi Pavel,
Thank you for reading the blog!
I wrote about the problem in the way that it was asked by my interviewer, which was a little bit confusing to me. I originally thought I was supposed to find max in a given stack as well, until he explained that if the current max was popped off the stack, he would want to know what the previous max was. After he explained this, it was more obvious that he wanted to keep track of the current max.
While I did mention looping through the stack to find the max, he stated that if he popped or pushed an element he would want to know the new max. The interviewer was leading me to believe that he didn't want loops involved, and wanted me to think of a different data structure to use ( a stack). I should have clarified this more in my blog. Thank you for continuing to read through the confusion, I hope I cleared up my thought process a bit.
I have the same feeling. The problem solved here doesn't correspond with what I thought was the problem at the beginning of the article.
Hi Martin,
Thank you for reading. I responded to Pavel with some clarification. Let me know if I cleared it up or if you have any additional input.
Thank you!
Thanks for the clarification. Indeed, the explanation given by the interviewer was confusing, and sadly most interviewers want the answer they expect or know and don't care too much about how you would solve a similar problem.
Have a nice day!
Of course!
I can imagine it is hard to ask technical questions over the phone without being able to write out exactly what you are looking for. Since I come from a non-traditional CS background and knew very little about stacks during this interview, I needed more guidance to understand the problem.
I definitely will be practicing data structures and algorithms in the coming weeks so I can be better prepared next time. It seems like for a lot of algorithms, it is just memorizing the solution that they are looking for, as you have mentioned.
Have a great rest of your week Martín!
Thanks for the resources! I'll definitely check those out.
That's great! There is hope for me too, then.
Thanks for reading Calin!