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.
I have a solution here: (not converted to code yet, but it should be simple)
- Yi-An Lai November 21, 2013All you need to do is fill 2 arrays, both of which having length n (lenght of the input array). One recording the greatest value seen so far, and the other recording the smallest value after that position, which is easier if we start the scan from the very end of the array.
For example,
input: [ 2, 3, 1, 4, 5, 6, 5 ]
1st array: [ 2, 3, 3, 4, 5, 6, 6 ] // start the scan at the beginning and keep track of max
2nd array: [ 1, 1, 1, 4, 5, 5, 5 ] // start the scan at the end and keep track of min
After we have these 2 array, we look for matching elements, which is 4 & 5 at index 3 & 4 respectively. These two are the possible index for choosing a pivot.
If no matches can be found, return -1:
input: [ 3, 2, 1 ]
1st: [ 3, 3, 3]
2nd: [ 1, 1, 1]
=> no match
This solution is correct because of the fact that, everything on the LHS of the pivot point is smaller than or equal to the pivot value, that is to say, the maximum value on the LHS of the pivot point is equal to the pivot value. Vice versa for minimum value on the RHS.
Hope this helps.