Avoid This Coding Interview Mistake! | Dynamic Programming / Climbing Stairs - Leetcode 70

dynamic programming, leetcode, coding interview question, data structures, data structures and algorithms, faang

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[moofymoo]

it would be great if you spent more that 1.333 (repeating) seconds to show actual problem.

[hopiuscoliun]

bold of you to assume I have a solution

[pzfrvyv]

In an interview: code O(1) in both time and memory.

During the actual job: code O(n!) in both time and memory.

[harryclewlow]

This is the worst thing to ask it’s something you can just learn to solve and repeat it back to an interviewer, you will never use this in practicality, they will care more if you can do code and close tickets…

[dusknt]

You can make it O(1) space without using dp by using Binet's formula.

def climbStairs(n):
sqrt5 = 5**0.5
phi = (1 + sqrt5) / 2
psi = (1 - sqrt5) / 2
return int(((phi**(n + 1)) - (psi**(n + 1))) / sqrt5)

[bnjer]

Well actually🤓 if you find the characteristic equation for the recurrence relation. You can solve for x, giving you the characteristic root(s) . You can take any linear combination of those roots that fits your base case as a solution. Making it O(1) time and space complexity

[tiagodagostini]

Wtf? The GODO answer is seeing that this is just a fibonacci series. So it can be solved analitically

[Maaarrrioooooo]

Everyone that is saying it's the fibonacci series so it's constant time, that's just not true. There is no way to get the n-th element of the fibonacci series in O(1), best you can do is O(log n)

[dacjames]

Just remember, it’s not about getting the best answer, it’s about how you respond to feedback and collaborate with the interviewer to improve the solution.

[christopherparke]

Also use a strongly typed language unless the job is a Python job.

[MikhailFederov]

Same trick can be applied to many 2D DP problems where you only need to reference the previous row

[ttpotdx]

It’s simple fibonacci series . We can do it in constant space and linear time

[nevokrien]

U can pull the array out to make big O(1) runtime

[WhyOhWhy]

Did you see that? If you don't know what I'm talking about, you didn't see it.
Hint: it involves another video...

[ghost_online]

Isn't that similar to Fibonacci series

[samipshah]

You can do matrix exponentiation and make it O(logN) and O(1)

[KingGisInDaHouse]

Yeah I would have rejected and black listed that woman immediately for stepping on the cat.

[Quillraven]

That is what is going to get you the job 😂😂😂

Of course, if a company decides if they want me based on that single thing then I guess it is the wrong company for me (11 years in that area and right now Lead Developer).

Guess Austria is a special place because I never had those coding "puzzles" in my interviews.

My interviews cared more about personality and communication skills and wanted to know more about certain github projects they saw.

[Ortiane]

Let's be real here, faang companies ask incredibly difficult questions and multiple questions over multiple hours of interviewing. It takes hundreds of hours to get good at competitive coding styled questions which compromise only a portion of the interview. You can be asked about system design, debugging, project management, yourself, and any number of topics. Basically, don't get a course in this type of stuff. Waste of money since you probably won't even get in the pile of resumes they don't throw out.