Google Interview Question for Software Engineers


Country: UK
Interview Type: Phone Interview




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

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.

void 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);
        }
    }
}

- JW March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

simple and nice solution!

- Kaidul Islam May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Klaus July 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
}

- thinhdu March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Anonymous March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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 ]

- srterpe May 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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])

- tested.candidate March 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You mention swapping through 0, but where in the code does it use it? looks like you just reorder 1 and 4 directly when i = 0 in your given example, without using lut[0].

- SJag April 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- cornelius March 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jhl March 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{

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

}}

- Dipankar March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- dutta.dipankar08 March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}//----------------------------------------------------------------------------------------

- DR ADM April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- peter tang April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you try the algorithm for sequence 543210 -> 012345

- epavlova April 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Last algorithm is not correct for use case 543210 -> 012345

- EPavlova April 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- jean.timex August 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
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;
}

- diba.bec August 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
		
		
	}

- MAB January 22, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More