is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.
Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.
Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.
1. Dynamic Programming.
Establish a DP record array:
min[] to represent how many min steps it needs to reach the current position.
steps[] is the input array.
We get the recurrence formula
min[i] = min{min[k] where k = 0, 1, 2, ..., i-1 if k+steps[k] >= i} + 1
Base condition:
min[0] = 0;
DP gives O(n^2) time complexity and O(n) space complexity.
2. Greedy
Every time we make the greedy decision:
for example we have steps[] = {2, 0, 1, 4}
when we are at index = 0, we can reach index 0, 1, 2.
Check each index and find they can reach 2, 1, 3 respectively. The last one can reach farthest. So we make a greedy decision to jump to index 2. We continue the jumping process til we reach the end of the array.
Greedy method takes O(n) time and O(1) space
Here's the Java code:
- njuprincerain May 31, 2014