Google Interview Question Software Engineers
Country: UK
Interview Type: Phone Interview
We need to take care of the zero inside the loop.
void change(arr &A,arr &B){
int zero=find(A.begin(),A.end(),0)-A.begin();
if(zero==B.size())
return ;
for(int i=0;i<A.size();i++){
if(A[i]!=B[i]){
int j=find(A.begin(),A.end(),B[i])-A.begin();
if(B[i]==0){
swap(A[i],A[j]);
zero=i;
continue;
}//end if
swap(A[i],A[zero]);
swap(A[i],A[j]);
swap(A[zero],A[j]);
}//end if
}//end for
}//end change
Simple O(n) time, O(n) memory
#include <iostream>
#include <vector>
using namespace std;
void Swap(vector<int> &v, int i, int j) {
int temp = v[i];
v[i] = v[j];
v[j] = temp;
}
int convert(vector<int>& a, vector<int>& b) {
int swapCount = 0;
int size = a.size();
if (size <= 1)
return swapCount;
vector<int> indexes(size);
int k = -1;
for (int i = 0; i < size; ++i) {
indexes[a[i]] = i;
if (a[i] == 0)
k = i;
}
for (int i = 0; i < size; ++i) {
if (a[i] != b[i]) {
int j = indexes[b[i]];
Swap(a, k, i);
Swap(indexes, a[k], a[i]);
Swap(a, i, j);
Swap(indexes, a[i], a[j]);
k = j;
swapCount += 2;
}
}
return swapCount;
}
int main() {
vector<int> A = {1, 4, 3, 0, 2};
vector<int> B = {2, 3, 0, 1, 4};
cout << "Swap Count = " << convert(A, B) << endl;
for (int i = 0; i < A.size(); ++i)
cout << A[i] << ' ';
cout << endl;
return 0;
}
void swap(int *a,int i,int j){
printf("Do Swap %d with %d\n",a[i],a[j]);
if(a[i]==0){a[i]=a[j];a[j]=0;}
else if(a[j]==0){a[j]=a[i];a[i]=0;}
else{
printf("Invlid swap(%d,%d)",a[i],a[j]);
}
}
void SwapAtoBWhenOneZero(int *a,int *b,int n){
// build reverse index of Array A
int RevIndex[n];
for(int i=0;i<n;i++) {RevIndex[a[i]] = i;}
for(int k=0;k<n;k++){ //let's place a[k] in proper place
//a[k] shoud be b[k] and it is so continue..
if(a[k]== b[k]){continue;}
//yes.. Now we have a mismatch and b[k] shoud be in place of a[k]
// where is b[k] in array a ?we can found it from RevIndex[b[k]] ..
int target_idx = RevIndex[b[k]];// it return the index.
if( a[target_idx] == 0 || a[k] == 0){ // is that element is Zero.. Ok.. yes.. so swap is possible..
swap(a,k,target_idx);
}
else{ // direct swap is not possible bcz atleast one elemnt shoud be zero..
// swap using zero-th index...
int zero_idx = RevIndex[0];
swap(a,zero_idx,target_idx);
swap(a,k,target_idx);
swap(a,zero_idx,k);
}
// reConstract Index
for(int i=0;i<n;i++) {RevIndex[a[i]] = i;}
}
}
int main(){
int a[] = {1, 3, 2, 4, 0};
int b[] = { 4, 0, 3, 2, 1};
SwapAtoBWhenOneZero(a,b,5);
}
>>> Compiling...
Compiled succesully with warning
>>> Running...
Do Swap 0 with 4
Do Swap 1 with 0
Do Swap 4 with 0
Do Swap 3 with 0
Do Swap 0 with 3
Do Swap 2 with 0
Do Swap 3 with 0
Do Swap 0 with 2
Do Swap 1 with 0
Do Swap 2 with 0
function swap(A, B) {
var hashTable = {};
var i;
for (i = A.length - 1; i >-1; i--) {
hashTable[A[i]] = i;
}
console.log(A, B);
for (i = 0; i < B.length; ++i) {
if (A[i] === B[i]) continue;
if (i !== hashTable[0])
swp(A, hashTable[0], i, hashTable);
swp(A, i, hashTable[B[i]], hashTable);
}
console.log(A, B);
}
function swp(A, i, j, table) {
console.log('swap A[' + i + '] = ' + A[i] + ' for A[' + j + '] = ' + A[j]);
var tmp = A[i];
A[i] = A[j]
A[j] = tmp;
table[A[j]] = j;
table[A[i]] = i;
}
swap([1, 0, 2,3,4], [2,1,3, 0, 4]);
swap([5,4,3,2,1,0], [0,1,2,3,4,5]);
//Output
[ 1, 0, 2, 3, 4 ] [ 2, 1, 3, 0, 4 ]
swap A[1] = 0 for A[0] = 1
swap A[0] = 0 for A[2] = 2
swap A[2] = 0 for A[3] = 3
[ 2, 1, 3, 0, 4 ] [ 2, 1, 3, 0, 4 ]
[ 5, 4, 3, 2, 1, 0 ] [ 0, 1, 2, 3, 4, 5 ]
swap A[5] = 0 for A[0] = 5
swap A[0] = 0 for A[0] = 0
swap A[0] = 0 for A[1] = 4
swap A[1] = 0 for A[4] = 1
swap A[4] = 0 for A[2] = 3
swap A[2] = 0 for A[3] = 2
swap A[3] = 0 for A[4] = 3
swap A[4] = 0 for A[0] = 4
[ 0, 1, 2, 3, 4, 5 ] [ 0, 1, 2, 3, 4, 5 ]
While iterating through A use a look up table to figure out the indices of the elements to be swapped.
Algorithm (pseudocode):
Build a look up table LUT from the array A mapping a value to its position in the array A
Iterate through the array A{
If value at current index I is misplaced then{
Find the index J of the element which should be placed at the current index I
If A[I] == 0 or A[J] == 0 then{
Do one swap between A[I] and A[J]
}Else{
Find the position of zero K
Do three swaps between A[I], A[J] & A[K]
}
Update the LUT
}
}
Code (Python):
def reorder(a, b):
# Check input
if len(a) != len(b):
print('Mismatched array length')
return
print('A = %s' % str(a))
print('B = %s' % str(b))
N = len(a)
# Building LUT
lut = N * [None]
for i in range(N):
lut[a[i]] = i
print('LUT = %s' % str(lut))
# Reordering
for i in range(N):
impostor = a[i]
expected = b[i]
if impostor != expected:
j = lut[expected]
if 0 in [expected, impostor]:
print('Swapping %d and %d' % (i, j))
else:
print('Swapping %d and %d through %d' % (i, j, lut[0]))
a[j] = impostor
a[i] = expected
lut[impostor] = j
lut[expected] = i
print('A = %s' % str(a))
reorder([1, 3, 2, 4, 0], [4, 0, 3, 2, 1])
In Java:
public static void main(String[] args) {
int[] order = new int[]{1,2,6,5,4,9,8,0,3,7};
int[] data = new int[]{2,9,8,1,0,3,6,5,4,7};
System.out.println(Arrays.toString(data));
//this keeps track of the index in data where the ith number is
int[] whereIsInData = new int[data.length];
for (int i = 0; i < data.length; i++) {
whereIsInData[data[i]] = i;
}
System.out.println(Arrays.toString(whereIsInData) +"\n");
int zeroIndx = whereIsInData[0];
for (int i = 0; i < data.length; i++) {
int numberThatShouldBeAtIthPosition = order[i];
int originalNumberAtIthPosition = data[i];
// System.out.println(Arrays.toString(data));
swap(data,zeroIndx,i);
// System.out.println(Arrays.toString(data));
swap(data, i, whereIsInData[numberThatShouldBeAtIthPosition]);
// System.out.println(Arrays.toString(data));
swap(data,whereIsInData[numberThatShouldBeAtIthPosition],zeroIndx);
System.out.println("---------------");
System.out.println(Arrays.toString(data));
swap(whereIsInData,numberThatShouldBeAtIthPosition,originalNumberAtIthPosition);
}
System.out.println("Solution: ");
System.out.println(Arrays.toString(data));
}
public static void swap(int[] data, int from, int to){
int tmp = data[to];
data[to] = data[from];
data[from]=tmp;
}
python solution:
def swap_val(x, rev_x, p, q):
p_pos = rev_x[p]
q_pos = rev_x[q]
rev_x[p] = q_pos
rev_x[q] = p_pos
x[q_pos] = p
x[p_pos] = q
def build_reverse_index(x):
res = {}
for i, e in enumerate(x):
res[e] = i
return res
def f(a, b):
rev_a = build_reverse_index(a)
rev_b = build_reverse_index(b)
unsorted = set([])
for k,v in rev_a.items():
if (v != rev_b[k]) and (k!= 0):
unsorted.add(k)
while len(unsorted) != 0:
if rev_a[0] == rev_b[0]:
q = unsorted.pop()
unsorted.add(q)
swap_val(a, rev_a, 0, q)
r = b[rev_a[0]]
swap_val(a, rev_a, 0, r)
unsorted.remove(r)
#main
#a = [1,0,3,5,2,4]
a = [1,5,3,0,2,4]
b = [4,0,1,3,5,2]
f(a,b)
print a
print b
{{
void swap(int *a,int i,int j){
printf("Do Swap %d with %d\n",a[i],a[j]);
if(a[i]==0){a[i]=a[j];a[j]=0;}
else if(a[j]==0){a[j]=a[i];a[i]=0;}
else{
printf("Invlid swap(%d,%d)",a[i],a[j]);
}
}
void SwapAtoBWhenOneZero(int *a,int *b,int n){
// build reverse index of Array A
int RevIndex[n];
for(int i=0;i<n;i++) {RevIndex[a[i]] = i;}
for(int k=0;k<n;k++){ //let's place a[k] in proper place
//a[k] shoud be b[k] and it is so continue..
if(a[k]== b[k]){continue;}
//yes.. Now we have a mismatch and b[k] shoud be in place of a[k]
// where is b[k] in array a ?we can found it from RevIndex[b[k]] ..
int target_idx = RevIndex[b[k]];// it return the index.
if( a[target_idx] == 0 || a[k] == 0){ // is that element is Zero.. Ok.. yes.. so swap is possible..
swap(a,k,target_idx);
}
else{ // direct swap is not possible bcz atleast one elemnt shoud be zero..
// swap using zero-th index...
int zero_idx = RevIndex[0];
swap(a,zero_idx,target_idx);
swap(a,k,target_idx);
swap(a,zero_idx,k);
}
// reConstract Index
for(int i=0;i<n;i++) {RevIndex[a[i]] = i;}
}
}
int main(){
int a[] = {1, 3, 2, 4, 0};
int b[] = { 4, 0, 3, 2, 1};
SwapAtoBWhenOneZero(a,b,5);
}
>>> Compiling...
Compiled succesully with warning
>>> Running...
Do Swap 0 with 4
Do Swap 1 with 0
Do Swap 4 with 0
Do Swap 3 with 0
Do Swap 0 with 3
Do Swap 2 with 0
Do Swap 3 with 0
Do Swap 0 with 2
Do Swap 1 with 0
Do Swap 2 with 0
}}
void swap(int *a,int i,int j){
printf("Do Swap %d with %d\n",a[i],a[j]);
if(a[i]==0){a[i]=a[j];a[j]=0;}
else if(a[j]==0){a[j]=a[i];a[i]=0;}
else{
printf("Invlid swap(%d,%d)",a[i],a[j]);
}
}
void SwapAtoBWhenOneZero(int *a,int *b,int n){
// build reverse index of Array A
int RevIndex[n];
for(int i=0;i<n;i++) {RevIndex[a[i]] = i;}
for(int k=0;k<n;k++){ //let's place a[k] in proper place
//a[k] shoud be b[k] and it is, so continue..
if(a[k]== b[k]){continue;}
//yes.. Now we have a mismatch and b[k] shoud be in place of a[k]
// where is b[k] in array A ?we can found it from RevIndex[b[k]] ..
int target_idx = RevIndex[b[k]];// it return the index.
if( a[target_idx] == 0 || a[k] == 0){ // is that element is Zero.. Ok.. yes.. so swap is possible..
swap(a,k,target_idx);
}
else{ // direct swap is not possible bcz atleast one elemnt shoud be zero..
// swap using zero-th index...
int zero_idx = RevIndex[0];
swap(a,zero_idx,target_idx);
swap(a,k,target_idx);
swap(a,zero_idx,k);
}
// reConstract revese Index
for(int i=0;i<n;i++) {RevIndex[a[i]] = i;}
}
}
int main(){
int a[] = {1, 3, 2, 4, 0};
int b[] = { 4, 0, 3, 2, 1};
SwapAtoBWhenOneZero(a,b,5);
}
>>> Compiling...
Compiled succesully with warning
>>> Running...
Do Swap 0 with 4
Do Swap 1 with 0
Do Swap 4 with 0
Do Swap 3 with 0
Do Swap 0 with 3
Do Swap 2 with 0
Do Swap 3 with 0
Do Swap 0 with 2
Do Swap 1 with 0
Do Swap 2 with 0
This solution is optimized under the assumption that comparisons are very cheap and swaps are very expensive. I do a few more comparisons then are strictly necessary but I think this does the minimal number of swaps.
// Reorder.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <assert.h>
void swap(int * data, int i, int j)
{
printf("swap [%i] %i, [%i] %i\n", i, data[i], j, data[j]);
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}//----------------------------------------------------------------------------------------
int find(int *data, int l , int x)
{
for (int i = 0; i < l; i++)
{
if (data[i] == x)
{
return i;
}
}
assert(false);
return -1;
}//----------------------------------------------------------------------------------------
int swap_step(int *a, int *b, int l, int i) // returns new position of 0
{
assert(a[i] == 0);
int v = b[i];
int j = find(a, l, v);
swap(a, i, j);
return j;
}//----------------------------------------------------------------------------------------
int find_first_out_of_place(int *a, int *b, int l) // returns -1 if all are in place
{
for (int i = 0; i < l; i++)
{
if (a[i] != b[i])
{
return i;
}
}
return -1;
}//----------------------------------------------------------------------------------------
void dump(int * data, int l)
{
for (int i = 0; i < l; i++)
{
printf("%i ", data[i]);
}
printf("\n");
}//----------------------------------------------------------------------------------------
void swapper_sort(int *a, int *b, int l)
{
dump(a, l);
dump(b, l);
int z = find(a, l, 0);
while (true)
{
int i = find_first_out_of_place(a, b, l);
if (i == -1)
{
dump(a, l);
dump(b, l);
return; // a == b we are done
}
if (z == i) // b[z] if the first one that is in the wrong place
{
i = find_first_out_of_place(a + z + 1, b + z + 1, l - z - 1); // find another one (and there will be one)
i = i + z + 1;
}
if (a[z] == b[z]) // the 0 is in the correct place we are going to have to move it bacuase we need to use it as a temp
{
swap(a, z, i);
dump(a, l);
z = i;
}
while (a[z] != b[z])
{
z = swap_step(a, b, l, z);
}
}
}//----------------------------------------------------------------------------------------
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = { 1, 3, 2, 4, 0 };
int b[] = { 4, 0, 3, 2, 1 };
swapper_sort(a, b, 5);
return 0;
}//----------------------------------------------------------------------------------------
None of above solutions talked about the minimal swaps. This solution has O(N) computation complexity and O(N) space complexity and guarantees minimal swaps as M-1/M+1. M is the edit distance between A and B, assuming each element as a single character as if in a string.
Here is the pseduo-cdoe,
- 1. Extract out the different elements into the edit distance list
- 2. Check if 0 is appearing in edit distance list
- 2.1 If not, swap 0 with one of element in the edit distance and add it into this list
- 3. From the list look at the location of element "0".
- 4. Find out the value x in B at the same location
- 5. Swap 0 with x in the edit distance list (in A)
- 6. Remove x from the edit distance list
- 7. Repeat last 5 steps until exhaust the edit distance list
Following this: cpluspluslearning-petert.blogspot.co.uk/2015/04/data-structure-and-algorithm-minimal.html, for more details - the reasoning and logic.
The idea is to use a hashmap to help get the index of the target value in B. Each time when A[i] is not equal to B[i], we must need to swap, if A[i] is already 0, then we just need to swap 0 and B[i] in A, otherwise, use 0 to help. The solution should be O(n).
public void solve(int[] A, int[] B, int n) {
// use a map to track the index of a value
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
map.put(A[i], i);
}
for (int i = 0; i < n; i++) {
if (A[i] != B[i]) {
if (A[i] != 0) {
swap(A, i, map.get(0), map);
}
swap(A, i, map.get(B[i]), map);
}
}
}
void swap(int[] A, int i, int j, Map<Integer, Integer> map) {
System.out.format("%d <-> %d\n", A[i], A[j]);
map.put(A[i], j);
map.put(A[j], i);
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
/*
Sample input
4
1 2 4 3
3 2 1 4
*/
#include <iostream>
#include <stdio.h>
using namespace std;
void Convert(int* a, int* b, int N){
int* m_a = new int[N+1];
for(int i=0; i<N; i++) {
m_a[a[i]] = i;
}
for(int i=0; i<N; i++){
if(a[i] == b[i]) continue;
int j = m_a[b[i]];
printf("Swap %dth %d with %dth %d\n", i, a[i], j, a[j]);
int tmp = a[j];
a[j] = a[i];
a[i] = tmp;
m_a[a[j]] = j;
}
delete [] m_a;
}
int main() {
freopen("input.txt", "r", stdin);
int N;
scanf("%d", &N);
int* a = new int[N];
int* b = new int[N];
for(int i=0; i<N; i++) scanf("%d", &a[i]);
for(int i=0; i<N; i++) scanf("%d", &b[i]);
Convert(a, b, N);
delete [] a;
delete [] b;
return 0;
}
O(n) solution
public int[] sortArrays(int[]A, int[]B){
Hashtable<Integer,Integer>map=new Hashtable<Integer,Integer>();
for(int i=0;i<A.length;i++){
map.put(new Integer(A[i]), new Integer(i));
}
for(int i=0;i<B.length;i++){
if(A[i]==B[i]){
continue;
}else{
swap(A,A[i],0,map);
swap(A,A[i],B[i],map);
}
}
return A;
}
private void swap(int[]A, int i, int j, Hashtable<Integer,Integer> map){
int iIdx=map.get(new Integer(i)).intValue();
int jIdx=map.get(new Integer(j)).intValue();
A[iIdx]=j;
A[jIdx]=i;
map.put(new Integer(i), new Integer(jIdx));
map.put(new Integer(j), new Integer(iIdx));
}
Idea is to keep finding values in B that differ in A and swap these values in B to make them the same as in A. Do this until no values differ.
To swap B[i] with B[j] using B[k] (value 0)
- swap B[i] with B[k] // Place B[i] into temp location
- swap B[k] with B[j] // Place B[j] into location i
- swap B[j] with B[i] // Place B[i] into location j
After these 3 swaps, the value 0 will end up at the same index k it started in.
- JW March 24, 2015void equalize(int [] A, int [] B) { int k = -1; // Find index of value 0 in B, let this be k for (int i = 0; i < B.length; i++) { if (B[i] == 0) { k = i; } } for (int i = 0; i < A.length; i++) { if (B[i] != A[i]) { int j = findValue(B, A[i]); // Find index of value A[i] in B, let this be j swap(B, i, k); swap(B, k, j); swap(B, j, i); } } }