Adobe Interview Question
Software EngineersCountry: United States
int SwapCount(int A[], int B[], int size)
{
int j = 0;
int minSwapCount = 0;
for(int i =0; i < size; i++)
{
if(A[i] == 1)
{
while(B[j] !=1)
{
j++;
}
if(i > j)
minSwapCount += i - j;
else
minSwapCount += j - i;
j++;
}
}
return minSwapCount;
}
int main()
{
int A[] = {1,0,0,1};
int B[] = {0,1,1,0};
printf("SwapCount = %d", SwapCount(9, 6));
return 0;
}
int minSwaps(int A[], int B[], int n)
{
assert(A != NULL && B != NULL && n > 0);
int ans = 0, rb = 1;
for (int i = 0; i < n; ++i)
{
if (A[i] != B[i])
{
if (rb <= i) rb = i + 1;
while (rb < n && A[rb] != B[i]) ++rb;
if (rb >= n) throw logic_error("there is no solution");
ans += rb - i; A[rb] = A[i]; ++rb;
}
}
return ans;
}
void findMInSwapBinary(int binArr1[n],int binArr2[n])
{
int minSwaps =0;
for(int i=0;i<n;i++)
{
if(binArr1[i] ^ binArr2[i]==1)
minSwaps++;
}
return;
}
Your logic does not work on this.
eg. arr1[]={1,1,1,0,0,0}
arr2[]={1,0,1,0,1,0}
You output would result 2
Correct answer is 3.
O(1) solution .....
int numOfSwaps(int x, int y){
int tmp = x ^ y;
return NumberOfSetBits(tmp);
}
int NumberOfSetBits(int i)
{
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
O(1) solution ....
int countSwaps(int x, int y){
int tmp = x ^ y;
return numberOfSetBits(tmp);
}
int numberOfSetBits(int i)
{
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
sv, The answer would have been 2 if we were not given the condition of adjacent swapping only. Since we can only swap two adjacent elements, minimum swaps will be 3.
void findMInSwapBinary(int binArr1[n],int binArr2[n])
{
int minSwaps =0;
for(int i=0;i<n;i++)
{
if(binArr1[i] ^ binArr2[i]==1)
minSwaps++;
}
return;
}
XOR the numbers, then see how many 1s there are in this value
Reasoning:
We know that a ^ a = 0 , so 1 ^ 1 = 0 and 0 ^ 0 = 0
But, 1 ^ 0 = 1 and 0 ^1 = 1, so we see that we can find differences by xoring
Some code:
int numSwaps(int a, int b) {
int c = a ^ b;
int output = 0;
while (c != 0) {
out += c & 1;
c =>> 1;
}
return out;
}
This one works, but given the answer size there might be an easier solution or this is not an interview question.
public static void main(String[] args) throws Exception {
Random rseed = new Random();
int seed = rseed.nextInt(100);
System.out.println("seed = " + seed);
Random r = new Random(seed);
int size = 10;
int[] orig;
int[] dest = new int[size];
for (int i = 0; i < dest.length; i++) {
dest[i] = r.nextInt(3)==1? 1 : 0;
}
orig = dest.clone();
for (int i = 0; i < dest.length-1; i++) {
int tmp = orig[i];
int destIndx = i + r.nextInt(size-i-1);
orig[i] = orig[destIndx];
orig[destIndx] = tmp;
}
// orig = new int[]{1, 0, 0, 0, 1, 0, 0, 0, 0, 1};
// dest = new int[]{0, 0, 0, 0, 0, 1, 0, 1, 0, 1};
System.out.println("Orig" + Arrays.toString(orig));
System.out.println("Dest"+Arrays.toString(dest));
System.out.println();
System.out.println("Best "+findMinSwaps(orig, dest));
}
private static int findMinSwaps(int[] orig, int[] dest) throws Exception {
int leftDest=0,
leftOrigin=0,
rightOrigin=orig.length-1,
rightDest=orig.length-1;
int swaps = 0;
while(!Arrays.equals(orig,dest)){
//scan left to right
while(leftDest < dest.length && (dest[leftDest]==0 || orig[leftDest]==1) )
leftDest++;
while(leftOrigin< orig.length && (orig[leftOrigin]==0 || dest[leftOrigin]==1))
leftOrigin++;
if(leftDest != dest.length-1 && leftOrigin != dest.length-1 )
swaps+= multipleSwaps(orig,leftOrigin,leftDest);
//scan right to left
while(rightDest>0 && (dest[rightDest]==0 || orig[rightDest]==1))
rightDest--;
while(rightOrigin>0 && (orig[rightOrigin]==0 || dest[rightOrigin]==1) )
rightOrigin--;
if(rightDest != 0 && rightOrigin != 0)
swaps+= multipleSwaps(orig,rightOrigin,rightDest);
leftDest++;
leftOrigin++;
rightDest--;
rightOrigin--;
}
return swaps;
}
private static int multipleSwaps(int[] orig, int from, int to) throws Exception {
if(from == to)
return 0;
int direCtion = (to-from)/Math.abs(to-from);
int swaps =0;
while(from != to){
if(orig[from+direCtion]==1){
swaps+=multipleSwaps(orig,from+direCtion,to);
swap(orig,from,from+direCtion);
System.out.println("Orig" +Arrays.toString(orig));
return swaps+1;
} else {
swap(orig,from,from+direCtion);
System.out.println("Orig" +Arrays.toString(orig));
from+=direCtion;
swaps++;
}
}
return swaps;
}
static void swap(int[] data, int indx1, int indx2) throws Exception {
if(Math.abs(indx1-indx2)!= 1)
throw new Exception("Wrong indexes " + indx1 + " " + indx2);
int tmp = data[indx1];
data[indx1] = data[indx2];
data[indx2] = tmp;
}
The approach is simple:
match the head and for the tail do a swap for desired character to left.
I could not prove it would be lease
- kingKode March 31, 2015