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.
Got the solution...
- fenghaolw October 02, 20121. Find the min and max: takes O(n)
2. Divide the interval between min and max into n-1 buckets of equal size (note that we are dividing the interval instead of the array): takes O(n)
3. For each of the remaining n-2 numbers, determine which buckets it belongs to: takes O(n)
4. For each bucket, compute the min and max in this bucket (if the bucket is empty return empty; if the bucket only has one number, min = max): takes O(n)
5. Since there are n-1 buckets and n-2 numbers: there must be one empty bucket. That indicates that the maximum gap must be at least the length of the bucket. We don't need to compare the gap between any numbers in the same bucket.
6. So all we need to do is to compare the inter-bucket distance and find the maximum one. That takes at most O(n).
In total the time complexity is O(n)
The solution can also be found by google "Maximum-Gap-Problem"