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.
The other solutions proposed so far all run in O(n^2). However, the more interesting question is whether one can do better than O(n^2) without extra data structures. Below is my solution, running in O(n log n).
Let me briefly explain it as follows. Let's call an array arr of length n "good", if the following holds:
1) The roundup(n/2) lowest values of arr all reside at indices 0, 2, 4, ... and are sorted in non-decreasing order,
2) the remaining larger values all reside at indices 1, 3, 5, ..., and are also sorted in non-decreasing order.
For example, the following arrays are good:
{1, 5, 2, 6, 3, 7, 4}
{12, 34, 14, 41, 21, 55, 33, 60}
Now, if an array is good, it can easily be transformed into the required ordering in linear time, by carefully reversing twice: once the whole array (with special treatment of odd array lengh) and once the elements at every second position.
Therefore, the remaining task is to make the input array a good one.
We can achieve this by first sorting the array into non-decreasing order, and then applying a divide-and-conquer approach. In essence, in order to merge to good subarrays, we swap the higher values of the left subarray with the lower values of the right one. Again we must be especially careful of odd subarray lenghts.
It should be noted that O(log n) memory is needed on the stack.
- Stephan April 06, 2017