Country: India
Interview Type: Written Test

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

Here are two observations about the problem:
- For arrays with an odd number of elements, the element in the middle cannot be moved.
- Any element can only be moved to its "mirror" index when you pivot around the center, so the element at index 0, can only move to the index "length - 1"

The "simple" brute force approach would be to try every possible rotation and see if one is found.
Given the second observation above, by rotating around the center each element in the array can have one of two possible values - the value at index i or the value at index "length - 1 - i". For an array with n elements, that means there are 2^n combinations. So Running time would be O(2^n) and memory usage would be O(1).

An alternative approach would be to make a copy of the array, sort that copy and compare each element of the sorted copy to the equivalent element of the original array and it's mirror image when pivot around the center.

Sorting takes O(n lg n) and we make up to 2n comparisons, so the runtime is O(n lg n).
We need a "helper" array with n elements, so the memory needed is O(n).

In Java, the code would look like this:

``````public String canBeSortedByReverse(int[] A) {
int[] B = Arrays.copyOf(A, A.length);
Arrays.sort(B);
for (int i = 0; i < A.length; i++) {
if (!(A[i] == B[i]) && ! (A[A.length - 1 - i] == B[i])) {
return "Not Possible";
}
}
return "Possible";
}``````

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

``````public boolean canSortByReversing(int[] input) {

if(input.length % 2 == 0)
return false;
int middle = input[input.length / 2];
int i = 0,j = input.length - 1,max=0,min=10000;
for(;i != j;i++,j--) {

int left = input[i];
int right = input[j];
if(!orderable(left,middle,right))
return false;
boolean reverseRequired = right < left;

int newMax = left,newMin = right;
if(reverseRequired) {
newMax = right;
newMin = left;
}
if(newMax >= max && newMin <= minRight) {
max = newMax;
min = newMin;
continue;
}

return false;
}

return true;
}

public boolean orderable(int left,int middle,int right) {
return ((left <= middle) && (middle <= right)) || ((left >= middle) && (middle >= right));
}``````

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

public boolean canSortByReversing(int[] input) {

if(input.length % 2 == 0)
return false;
int middle = input[input.length / 2];
int i = 0,j = input.length - 1,max=0,min=10000;
for(;i != j;i++,j--) {

int left = input[i];
int right = input[j];
if(!orderable(left,middle,right))
return false;
boolean reverseRequired = right < left;

int newMax = left,newMin = right;
if(reverseRequired) {
newMax = right;
newMin = left;
}
if(newMax >= max && newMin <= minRight) {
max = newMax;
min = newMin;
continue;
}

return false;
}

return true;
}

public boolean orderable(int left,int middle,int right) {
return ((left <= middle) && (middle <= right)) || ((left >= middle) && (middle >= right));
}

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

Swift 2.2

``````func isSwapSortPossible(array: [Int]) -> String {
if (array.count <= 1) {
return "Possble!"

} else if (array.count % 2 == 0) {
return "Not Possible"

}

let sortedArray = array.sort({ return \$0 < \$1 })
let mid = array.count / 2

for i in 1 ..< mid {
let left = array[mid - i]
let right = array[mid + i]
let sortedLeft = sortedArray[mid - i]
let sortedRight = sortedArray[mid + i]
// If left and right don't pair up and match
if ((left != sortedLeft || right != sortedRight) &&
(left != sortedRight || right != sortedLeft)) {
return "Not Possible!"

}

}
return "Possible!"

}

isSwapSortPossible([1, 6, 3, 4, 5, 2, 7]) // "Possible!"
isSwapSortPossible([2, 6, 5, 1, 7, 5, 4]) // "Not Possible!"``````

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

What about O(N) solution with a simple walkthrough of a copy of the array and swapping elements with mirror index values whenever they don't follow a normal sort order.

We can do that as all the sub-elements between the swapped ones can be put in the same order with another reverse operation.

If a is a copy of the original array, then in C++:

``````bool possible(int *a, const int n) {

int i, t;

for (i=0; i<n/2; ++i) {
if (a[i] > a[n-1-i]) {
t = a[i];
a[i] = a[n-1-i];
a[n-1-i] = t;
}
}

for (i=0; i<n-1; ++i) {
if (a[i] > a[i+1]) {
return false;
}
}

return true;
}``````

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

``````/*
1) all elements on the left must be <= than the element in the
middle after n such mirror operations.
2) Most perumtations that are possible are 2^(n/2), that is,
swap index 0 with n-1, index 1 with n-2, etc...
(independently if given mirror operation is performed outwards inwards)
3) Every element, except the middle one has two possible values,
it's value at index or it's value at mirrored index

Solution:
f[i] = min(a[i], a[n-1-i]) for 0<=i<n/2
e[i] = max(a[i], a[n-1-i]) for 0<=i<n/2

Iterate through the array 1 to n/2-1 and check if:
f[i]>=f[i-1] AND e[i]>=e[i-1]

If that succeeded and length of a is odd, only need to check
f[n/2-1] <= a[n/2] <= e[n/2+1] if that's true, its sortable,
obviously if array length is even, if above iteration succeeded with all checks
it is sortable.

Time complexity O(N)
Space complexicty O(1)
*/

#include <iostream>
#include <algorithm>

using namespace std;

// array with n-elements
bool IsSortable(const int a[], int n)
{
for (int i = 1; i < n/2; ++i)
{
if (min(a[i], a[n - i - 1]) < min(a[i - 1], a[n - i]))
return false;
if (max(a[i], a[n - i - 1]) > max(a[i - 1], a[n - i]))
return false;
}
if (n & 1 == 1)
return min(a[n / 2 - 1], a[n / 2 + 1]) <= a[n / 2] &&
max(a[n / 2 - 1], a[n / 2 + 1]) >= a[n / 2];
return true;
}

int main()
{
int a1[]{ 1,2,3,4,5 };
cout << "a1: " << IsSortable(a1, sizeof(a1)/sizeof(int)) << endl;

int a2[]{ 5,4,3,2,1 };
cout << "a2: " << IsSortable(a2, sizeof(a2) / sizeof(int)) << endl;

int a3[]{ 1,2,6,3,4 };
cout << "a3: " << IsSortable(a3, sizeof(a3) / sizeof(int)) << endl;

int a4[]{ 4,2,1,2 };
cout << "a4: " << IsSortable(a4, sizeof(a4) / sizeof(int)) << endl;

int a5[]{ 9,8,7,6,5,4,3,2,1 };
cout << "a5: " << IsSortable(a5, sizeof(a5) / sizeof(int)) << endl;

int a6[]{ 9,8,7,6,5,4,5,2,1 };
cout << "a6: " << IsSortable(a6, sizeof(a6) / sizeof(int)) << endl;
}``````

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

``````static void IsSortableByReversing()
{
int[] input = { 1, 6, 8, 4, 5, 2, 7 };
int mid = input.Length / 2;
int increment = 1;

while (mid - increment >= 0)
{
if((input[mid + increment] > input[mid] && input[mid - increment] > input[mid]) ||
(input[mid + increment] < input[mid] && input[mid - increment] < input[mid]))
{
Console.WriteLine("Not Possible");
}

increment++;
}
Console.WriteLine("Possible");
}``````

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.