## Google Interview Question for SDE-2s

Country: India

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

My solution is totally brute force, so it is not efficient, but definitely right, compared to other "smarter" solutions.
For each permutation of the array, I BFS all possible permutations within one transform (swap blocks of the array). Once the final permutation (ascending order) is reached, the problem is solved.

``````//swap 2 blocks of data in an array.
vector<int> block_swap(vector<int> arr, size_t i, size_t j, size_t len)
{
assert(len && (i + len <= j || j + len <= i));
for (size_t k = 0; k < len; ++k)
swap(arr[i + k], arr[j + k]);
return arr;
}

//check if array is ascending ordered.
bool sorted(const vector<int> & arr)
{
for (size_t i = 1; i < arr.size(); ++i){
if (arr[i - 1] > arr[i])
return false;
}
return true;
}

//compute hash value of current permutation.
unsigned long myhash(const vector<int> & arr)
{
unsigned long ret = 0;
for (int v : arr)
ret = ret * 199 + v;
return ret;
}

struct Node
{
Node * parent;   //where does this node come from.
vector<int> arr; //what is the permutation this node stands for.
Node(const vector<int> & a = {}, Node * np = nullptr) : parent(np), arr(a){}
bool sorted() const{ return ::sorted(arr); }
Node * generate();
void print() const{
if (parent)
parent->print();
for(int v : arr)
cout<< v <<' ';
cout<<endl;
}
};

list<Node> tree;
unordered_map < unsigned long, vector<list<Node>::iterator>> save;

//BFS the next permutations
Node * Node::generate() {
if (sorted())
return this;
for (size_t nl = 1; nl <= arr.size() / 2; ++nl){
for (size_t ni = 0; ni + nl <= arr.size(); ++ni){
for (size_t nj = ni + nl; nj + nl <= arr.size(); ++nj){
bool found = false;
vector<int> na(block_swap(arr, ni, nj, nl));
auto wh = save.find(myhash(na));
if (wh != save.end()){
for (auto it : wh->second){
if (it->arr == na){
found = true;
break;
}
}
}
if (!found){
tree.emplace_back(move(na), this);
if (tree.back().sorted())
return &tree.back();
}
}
}
}
return nullptr;
}

// find minimum block swaps to sort the array
void block_swap_sort(vector<int> arr)
{
tree.emplace_back(arr);
save[myhash(arr)].push_back(tree.begin());
for (auto it = tree.begin();it != tree.end(); ++it){
const Node * const n = it->generate();
if (n){
n->print();
break;
}
}
}

void test()
{
block_swap_sort({ 4, 1, 2, 5, 6, 3 });
/*
4 1 2 5 6 3
4 5 6 1 2 3
1 2 3 4 5 6
*/

block_swap_sort({ 3, 6, 9, 2, 1, 10, 4, 5, 7, 8 });
/*
3 6 9 2 1 10 4 5 7 8
3 9 6 2 1 10 4 5 7 8
3 9 10 4 5 6 2 1 7 8
1 7 8 4 5 6 2 3 9 10
1 2 3 4 5 6 7 8 9 10
*/
}

int main()
{
srand((unsigned int)time(NULL));
test();
}``````

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

Maybe this is actually the answer they were looking for. It definitely finds the minimum number of swaps to sort the array. They didn't ask to sort the array in the minimum number of swaps.

My current algorithm sorts most arrays in the fewest swaps but fails miserably on some contrived arrays (specifically the two examples you list).

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

count the number occurrences during merge stage of mergesort where the elements of left array is greater than the elements of right array.

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

If you're counting individual swaps this will not work. I take it you're counting the number of occurrences when the minimum element from the left array is larger than the maximum element from the right array?

Do you have proof that this will always return the correct number (especially since merge sort doesn't always merge same-sized arrays)?

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

Even that won't work. Take 876321.

With merge sort:
78 36 12 -> 3x min-left is larger than max-right
3678 12 -> 1x
123678 -> 1x = 5x total

Optimal = 3x:
176328
126378
123678

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

ff

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

1. do sub array can be of length = 1?
2. sub arrays are to be selected randomly or we can have any particular sequence?

if we can have sub array of length = 1 , then this problem can be easily modified to get total number of swaps taking place sorting algo like bubble sort.
minimum swaps = nlogn for sub array length 1 .

this soln is based on too much of hypothesis!!

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

This works

``````struct SPart
{
int start;
int size;
};

struct SSwap
{
int x, y, size;
};

static bool is_closer_larger(const std::vector<int>& items, size_t nStart, int nValue, int nLargerValue)
{
if(nLargerValue > nValue)
{
const int nDiff = nLargerValue - nValue;
for(size_t x = nStart, n = items.size(); x < n; ++x)
{
const int v = items[x];
if(v > nValue && (v - nValue) < nDiff)
return true;
}
}
return false;
}

bool do_sort(std::vector<int>& items)
{
do
{
// break up into sorted subarrays
std::vector< SPart > subarrays;

SPart part;
part.start = 0;
part.size  = 1;
for(size_t x = 1, n = items.size(); x < n; ++x)
{
if(items[x] >= items[x-1]
&& !is_closer_larger(items, x+1, items[x-1], items[x])
)
{
++part.size;
}
else
{
subarrays.push_back(part);
part.start = x;
part.size  = 1;
}
if(x == n - 1)
subarrays.push_back(part);
}

// all one subarray, so everything is sorted
if(subarrays.size() == 1)
break;

std::vector<SSwap> swappableRanges;

for(int x = 0, xn = subarrays.size(); x < xn; ++x)
{
for(int y = x+1, yn = subarrays.size(); y < yn; ++y)
{
if(x == y)
continue;
else if(y < x)
{
// this comes before subarray x
const int vY = items[subarrays[y].start + subarrays[y].size - 1];
const int vX = items[subarrays[x].start + subarrays[x].size - 1];
if(vY > vX)
{
// subarray is out of order
SSwap swappableSubarrays;
swappableSubarrays.x = x;
swappableSubarrays.y = y;
swappableSubarrays.size = std::min(subarrays[x].size, subarrays[y].size);
swappableRanges.push_back(swappableSubarrays);
}
}
else if(x < y)
{
// this comes after subarray x
const int vY = items[subarrays[y].start + subarrays[y].size - 1];
const int vX = items[subarrays[x].start + subarrays[x].size - 1];
if(vY < vX)
{
// subarray is out of order
SSwap swappableSubarrays;
swappableSubarrays.x = x;
swappableSubarrays.y = y;
swappableSubarrays.size = std::min(subarrays[x].size, subarrays[y].size);
swappableRanges.push_back(swappableSubarrays);
}
}
}
}
if(!swappableRanges.size())
{
return false; // failed within constraints
}
// get largest pair
SSwap *pMax = &swappableRanges[0];
for(size_t x = 1, n = swappableRanges.size(); x < n; ++x)
{
if(swappableRanges[x].size > pMax->size)
pMax = &swappableRanges[x];
}
for(size_t x = 0; x < (size_t)pMax->size; ++x)
{
std::swap(items[subarrays[pMax->x].start+x], items[subarrays[pMax->y].start+x]);
}
} while(1);
return true;
}

#if 1
int main()
{
const int vars[] = { 11, 12, 13, 6, 7, 8, 1, 2, 3, 15, 16, 9, 10 };
//const int vars[] = { 6, 7, 8, 1, 2, 3 };
std::vector<int> items;
items.reserve(sizeof(vars)/sizeof(vars[0]));
for(int x = 0; x < sizeof(vars)/sizeof(vars[0]); ++x)
items.push_back(vars[x]);
bool rc = do_sort(items);
printf("%s: ", rc ? "SUCCESS" : "FAILED");
for(size_t x = 0; x < items.size(); ++x)
printf("%d ", items[x]);
printf("\n");
getchar();
return(0);
}
#endif``````

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

can you write the logic in plain text?

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

can you write logic in plain text?

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

Dude without explanation of logic, pages of code is just garbage.

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

Ok, this works and return minimum swaps

``````struct SPart
{
int start;
int size;
};

struct SSwap
{
int x, y, size;
int startX;
int startY;
};

static bool is_closer_larger(const std::vector<int>& items, size_t nStart, int nValue, int nLargerValue)
{
if(nLargerValue > nValue)
{
const int nDiff = nLargerValue - nValue;
for(size_t x = nStart, n = items.size(); x < n; ++x)
{
const int v = items[x];
if(v > nValue && (v - nValue) < nDiff)
return true;
}
}
return false;
}

int do_sort(std::vector<int>& items)
{
int nPasses = 0;
do
{
// break up into sorted subarrays
std::vector< SPart > subarrays;

SPart part;
part.start = 0;
part.size  = 1;
for(size_t x = 1, n = items.size(); x < n; ++x)
{
if(items[x] >= items[x-1]
&& !is_closer_larger(items, x+1, items[x-1], items[x])
)
{
++part.size;
}
else
{
subarrays.push_back(part);
part.start = x;
part.size  = 1;
}
if(x == n - 1)
subarrays.push_back(part);
}

// all one subarray, so everything is sorted
if(subarrays.size() == 1)
break;

std::vector<SSwap> swappableRanges;

for(int x = 0, xn = subarrays.size(); x < xn; ++x)
{
for(int y = x+1, yn = subarrays.size(); y < yn; ++y)
{
if(x == y)
continue;
else if(y < x)
{
// this comes before subarray x
const int vY = items[subarrays[y].start + subarrays[y].size - 1];
const int vX = items[subarrays[x].start + subarrays[x].size - 1];
if(vY > vX)
{
// subarray is out of order
SSwap swappableSubarrays;
swappableSubarrays.x = x;
swappableSubarrays.y = y;
swappableSubarrays.size   = std::min(subarrays[x].size, subarrays[y].size);
swappableSubarrays.startX = items[subarrays[x].start];
swappableSubarrays.startY = items[subarrays[y].start];
swappableRanges.push_back(swappableSubarrays);
}
}
else if(x < y)
{
// this comes after subarray x
const int vY = items[subarrays[y].start + subarrays[y].size - 1];
const int vX = items[subarrays[x].start + subarrays[x].size - 1];
if(vY < vX)
{
// subarray is out of order
SSwap swappableSubarrays;
swappableSubarrays.x = x;
swappableSubarrays.y = y;
swappableSubarrays.size   = std::min(subarrays[x].size, subarrays[y].size);
swappableSubarrays.startX = items[subarrays[x].start];
swappableSubarrays.startY = items[subarrays[y].start];
swappableRanges.push_back(swappableSubarrays);
}
}
}
}
if(!swappableRanges.size())
{
return -1; // failed within constraints
}

// get largest pair
SSwap *pMax = &swappableRanges[0];
// do swap with min value on right side
for(size_t x = 1, n = swappableRanges.size(); x < n; ++x)
{
if(swappableRanges[x].startY < pMax->startY)
{
pMax = &swappableRanges[x];
}
else if(swappableRanges[x].startY == pMax->startY && swappableRanges[x].startX > pMax->startX)
{
pMax = &swappableRanges[x];
}
}
for(size_t x = 0; x < (size_t)pMax->size; ++x)
{
std::swap(items[subarrays[pMax->x].start+x], items[subarrays[pMax->y].start+x]);
}
++nPasses;
} while(1);
return nPasses;
}
#if 1
int main()
{
//const int vars[] = { 6, 7, 8, 1, 2, 3 };
//const int vars[] = { 11, 12, 13, 6, 7, 8, 1, 2, 3 };
const int vars[] = { 11, 12, 13, 6, 7, 8, 1, 2, 3, 15, 16, 9, 10 };
/* min passes: 5
1 2 3 6 7 8 11 12 13 15 16 9 10	// 1
1 2 3 6 7 8 9 10 13 15 16 11 12 // 2
1 2 3 6 7 8 9 10 11 12 16 13 15 // 3
1 2 3 6 7 8 9 10 11 12 13 16 15 // 4
1 2 3 6 7 8 9 10 11 12 13 15 16 // 5
*/

std::vector<int> items;

items.reserve(sizeof(vars)/sizeof(vars[0]));
for(int x = 0; x < sizeof(vars)/sizeof(vars[0]); ++x)
items.push_back(vars[x]);

int nPasses = do_sort(items);

//int nPasses = minSwaps(items); bool rc = true;

printf("Passes: %d, %s: ", nPasses, nPasses >= 0 ? "SUCCESS" : "FAILED");
for(size_t x = 0; x < items.size(); ++x)
printf("%d ", items[x]);
printf("\n");
getchar();
return(0);
}
#endif``````

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

Hard to tell what the intent is without better documentation, but this algorithm does not give the minimum swaps for the list {4,1,2,5,6,3}.
{4,1,2,5,6,3} ->{5,6,3,4,1,2}-> {1,2,3,4,5,6}

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

Refer to Timsort in Wiki.

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

This is the best answer so far. Everything else is incorrect

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

second that

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

Couple of questions.
1. Will array always have even number of elements ?
2. Will array always have only 2 sorted sets that are rotated ?

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

I am not sure about the minimum number of operations but seems to be efficient solution.
Logic : find the max element in each operation and perform that swap such that maximum element goes to the end.
Do this operation N times reducing array size each time by one and aiming to have max element in each operation.
It doesn't necessary to have N swaps. It performs swaps only if the max element is not in its place.
T = O(n2)

Code
------------

``````#include <iostream>
using namespace std;

void swaparr(int a[],int l,int r,int n) {
for(int i=l,j=r;i<=l+n&&j<=r+n;i++,j++)
swap(a[i],a[j]);
}
int findMax(int a[],int n) {
int index = 0;
for(int i=1;i<=n;i++)
if(a[i] > a[index])
index = i;
return index;
}
void sort(int a[],int n) {
for(int r=n-1;r>0;r--) {
int index = findMax(a,r);
if(index != r) {
int l = min(r-index-1,index);
swaparr(a,index-l,r-l,l);
}
}
}
int main() {
int a[] = {7,23,8,234,3,6,41,334};
int n = 8;
sort(a,n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}``````

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

``````#include <iostream>
using namespace std;

void swaparr(int a[],int l,int r,int n) {
for(int i=l,j=r;i<=l+n&&j<=r+n;i++,j++)
swap(a[i],a[j]);
}
int findMax(int a[],int n) {
int index = 0;
for(int i=1;i<=n;i++)
if(a[i] > a[index])
index = i;
return index;
}
void sort(int a[],int n) {
for(int r=n-1;r>0;r--) {
int index = findMax(a,r);
if(index != r) {
int l = min(r-index-1,index);
swaparr(a,index-l,r-l,l);
}
}
}
int main() {
int a[] = {7,23,8,234,3,6,41,334};
int n = 8;
sort(a,n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}``````

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

Bubble sort get n swaps; and a modified merge sort get O(log n) swaps.

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

So if you look at the displacement (positive or negative) each element is from its sorted position, the minimum number of swaps becomes the minimum number of operations to get each displacement to 0.

An operation is defined by: given two groups A and B of size n, adding n to all displacements of one group and subtracting n from all displacements of the other group. The groups can overlap, because the overlapping areas get canceled out by the +n and -n.

Given this, I'm still not sure how to solve for the minimum number of swaps, but it might help to look at the problem from this perspective.

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

``````public int minSwaps(int nums[]) {
if (nums == null) {
return Integer.MIN_VALUE;
}
int k = 1, swap = 0;
int length = nums.length - 1;
for (int i = 0; i <= length; i += k) {
if (nums[i + 1] > nums[i]) {
k++;
} else {
int j = (i + k) > length ? length : i + k;
while ((j > k) && (nums[j] > nums[--j]));
if (j > i) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
swap++;
}
k = j;
}
}
return swap;
}``````

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

``````public int minSwaps(int nums[]) {
if (nums == null) {
return Integer.MIN_VALUE;
}
int k = 1, swap = 0;
int length = nums.length - 1;
for (int i = 0; i <= length; i += k) {
if (nums[i + 1] > nums[i]) {
k++;
} else {
int j = (i + k) > length ? length : i + k;
while ((j > k) && (nums[j] > nums[--j]));
if (j > i) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
swap++;
}
k = j;
}
}
return swap;
}``````

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.