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.
Assumptions:
*The method should return true/false, as the question is "is it possible to...".
*We can't affect the array insitu, since we are only characterizing it (it doesn't say "sort the array" or even "return a sorted array").
* Assuming sorting is lowest index => lowest value (numerical order starting at idx 0)
Discussion:
If swapping 2 elements results in a sorted array, it means all of the elements are in their proper place except for the 2 we need to swap.
Thus, if we just walk the array we will run into these "anomalies", which are the out-of-place elements. Naively I claim that we want two and exactly two anomalies, otherwise we can't do this.
But there is an edge-case (literally) when the out-of-place element is on either end and it belongs on the other side of the adjacent element, in which case we would only see one anomaly (either right at the beginning or at the end) and it can be swapped with the neighboring element. If either the start or end element belongs somewhere in the middle, we must have another out-of-place element with which to swap, but if there isn't an internal anomaly, then all of the elements are in the correct place and must be preserved. Allowing repeats makes the previous statement false so that would require clarification of the question.
An easy approach, then, is do a single walk of the array and notate anomalous indices. After the fact, we can return false if we got more than 2, or do some more processing to validate that the one or two out-of-place elements can be "fixed". In this example we do an array copy as a workspace for the swap, so we use an extra N space.
JAVA
We need the 2N space for the copy when we are checking that the swap works. However we can optimize this by just checking that the newly swapped elements would fit between their new neighbors, without actually swapping.
- tseiff April 23, 2015