## xyz Interview Question for Developer Program Engineers

Team: xyz
Country: India

Comment hidden because of low score. Click to expand.
2
of 2 vote

Time complexity: O(n)
Space complexity: O(1)

``````public 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;

}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Doesn't work. This code is checking whether the array has at most one element out of place.

Consider this array:

1, 2, 3, 9, 6, 7, 4, 12, 13

The code will return false, but the array can be made sorted by swapping 9 with 4, so it should return true.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````ArrayList<Integer> positionsOutOfOrder = new ArrayList<>();
for(int i = 1; i < arr.length; i++) {
if(arr[i-1] > arr[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");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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] {
}
}
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");
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Won't work. Counter-example: 1, 2, 9, 9, 2. Can be sorted by swapping the first 9 with the second 2; the code throws an exception.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

just check the first element out of order ... hold it in say A..then check the next element out of order after that ...hold it in B...then swap A and B and check for 1 pass of bubble sort ... if flag remains 0 your array is sorted !

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just find the two elements out of order by traversing the array once.As soon as you find one out of order increment a counter.At last check whether the counter is exactly 2 else the array cant be sorted by just swapping!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just find the two elements out of order by traversing the array once.As soon as you find one out of order increment a counter.At last check whether the counter is exactly 2 else the array cant be sorted by just swapping!

Comment hidden because of low score. Click to expand.
0
of 0 vote

While most folks answered to find out two such elements, there is a edge case when both elements to be swapped are adjacent to each other. You need to handle that can as well since you will fin only one instance of value out of order.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

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.