xyz Interview Question Developer Program Engineers
Team: xyz
Country: India
If the array becomes sorted based on just one swap then utmost two elements can be out of order.
Iterate through the array and for each iteration the following condition must hold - elements[i] < elements[i+1]. If this is not the case then we have found the first element that is out of order. Pick the smallest element named elements[j] from the remaining portion of the array such that the index j is greater than i
Swap these two elements and iterate through the array again to check if the array is ordered.
Attaching my C++ solution and the three test cases
1. [1 2 3 4 5 6] - Already sorted no swaps necessary
2. [1 2 3 9 6 7 4 12 13] - One swap of 9 and 4 makes the array sorted
3. [1 2 6 3 4 5] - A single swap cannot make the array sorted.
4. [1 2 9 9 2] - A single swap of 9 and 2 makes the array sorted
// http://www.careercup.com/question?id=5738109364862976
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector <int> elements;
int tmp_element;
// Store the array elements in a vector for easier access
unsigned int num_elements;
cin >> num_elements;
for(unsigned int i=0; i<num_elements; ++i)
{
cin >> tmp_element;
elements.push_back(tmp_element);
}
int min_element, min_element_index, i, swap_index = 0;
bool ordered = true;
for(i=0; i<elements.size()-1; ++i)
{
if(elements[i] >= elements[i+1])
{
swap_index = i;
break;
}
}
// If there are more elements to be handled by the loop
if(i < elements.size()-1)
{
min_element = elements[i+1];
min_element_index = i+1;
if(elements.size() > i+1)
{
for(unsigned int j=i+2; j<elements.size(); ++j)
{
if(elements[j] < min_element)
{
min_element = elements[j];
min_element_index = j;
}
}
}
// Swap the elements
tmp_element = elements[swap_index];
elements[swap_index] = elements[min_element_index];
elements[min_element_index] = tmp_element;
}
else
{
// All the elements are already handled by the previous for loop
// Not even a single swap is needed in this case
ordered = true;
}
if(ordered)
{
for(unsigned int i=0; i<elements.size()-1; ++i)
{
if(elements[i] > elements[i+1])
{
ordered = false;
break;
}
}
}
if(ordered)
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
All that has to be done is to check that every i element is greater than i-1. Count the instances of that and return true iff the count == 1.
O(n) runtime and O(1) memory:
public static boolean sortIn1Swap(int[] arr){
if(arr == null){
throw new NullPointerException();
}
if(arr.length < 2){
throw new IllegalArgumentException();
}
//flag that tracks if the single instance of a misordered element has been found
boolean needsASwap = false;
for(int i = 1; i < arr.length; i++){
if(arr[i] < arr[i-1]){
//if a misordered element has already been found, return false
if(needsASwap){
return false;
}
needsASwap = true;
}
}
return needsASwap
}
ArrayList<Integer> positionsOutOfOrder = new ArrayList<>();
for(int i = 1; i < arr.length; i++) {
if(arr[i-1] > arr[i]) {
positionsOutOfOrder.add(i);
}
}
if (positionsOutOfOrder.size() != 2) {
throw new IllegalArgumentException("different algorithm needed");
}
//Swap out of order positions
int temp = positionsOutOfOrder.get(0);
arr[positionsOutOfOrder.get(0)] = arr[positionsOutOfOrder.get(1)];
arr[positionsOutOfOrder.get(1)] = temp;
//Test
for(int i = 1; i < arr.length; i++) {
if(arr[i-1] > arr[i]) {
throw new Exception("swapping two out of order positions did not sort the array");
}
}
public boolean swapAnyTwoItemsToSortArray(int[] array) {
ArrayList<Integer> positionsOutOfOrder = new ArrayList<Integer>();
for (int i = 0; i < array.length; i++) {
if (array[i - 1] > array[i] {
positionsOutOfOrder.add(i - 1);
}
}
if (positionsOutOfOrder.size() != 2) {
throw new Exception("different algorithm needed");
}
int temp = array[positionsOutOfOrder.get(0)];
array[positionsOutOfOrder.get(0)] = array[positionsOutOfOrder.get(1)];
array[positionsOutOfOrder.get(1)] = temp;
for (int i = 0; i < array.length; i++) {
if (array[i - 1] > array[i] {
throw new Exception("Array still not in order");
}
}
}
public boolean swapAnyTwoItemsToSortArray(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int p = 1; i < array.length; p++) {
//swap
int temp = array[i];
array[i] = array[p];
array[p] = temp;
if (sorted(array)) {
return true;
} else {
//swap back
temp = array[i];
array[i] = array[p];
array[p] = temp;
}
}
}
return false;
}
private boolean sorted(int[] array) {
for (int i = 0; i < array.length; i++) {
if (array[i - 1] > array[i] {
return false;
}
}
return true;
}
I believe the following should be an O(n) solution. Scan once to find the first element where a[i] >= a[i+1]. If it's = keep scanning until you either meet a number greater than it, in which case you throw out that guess and continue or a number where a[i] < a[j] in which case you save it. In other words save the FIRST index of a run of equal numbers. Then find the next element out of order such that a[j-1] >= a[j]. Do the same as above but in reverse to save the last index of a run of equal numbers.(Note this shouldn't actually need to be done for j as if there is a run of equal numbers out of order at this point, there is automatically more than two out of order and it's false). Swap j and i Scan one more time to see if it's sorted.
If nothing else is out of order, only then, do you let j = i+1; Otherwise you'll always let j = i+1 by definition.
Counter Example posted above:
1, 2, 9, 9, 2
Scan 1: A[i] = 9 as 9 >=9>2, A[j] = 2 as 2 < 9
swap 9 and 2
1,2,2,9,9,is sorted
1, 2, 2, 2, 1, 9
Scan 1: a[i] = 2 as 2 >= 2 >= 2 > 1 a[j] = 1 as 1 < 2
swap 2 and 1
1,1,2,2,2,9 is sorted.
1 2 3 7 5 6 4 8 9
Scan 1: a[i] = 7 a[j] = 4
Swap 4 and 7
Scan 3: It's in order
8 1 2 3 4 5 6 7 0
Scan 1:a[i] = 8 a[j] = 0
swap
scan 2: in order
1 2 3 5 4 7 6 8 9
Scan 1: a[i] = 5, a[j] = 4
Swap
Scan 2: out of order.
1 2 3 5 4 6 7 8 9
Scan 1: a[i] = 5 a[j] = 4
Swap
Scan 2 in order.
0, -10, 10, 20, 30, 40, 50
Scan 1: a[i] 0 and a[j] = -10
swap a[i] and a[i+1]
scan2 in order
0, 2, 4, 6, 8, 10, 9
Scan1: a[i] = 10, a[j] = 9
swap a[i] and a[j]
scan 2: sorted.
It's important that you never let j = i+sizeofequalrun unless you didn't find a candidate j elsewhere in the array. Therefore set j to a dummy value and if it's still that dummy value after the scan set it to "defaultJ" which will be either i+1 or j+sizeofrunofnumbersequaltoJ. Here's the code to show it's not hard to implement.
bool ifoneswapp(std::vector<int> a) {
int i = a.size(), j = a.size();
int defaultJ = a.size();
for (int k = 0; k < a.size() - 1; ++k) {
if (a[k] >= a[k + 1]) {
i = k;
while (k < a.size() - 1 && a[k + 1] == a[k]) {
k++;
};
if (a[k + 1] < a[k]) {
defaultJ = k + 1;
break;
}
}
}
for (int k = defaultJ + 1; k < a.size(); ++k) {
if (a[k] < a[k - 1]) j = k;
}
if (j == a.size()) j = defaultJ;
if (i >= a.size() || j >= a.size()) return true;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
for (int i = 0; i < a.size() - 1; ++i) {
std::cout << a[i] << " ";
if (a[i] > a[i + 1]) return false;
}
return true;
}
If anyone can think of a counter example, I would be much obliged. I only ran the tests above but I believe it makes sense. The only way for a single swap to make a sorted array is if there are two numbers A[i] and A[j] that split the whole array A into 3 sorted arrays of possibly empty size where A[i] > A[j] if i < j. If there's more than a single swap won't work and if A[i] < A[j] for i < j then a swap will place you in the same position as the 3 sub arrays are already sorted and you're placing a smaller(or greater) number at the end
#include<iostream>
// Function prototypes
bool isSortedArrayPossible(int* nArray, int nLength);
void swap(int* num1, int* num2);
int main()
{
int nArray[] = {5, 13, 19, 22, 29, 21};
int nLength = sizeof(nArray) / sizeof(int);
if(isSortedArrayPossible(nArray, nLength))
{
std::cout << "Sorted array is possible\n";
}
else
{
std::cout << "Sorted array is not possible\n";
}
return 0;
}
// ------------------------------------------------------------------------------------
// Func : bool isSortedArrayPossible(int* nArray, int nLength)
// Descrip : Check whether we can get a sorted array or not
// ------------------------------------------------------------------------------------
bool isSortedArrayPossible(int* nArray, int nLength)
{
int i = 0;
while(i < nLength - 1 && nArray[i] < nArray[i + 1])
{
i++;
}
int j = i + 1;
while(j < nLength - 1 && nArray[j] < nArray[j + 1])
{
j++;
}
swap(nArray + i, nArray + j);
bool bSorted = false;
if(nArray[i] < nArray[i + 1] && (i == 0 || nArray[i] > nArray[i - 1]))
{
if(nArray[j] > nArray[j - 1])
{
int k = j;
while(k < nLength - 1 && nArray[k] < nArray[k + 1])
{
k++;
}
if(k == nLength - 1)
{
bSorted = true;
}
}
}
return bSorted;
}
// ----------------------------------------------------------
// Func : void swap(int* num1, int* num2)
// Descrip : Swap two numbers
// ----------------------------------------------------------
void swap(int* num1, int* num2)
{
int nTemp = *num1;
*num1 = *num2;
*num2 = nTemp;
}
Time complexity: O(n)
Space complexity: O(1)
- sagar June 14, 2015public static boolean canSortInOneSwap(Integer array[]){ if(array != null && array.length > 1){ boolean notInOrder = false; // Scan array from last index for first not ordered element. int i; for(i = array.length-1; i > 1; i--){ if(array[i] < array[i-1]){ notInOrder = true; break; } } // If found not at least one not ordered element, // Scan for its correct position and swap if(notInOrder){ for(int j = i-1; j >= 0 ; j--){ if(array[j] <= array[i] || j==0){ // If we find element smaller than or equal to array[i] // swap array[i] with element after that i.e. (j+1)th if(array[j] <= array[i]) j++; int temp = array[j]; array[j] = array[i]; array[i] = temp; break; } } // check if array is sorted now. for(i = 0; i < array.length-1; i++){ if(array[i] > array[i+1]){ return false; } } return true; } } return false; }