Is it just me or the Big O algebra at the end doesn't seem right?
Solving dynamic programming interview problems
11–20 of 176 posts
Re: Solving dynamic programming interview problems
#12Step 1. ur problem graph better be a dag
Step 2. ur sub problems better overlap
Step 3. time to table dat dag
Step 4. solve ur problems and build ur table graph the way a dag would : to-po-lo-gi-cal-ly
Re: Solving dynamic programming interview problems
#13I recently had a programming interview where, at the whiteboard question, I said "this may be a dynamic programming question, let me see--" and the interviewer said "STOP! Stop, every time someone says that, they end up flopping and never getting anywhere. Don't go down that path, I'm telling you." I think it had more to do with the interviewer being a poor interviewer, however.
For me it was a bit the other way around. I solved the problem in a brute force way and on interviewer's asking, was flopping to come up with a better algorithm. Then he mentioned that I should consider DP.
Unfortunately my DP was really bad so I knew right then I'm going to flop. And flop I did.
For me the two weakest points are DP, and coming up with the right O() estimate for an algorithm that I just created on the whiteboard, and am looking at it for the first time in my life. Would love advice on how to get good at both.
Re: Solving dynamic programming interview problems
#14I did watch live where Nikola solves this problem, https://www.youtube.com/watch?v=kKhnYLpME3w. It covered most of requirements of dynamic programming. For me the interesting part was coming up with algorithmic complexity (Big-O) of the solution.
Re: Solving dynamic programming interview problems
#15I recently had a programming interview where, at the whiteboard question, I said "this may be a dynamic programming question, let me see--" and the interviewer said "STOP! Stop, every time someone says that, they end up flopping and never getting anywhere. Don't go down that path, I'm telling you." I think it had more to do with the interviewer being a poor interviewer, however.
For me it was a bit the other way around. I solved the problem in a brute force way and on interviewer's asking, was flopping to come up with a better algorithm. Then he mentioned that I should consider DP. Unfortunately my DP was really bad so I knew right then I'm going to flop. And flop I did. For me the two weakest points are DP, and coming up with the right O() estimate for an algorithm that I just created on th…
For DP? Practice a couple on like HackerRank, CodeFights etc.
It starts to make sense after you do a few.
For Big O notation? Just think about how many times you're iterating through things (in the worst possible case).
e.g. Got two nested for loops each going to N.. we're going to loop N on the outer loop, so and each iteration of the inner loop we go through N times? that's N x N so O(N^2).. (easy example obviously).
Re: Solving dynamic programming interview problems
#16I really wanted to try out your service couple of weeks ago, but turns out you are only in US. Any plans of opening it for Europe?
Yes, currently it is only available for people searching for jobs in the US. I would say the answer is yes long-term, but probably not over the next few months.
Re: Solving dynamic programming interview problems
#17Potentially interesting data point: the company I'm at right now has been pretty successful for over a decade and has, to my knowledge, never once asked a dynamic programming question in an interview for any candidate in that entire time. We've managed to hire a lot of great developers and have very rarely had any real issues.
Re: Solving dynamic programming interview problems
#18Is it just me or the Big O algebra at the end doesn't seem right?
What do you think is wrong, I did not notice any really obvious mistake? Admittedly you would miss the improved bound unless you actually modified the implementation to abort further evaluation once you reach the maximum speed that still allows stopping, but I assume that is implied. I also guess one could even further improve the exponent to 1.25 by taking advantage of the fact that the maximum speed that still allows stopping decreases from left to right but I did not actually think it through, it is just my intuition that you would gain another square root.
Re: Solving dynamic programming interview problems
#19why are there so many companies trying to "solve hiring". i get it's a big expense to make a bad hire but how are there like 10 different companies thinking they have an edge on
1. existing practices 2. each other
Re: Solving dynamic programming interview problems
#20Is it just me or the Big O algebra at the end doesn't seem right?
thanks for this comment. I realized that I skipped a few steps in the explanation, so I am updating it now.
But essentially you see that the equation is S^2 - S - 2L from that, you can solve that the roots of the function are: (1) 1/2 + sqrt(2L) and (2) 1/2 - sqrt(2L)
That means that (S-1/2-sqrt(2L)) * (S-1/2+sqrt(2L)) The second term is always positive, which means that we need to make the first term negative in order for the inequality to hold.
=> S Does this make sense?