Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How do you guys come up with such an algorithm

news.ycombinator.com

Post reply on HN
Print view View original

11–20 of 21 posts

Re: How do you guys come up with such an algorithm

#11

Post by ahmedtd »

d--b wrote: post #8
pyfan878 wrote: post #6

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

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.

You don't pop the min, you pop the top of the stack.

Re: How do you guys come up with such an algorithm

#12

Post by masterof0 »

pyfan878 wrote: post #6

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

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.

Re: How do you guys come up with such an algorithm

#13

Post by arcastroe »

ahmedtd wrote: post #11
d--b wrote: post #8

Earlier quoted context omitted.

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.

You don't pop the min, you pop the top of the stack.

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.

Re: How do you guys come up with such an algorithm

#14

Post by d--b »

masterof0 wrote: post #12
pyfan878 wrote: post #6

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

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.

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.

Re: How do you guys come up with such an algorithm

#15

Post by aleksiy123 »

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/

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.

Re: How do you guys come up with such an algorithm

#16

Post by decafninja »

tra3 wrote: post #10

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 thei…

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.

Re: How do you guys come up with such an algorithm

#19

Post by jeffybefffy519 »

tra3 wrote: post #10

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 thei…

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.
Post reply on HN