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 think I have an O(n) solution, but which is O(n) in space too.
The code would probably be messy so I'll just propose a sketch for the algorithm.
also, the sketch is concerned with finding the maximum sum itself,
but it can (somewhat) easily be modified to return start and end indices,
though, again, it will get even messier.
The complexity, both in space and time, is defined by the reccursive relation :
- Elad December 20, 2013T(n) = T(2n/3) + O(n)
which yields an O(n) total.
The correctness is based on the following observations :
1. If we can take a positive value to the sum, we'll take it.
2. We'll never take a negative value,
unless it leads the way to a possitive value that compensate for it.
3. The algorithm checks all sums of sub arrays
that start and end with a positive value,
and are wrapped with negative values, or original array boundries,
thus returns the right value.
I'll be happy to hear opinions about it, as I just thought of it, so I might be missing out on something..
Also improvements will be welcomed.