5 ms·

How do you guys come up with such an algorithm

11 points by Handsome2734 5y ago

I was on an Apple QA interview yesterday, and I was asked to design a stack, which can do push and pop, and should have O(1) complexity to find the minimum value. I couldn't solve the problem, so after the interview, I looked up Google and found this: https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/ I wonder how you come up with such a solution when given the problem. It seems just incredible.

drooby 5y ago
O(1) implies it should always be sorted. So just accessing the top should be the solution. This implies that inserts and removals will be the more complex task. The naive approach would just be adding and then sorting - O(nlogn). But the best solution I believe is a max heap.. they essentially wanted you to write a max heap algo.
- melony 5y ago
  A correct max heap is very difficult to implement from scratch during an interview. Also, shouldn't it be a min-heap?
jerf 5y ago
You state "O(1) complexity to find the minimum value", but usually without further qualification, that refers to time, not space. With O(1) time, the easiest solution is just to store the minimum-to-date next to the value in the stack. Consulting the minimum is then just looking at the top value's minimum entry. In this case, the big clue is that O(1) means that there must be somewhere "constant" to look for the solution. In a stack, there's only one practical place to look in O(1) time. (In principle, "the second element" is always O(1) as well, as long as it is always the second unconditionally, but there's no clear reason to add that condition.) Since that place is incorrect, you're going to have to add one. Then it's only a matter of per-element, or per-stack, and from there it won't take long to work it out. Larger O() factors imply a larger possibility of places to look and possible things to compute. Not that I ask these questions in interviews anyhow, but I think a case could be made that's not entirely an unreasonable question. (Albeit weird for a QA position, unless you're going to be literally testing underlying APIs. Any UI-level QA position this is massive overkill for.) That is at least in the ballpark of problems I do solve all the time. I am always adding fields to things for faster lookup or something, even if I'm not implementing a generic stack. The "do it in O(1) space question" can be a trick question, either accidentally or otherwise, if the interviewer isn't careful to specify that they want it done for integers specifically. A lot of the clever "pack it in a tighter space" questions revolve around exploiting the properties of integers, and involve having seen uses of XOR or things like that. If they don't communicate it's integer-only, and the interviewee makes the completely reasonable assumption that "stacks" are meant to be data-type generic (since that's how we usually encounter them in the real world), the interviewer has accidentally asked a question which may be effectively impossible. (Which, in principle, means you should further ask your interviewer about it. However it seems the sort of people asking this question are also often inclined to not be that specific or something.) If you are not exceedingly fast on your feet with integer manipulation, in many ways the answer is just that you've done enough of these to have more-or-less memorized the tricks. Unless this is an interview for a super-constrained embedded job, I would not consider this a good interview question. There's a lot of games you can play with the integers specifically, because of their confined range of values and the strong relationships between them, but I almost prefer that you not know them, or that if you do know them that you keep them to yourself. I don't want to see that kind of game played in my code without a very good reason. Plus it's just memorization.
- Someone 5y ago
  > With O(1) time, the easiest solution is just to store the minimum-to-date next to the value in the stack. Consulting the minimum is then just looking at the top value's minimum entry. That won’t work. The all-time minimum may have been popped when the call to retrieve the lowest value currently on the stack is made. As a first go, I would use a min-heap (https://en.wikipedia.org/wiki/Heap_(data_structure) https://en.wikipedia.org/wiki/Heap_(data_structure)) and a stack. Adding items then is a matter of adding them to both the heap and the stack. Popping would pop an item from the stack, look up any item in the heap with that value, and remove that. To get the minimum, look at the top of the min-heap. Now, there probably is a way to combine these two data structures. I can’t rapidly think of one that’s more efficient in space and/or time, though. (Edit: thinking more about it, I guess the problem also requires push and, in particular, pop to be O(1). Without that, the problem is trivial, as you can update the minimum value after every push or pop)
  - jerf 5y ago
    The original post may have some ambiguity in the term "minimum" but I read it as the minimum of the current contents of the stack, based on where the link the OP provided went to. When I said "minimum to date", I meant relative to the current contents of the stack in order. That is, if you push a value larger than the minimum on the top of the stack, you copy the minimum, if it's smaller, the pushed entry on the stack will be the pushed value, then the pushed value again as the minimum. This always keeps the minimum of the stack on the top of the stack. "All time minimum" would just be one place to store the minimum, since popping would do nothing to it. It is equivalent to the simplest algorithm to find the min of an unsort array/set/whatever.
    - Someone 5y ago
      Sorry, misinterpreted ”store the minimum-to-date next to the value in the stack”, reading it as if you had the stack and, next to it, a single “minimum to date” value.
pyfan878 5y ago
This pretty standard interview question. You should keep track of the current minimum when you do a push: push 1: [(v=1,m=1)] push -1: [(v=1, m=1), (v=-1, m=-1)] push 3: [(v=1, m=1), (v=-1, m=-1), (v=3, m=-1)] get_min: [(v=1, m=1), (v=-1, m=-1), (v=3, m=-1)] returns m=-1 pop: [(v=1, m=1), (v=-1, m=-1)] returns v=3 get_min: returns -1
- d--b 5y ago
  problem is when you pop the min, you can't know which was the second to min unless you do the trick that's in the website quoted.
  - ahmedtd 5y ago
    You don't pop the min, you pop the top of the stack.
    - arcastroe 5y ago
      Yes. Of course. But what do you do when the top of the stack IS the min? Your new min should change, but you won't have the information to update to the second min unless you do the trick in the article.
- masterof0 5y ago
  Came here to say this, as far as LC questions go, this one is pretty straight forward. OP, the way you come up with a solution like this is practice and more practice, the same way you can solve an equation you never seen before, because you have a set of tools (patterns, "tricks", knowledge, ...) that allows you to come up with a solution. Keep practicing and you will see the progress.
  - d--b 5y ago
    OP meant O(1) in time and space (forgot the space but it’s in the linked article). That solution is O(N) in space.
d--b 5y ago
It's a shitty question. it's not O(1) in space cause it's using bits of the numbers on the stack to store extra information. The operations will overflow if it's filled with large enough numbers. This is not a brain teaser, this is a question you know the answer of or you don't. Nobody can come up with a crappy algorithm like this on the spot, especially in an interview setting. I hope your interviewer is reading this.
tra3 5y ago
Current answers are dealing with the technical aspect of the question, I'm gonna go in the other direction slightly. I've gone through a couple of leetcode style interviews recently. Basically it's either you've seen the question or have done a similar style question. I don't see how you can solve a question like that during an interview otherwise. I'm sure some people can solve things like that on the spot, but their minds must work differently than mine. I liked one of the comments on leetcode.com that basically amounted to:"some guy wrote a phd to solve this problem and 30 years later we're now expected to solve this in under 30 minutes in artificially stress induced conditions".
- decafninja 5y ago
  This. You need to grind leetcode enough that you can match the interview question to the leetcode problem. The best case scenario is that you get the exact leetcode problem more or less. Then you put on a show pretending like you've never seen it before and act like you serendipitously arrive at the optimal solution via iterating it from a naive one. Less than ideal, but still great is when it's not a perfect match but you can recognize the pattern required to solve it - which comes from grinding. There are a finite number of patterns and sub-patterns into which many interview questions fall into. You could still end up unlucky enough to get a question that does not, but at the end of the day, it's matter of optimizing your chances.
- jeffybefffy519 5y ago
  Its the problem with these kinds of interviews, its basically filtering for one kind of candidate which is why all the big tech places lack diversity.
aleksiy123 5y ago
I think you may have needed to clarify the question further. The solution you linked is more complex than what is actually being asked. The way you stated it the only requirement is O(1) runtime complexity on finding the min. You are already using O(n) space for the stack so you should be fine using extra linear space. The push and pop operations also don't necessarily have to be O(1) which makes this a lot simpler. You should clarify this in the interview. the discussion section here should give you some ideas https://leetcode.com/problems/min-stack/description/ https://leetcode.com/problems/min-stack/description/ The solution they are probably looking for is quite simple if a little tricky. Each node in the stack should store two values (the value pushed, the min of the stack when that node was inserted) This way you only have to compare the current value to the min at the top of the stack when inserting and don't have to find the min again when popping. This gives O(1) findMin, push, pop and O(n) space.
chiph 5y ago
They're wanting a QA role to be able to answer leetcode style questions? Why?
- rasz 5y ago
  Because when you make $200K you feel entitled and have strong urge to gatekeep. No random peon can have what you got unless his brain is made out of gold, like yours!
VirusNewbie 5y ago
They asked this in a QA position interview?

11 points by Handsome2734 5y ago

drooby 5y ago

O(1) implies it should always be sorted. So just accessing the top should be the solution. This implies that inserts and removals will be the more complex task. The naive approach would just be adding and then sorting - O(nlogn). But the best solution I believe is a max heap.. they essentially wanted you to write a max heap algo.

melony 5y ago
A correct max heap is very difficult to implement from scratch during an interview. Also, shouldn't it be a min-heap?

jerf 5y ago

You state "O(1) complexity to find the minimum value", but usually without further qualification, that refers to time, not space. With O(1) time, the easiest solution is just to store the minimum-to-date next to the value in the stack. Consulting the minimum is then just looking at the top value's minimum entry. In this case, the big clue is that O(1) means that there must be somewhere "constant" to look for the solution. In a stack, there's only one practical place to look in O(1) time. (In principle, "the second element" is always O(1) as well, as long as it is always the second unconditionally, but there's no clear reason to add that condition.) Since that place is incorrect, you're going to have to add one. Then it's only a matter of per-element, or per-stack, and from there it won't take long to work it out. Larger O() factors imply a larger possibility of places to look and possible things to compute. Not that I ask these questions in interviews anyhow, but I think a case could be made that's not entirely an unreasonable question. (Albeit weird for a QA position, unless you're going to be literally testing underlying APIs. Any UI-level QA position this is massive overkill for.) That is at least in the ballpark of problems I do solve all the time. I am always adding fields to things for faster lookup or something, even if I'm not implementing a generic stack. The "do it in O(1) space question" can be a trick question, either accidentally or otherwise, if the interviewer isn't careful to specify that they want it done for integers specifically. A lot of the clever "pack it in a tighter space" questions revolve around exploiting the properties of integers, and involve having seen uses of XOR or things like that. If they don't communicate it's integer-only, and the interviewee makes the completely reasonable assumption that "stacks" are meant to be data-type generic (since that's how we usually encounter them in the real world), the interviewer has accidentally asked a question which may be effectively impossible. (Which, in principle, means you should further ask your interviewer about it. However it seems the sort of people asking this question are also often inclined to not be that specific or something.) If you are not exceedingly fast on your feet with integer manipulation, in many ways the answer is just that you've done enough of these to have more-or-less memorized the tricks. Unless this is an interview for a super-constrained embedded job, I would not consider this a good interview question. There's a lot of games you can play with the integers specifically, because of their confined range of values and the strong relationships between them, but I almost prefer that you not know them, or that if you do know them that you keep them to yourself. I don't want to see that kind of game played in my code without a very good reason. Plus it's just memorization.

Someone 5y ago
> With O(1) time, the easiest solution is just to store the minimum-to-date next to the value in the stack. Consulting the minimum is then just looking at the top value's minimum entry. That won’t work. The all-time minimum may have been popped when the call to retrieve the lowest value currently on the stack is made. As a first go, I would use a min-heap (https://en.wikipedia.org/wiki/Heap_(data_structure) https://en.wikipedia.org/wiki/Heap_(data_structure)) and a stack. Adding items then is a matter of adding them to both the heap and the stack. Popping would pop an item from the stack, look up any item in the heap with that value, and remove that. To get the minimum, look at the top of the min-heap. Now, there probably is a way to combine these two data structures. I can’t rapidly think of one that’s more efficient in space and/or time, though. (Edit: thinking more about it, I guess the problem also requires push and, in particular, pop to be O(1). Without that, the problem is trivial, as you can update the minimum value after every push or pop)
- jerf 5y ago
  The original post may have some ambiguity in the term "minimum" but I read it as the minimum of the current contents of the stack, based on where the link the OP provided went to. When I said "minimum to date", I meant relative to the current contents of the stack in order. That is, if you push a value larger than the minimum on the top of the stack, you copy the minimum, if it's smaller, the pushed entry on the stack will be the pushed value, then the pushed value again as the minimum. This always keeps the minimum of the stack on the top of the stack. "All time minimum" would just be one place to store the minimum, since popping would do nothing to it. It is equivalent to the simplest algorithm to find the min of an unsort array/set/whatever.
  - Someone 5y ago
    Sorry, misinterpreted ”store the minimum-to-date next to the value in the stack”, reading it as if you had the stack and, next to it, a single “minimum to date” value.

pyfan878 5y ago

This pretty standard interview question. You should keep track of the current minimum when you do a push: push 1: [(v=1,m=1)] push -1: [(v=1, m=1), (v=-1, m=-1)] push 3: [(v=1, m=1), (v=-1, m=-1), (v=3, m=-1)] get_min: [(v=1, m=1), (v=-1, m=-1), (v=3, m=-1)] returns m=-1 pop: [(v=1, m=1), (v=-1, m=-1)] returns v=3 get_min: returns -1

d--b 5y ago
problem is when you pop the min, you can't know which was the second to min unless you do the trick that's in the website quoted.
- ahmedtd 5y ago
  You don't pop the min, you pop the top of the stack.
  - arcastroe 5y ago
    Yes. Of course. But what do you do when the top of the stack IS the min? Your new min should change, but you won't have the information to update to the second min unless you do the trick in the article.
masterof0 5y ago
Came here to say this, as far as LC questions go, this one is pretty straight forward. OP, the way you come up with a solution like this is practice and more practice, the same way you can solve an equation you never seen before, because you have a set of tools (patterns, "tricks", knowledge, ...) that allows you to come up with a solution. Keep practicing and you will see the progress.
- d--b 5y ago
  OP meant O(1) in time and space (forgot the space but it’s in the linked article). That solution is O(N) in space.

d--b 5y ago

It's a shitty question. it's not O(1) in space cause it's using bits of the numbers on the stack to store extra information. The operations will overflow if it's filled with large enough numbers. This is not a brain teaser, this is a question you know the answer of or you don't. Nobody can come up with a crappy algorithm like this on the spot, especially in an interview setting. I hope your interviewer is reading this.

tra3 5y ago

Current answers are dealing with the technical aspect of the question, I'm gonna go in the other direction slightly. I've gone through a couple of leetcode style interviews recently. Basically it's either you've seen the question or have done a similar style question. I don't see how you can solve a question like that during an interview otherwise. I'm sure some people can solve things like that on the spot, but their minds must work differently than mine. I liked one of the comments on leetcode.com that basically amounted to:"some guy wrote a phd to solve this problem and 30 years later we're now expected to solve this in under 30 minutes in artificially stress induced conditions".

decafninja 5y ago
This. You need to grind leetcode enough that you can match the interview question to the leetcode problem. The best case scenario is that you get the exact leetcode problem more or less. Then you put on a show pretending like you've never seen it before and act like you serendipitously arrive at the optimal solution via iterating it from a naive one. Less than ideal, but still great is when it's not a perfect match but you can recognize the pattern required to solve it - which comes from grinding. There are a finite number of patterns and sub-patterns into which many interview questions fall into. You could still end up unlucky enough to get a question that does not, but at the end of the day, it's matter of optimizing your chances.
jeffybefffy519 5y ago
Its the problem with these kinds of interviews, its basically filtering for one kind of candidate which is why all the big tech places lack diversity.

aleksiy123 5y ago

I think you may have needed to clarify the question further. The solution you linked is more complex than what is actually being asked. The way you stated it the only requirement is O(1) runtime complexity on finding the min. You are already using O(n) space for the stack so you should be fine using extra linear space. The push and pop operations also don't necessarily have to be O(1) which makes this a lot simpler. You should clarify this in the interview. the discussion section here should give you some ideas https://leetcode.com/problems/min-stack/description/ https://leetcode.com/problems/min-stack/description/ The solution they are probably looking for is quite simple if a little tricky. Each node in the stack should store two values (the value pushed, the min of the stack when that node was inserted) This way you only have to compare the current value to the min at the top of the stack when inserting and don't have to find the min again when popping. This gives O(1) findMin, push, pop and O(n) space.

chiph 5y ago

They're wanting a QA role to be able to answer leetcode style questions? Why?

rasz 5y ago
Because when you make $200K you feel entitled and have strong urge to gatekeep. No random peon can have what you got unless his brain is made out of gold, like yours!

VirusNewbie 5y ago

They asked this in a QA position interview?