Google Interview Question SDE-2s
Country: India
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).
count the number occurrences during merge stage of mergesort where the elements of left array is greater than the elements of right array.
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)?
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!!
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
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
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;
}
#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;
}
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.
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;
}
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;
}
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.
- DoZerg March 30, 2015//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(); }