Google Interview Question Software Engineer / Developers
Country: Australia
Interview Type: Phone Interview
This is a great answer. But here's a possible optimization. In the suggested implementation, you are checking for the next index that doesn't match in each iteration, swapping ZERO in that position, then swapping the correct element for ZERO. So there are 2 swaps per mismatch. I believe 2 swaps are not always necessary.
Instead, you could find ZERO in src and swap the tgt value there. Do this in each iteration. In this case, you are just moving the correct value for ZERO's current position, one swap per incorrectly placed item.
The special case for this is when you swap ZERO into its correct position. In this case, you can't swap the correct number in, because it is already there -- it just happens to be ZERO. Instead, you can swap some other incorrect number into ZERO's position. (just move misplaced number into a different misplaced position -- ZERO's position) In the next iteration after doing this fix, it is guaranteed that you will swap some number into its correct place. So even when this special case occurs, it will still only take 2 swaps to move 1 misplaced number.
I still think your solution is more suitable for answering this question as it is more simple to understand. However, I just wanted to point out that 2 swaps are not necessarily required :)
Could you please clarify on the shortest path. I understand the algorithm, but isn't the size of the problem too large? Can we implement it without extra memory?
If we have N numbers, then N! is the total number of permutations and in this case, vertices.
Good solution. You can use an extra O(n) space to get a solution with O(n) time complexity.
1. In a pre-processing step, go through the "source" array, compute the position of each of the 0 to n elements and store in the auxiliary 'position' array.
2. Start at the heads of both source and target array and compare the elements
3. If the elements are the same or the value of the target array ==0 proceed to the next elements. Otherwise go to step 4
4. Find position of 0 using the 'position' array and swap it with the current element 'e' in the source array and update the positions of 0 and 'e' in the position array. Now swap 0 with the target element(found again using the position array) and after the swap, update their positions in the position array. Advance the pointers of both source and target arrays.
5. Repeat steps 3 & 4 until all the elements are processed.
this can be reduced more with two cases.
1. 0 is in its own position.
2. 0 is not in its own position.
case 1: do as above.
case 2: keep on swapping with correct target until 0 is in its position.
#### Swap using swap_with_0 ###
# Basic Idea is to use indexes to find the element under 0 quickly
def swap(l, begin, end):
tmp = l[begin]
l[begin] = l[end]
l[end] = tmp
def rearrage_swap0(src, tgt):
FREE = 0
src_ind = dict([(a, i) for i, a in enumerate(src)])
tgt_ind = dict([(a, i) for i, a in enumerate(tgt)])
print src
i = src_ind[FREE]
if tgt_ind[FREE] == i:
swap(src, i, i + 1)
src_ind[FREE] = i + 1
src_ind[src[i]] = i
print i, ‘<->’, i + 1, src
while i != tgt_ind[FREE]:
j = src_ind[tgt[i]]
swap(src, i, j)
print i, ‘<->’, j, src
src_ind[src[i]] = i
i = j
I have implemented O(n) time with O(n) space solution and put it down.
Similar to @Murali Mohan comment.
void swap( int *arr, int pos1, int pos2 )
{
std::cout << pos1 << " " << pos2 << std::endl;
int temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}
void swapWith0( int src[], int tgt[], const int n )
{
int *now = new int[n];
int i;
for( i = 0; i < n; i++ )
now[ src[i] ] = i;
do
{
while( tgt[now[0]] != 0 )
swap( now, 0, tgt[now[0]] );
for( i = 0; i < n; i++ )
{
if( tgt[now[i]] != i )
{
swap( now, 0, i );
break;
}
}
}while( i < n );
free( now );
}
1)Make for loop of tgt
2)if ith element of tgt is 0 then contine (skip current iteration) with loop
3)Now find the position of ith element of tgt in src array and store it in say p variable.
4)check if postion found in 3rd step is equal to i?
5)if position is not equal to i than store p found in 3rd step to other variable say p2.
6)do while loop till p2!=i
7)in this while loop check if p2 is equal to p. this will be true for first iteration of while loop
8) if p2==p then replace zero in src array with p th element in src, then store new postion of pth element in p2.
9)if condition checked in step 7 is not true then
10) initialize temp=0;
11) And replace zero in src array with temp th element in src
12) Now replace zero with p2 in src array.
13) after while loop increment temp;
Below is pseudocode
for(int i=0;i<tgt.length;i++){
if(tgt[i]==0){
continue;
}
int position=findPositionOfInSrc(tgt[i])
if(position!=i){
int p2=position;
while(p2!=i){
if(p2==position){
replaceWithZeroInSrc(position);
int p2=findPositionOfInSrc(tgt[i]);
}
else{
replaceWithZeroInSrc(temp);
replaceWithZeroInSrc(p2);
int p2=findPositionOfInSrc(tgt[i]);
}
}
temp++;
}
}
replaceWithZeroInSrc(int position){
int zeroPosition=findZeroPosition(src);
int g=src[position];
src[position]=src[zeroPosition];
src[zeroPosition]=g;
}
public class RearrangeArray
{
public static void main(String[] args)
{
printArray("Soruce", src);
printArray("Target", tgt);
rearrange();
printArray("Achieved", src);
}
static int[] src = { 1, 0, 2, 3, 7, 4, 8, 9 };
static int[] tgt = { 0, 2, 8, 3, 1, 9, 4, 7 };
public static void rearrange()
{
int length = src.length;
int indexInSrc = -1;
int indexOfZeroSrc = -1;
for (int i = 0; i < length; i++)
{
if (tgt[i] != 0 && src[i] != tgt[i])
{
indexOfZeroSrc = findPosition(src, 0);
swapInSrc(indexOfZeroSrc, i);
indexInSrc = findPosition(src, tgt[i]);
swapInSrc(i, indexInSrc);
}
}
}
private static int findPosition(int[] array, int key)
{
for (int i = 0; i < array.length; i++)
{
if (array[i] == key)
{
return i;
}
}
return -1;
}
private static void swapInSrc(int index1, int index2)
{
int temp = src[index1];
src[index1] = src[index2];
src[index2] = temp;
}
public static void printArray(String tag, int[] a)
{
System.out.print(tag + ": ");
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i] + ",");
}
System.out.println("");
}
}
@Avinash
Sight modification is your code to avoid findPoistion of zero in each iteration. Correct me if I am wrong...
public class RearrangeArray {
public static void rearrange(int []source, int []target) {
int srcIndex = -1, srcZeroIndex = -1;
srcZeroIndex = findPosition(source, 0);
for (int index = 0; index < source.length; index++) {
if (target[index] != 0 && source[index] != target[index]){
swapInSource(source, srcZeroIndex, index);
srcZeroIndex = index;
srcIndex = findPosition(source, target[index]);
swapInSource(source, index, srcIndex);
srcZeroIndex = srcIndex;
}
}
}
private static int findPosition(int[] array, int key){
for (int i = 0; i < array.length; i++){
if (array[i] == key){
return i;
}
}
return -1;
}
private static void swapInSource(int source[], int index1, int index2){
int temp = source[index1];
source[index1] = source[index2];
source[index2] = temp;
}
public static void main(String[] args){
int[] source = { 1, 0, 2, 3, 7, 4, 8, 9 };
int[] target = { 0, 2, 8, 3, 1, 9, 4, 7 };
rearrange(source, target);
System.out.println("Source: "+ Arrays.toString(source));
}
}
My thoughts:
1) As any number can be swapped only with '0' -> The relative position of most of the numbers should be same, except the case of 1st position.
2) Zero always bubbles up to the first position, its like every new car gets to park on the top of the stack, so which means either (here zero travelling is nothing but swapping)
- Zero travels all the way to right-most and get swapped with left-most element.
- Zero travels all the way to the left-most
So if we consider target possibility of given src={1,0,2,3} would be either
Case 1: tgt={0,2,3,1} - Which is zero travels right-most and gets swapped with left-most element.
or
Case 2: tgt={0,1,2,3} - Which is zero travels left-most
I mean we compare src[0] with tgt[0] and decide whether to take zero to travel in which direction.
I might be assuming lot of things like
If we assume tgt[0] is always zero then tgt possibilities would be (n-1)!, so by assuming relative position I am ruling out all tgt possibilities except two.
So for {X, , , } => 1, 2, 3 can be arranged in 3! = 6 ways, but I am ruling out {0, 2, 1, 3}, {0, 3, 1, 2}, {0, 3, 2, 1} and {0, 1, 3, 2}
Sai
public class SwapWith0
{
public static void main(String[] args) {
int[] src = new int[] {1,0,2,3};
int[] tgt = new int[] {0,2,3,1};
int srcEmptyIndex = -1;
int tgtEmptyIndex = -1;
int[] indexTable = new int[src.length];
for(int i=0;i<src.length;i++) {
if(src[i]==0) {
srcEmptyIndex = i;
}
else {
indexTable[src[i]] = i;
}
if(tgt[i]==0) {
tgtEmptyIndex = i;
}
}
// If empty slots are the same, need to make it different to get things moving.
if(srcEmptyIndex==tgtEmptyIndex) {
int a = srcEmptyIndex;
int b = srcEmptyIndex;
if(srcEmptyIndex==0) { // first element
// Swap with next element
b = srcEmptyIndex+1;
}
else {
// Swap with previous element. takes care of last element as well.
b = srcEmptyIndex-1;
}
indexTable[src[b]] = srcEmptyIndex; // element src[b] swapped with 0
srcEmptyIndex=b;
System.out.println("Swap " + src[b] + " with 0");
src[a] = src[a] ^ src[b];
src[b] = src[a] ^ src[b];
src[a] = src[a] ^ src[b];
}
while(srcEmptyIndex!=tgtEmptyIndex) {
System.out.println("Swap " + tgt[srcEmptyIndex] + " with 0");
srcEmptyIndex = indexTable[tgt[srcEmptyIndex]];
}
}
}
A slight problem with the above code. There will still be instances where the 0 in the src and tgt ends up being in the same index before everything is finished swapping. Back to the drawing board.
OK. Second attempt.
public class SwapWith0
{
static int lastKnownDifference = 0;
public static void main(String[] args) {
// int[] src = new int[] {1,0,2,3};
// int[] tgt = new int[] {0,2,3,1};
int[] src = new int[] {0,1,2,3,4,5,6,7,8,9,10};
int[] tgt = new int[] {1,0,3,2,6,5,4,10,9,8,7};
int srcEmptyIndex = -1;
int tgtEmptyIndex = -1;
int[] indexTable = new int[src.length];
for(int i=0;i<src.length;i++) {
if(src[i]==0) {
srcEmptyIndex = i;
}
else {
if(src[i]!=tgt[i]) {
indexTable[src[i]] = i | 0x80000000; // MSB set means need to visit
lastKnownDifference = i;
}
else indexTable[src[i]] = i;
}
if(tgt[i]==0) {
tgtEmptyIndex = i;
}
}
// If empty slots are the same, need to make it different to get things moving.
if(srcEmptyIndex==tgtEmptyIndex) {
int a = srcEmptyIndex;
int b = srcEmptyIndex;
if(srcEmptyIndex==0) { // first element
// Swap with next element
b = srcEmptyIndex+1;
}
else {
// Swap with previous element. takes care of last element as well.
b = srcEmptyIndex-1;
}
indexTable[src[b]] = srcEmptyIndex | 0x80000000; // element src[b] swapped with 0
srcEmptyIndex=b;
System.out.println("Swap " + src[b] + " with 0");
/* No need to change the src array.
src[a] = src[a] ^ src[b];
src[b] = src[a] ^ src[b];
src[a] = src[a] ^ src[b];
*/
}
// while(srcEmptyIndex!=tgtEmptyIndex) {
while( srcEmptyIndex!=tgtEmptyIndex ||
((srcEmptyIndex=getNextSwapPosition(indexTable,srcEmptyIndex))!=-1)
) {
System.out.println("Swap " + tgt[srcEmptyIndex] + " with 0");
indexTable[tgt[srcEmptyIndex]] &= 0x7FFFFFFF;
srcEmptyIndex = indexTable[tgt[srcEmptyIndex]];
}
}
public static int getNextSwapPosition(int[] indexTable, int srcEmptyIndex) {
for(int i=lastKnownDifference;i>-1;i--) {
if(indexTable[i]<0) { // Need to visit
lastKnownDifference = i;
System.out.println("Swap " + i + " with 0");
indexTable[i] = srcEmptyIndex | 0x80000000;
return i;
}
}
return -1;
}
}
Just have to iterate through the cyclic transposition, only trick is that the graph may not be connected.
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main()
{
vector <int> src{1,0,2,3,5,4,7,9,6,8}, tgt{0,2,3,1,4,5,9,8,7,6};
int n = src.size(), visited=0;
vector<int> src_inv(n);
vector<char> flag(n,0);
deque<int> roots;
for(int i=0;i<n;++i)
src_inv[src[i]] = i;
for(int head = src_inv[0];visited<n;head++)
{
head = head%n;
if(flag[head]) continue;
flag[head] = true;
visited++;
if(src[head]) //if we are in a different component, we have to swap in
cout << "swap " << src[head]<< " with 0" << endl;
int pos = head;
do {
cout << "swap " << tgt[pos]<< " with 0" << endl;
pos = src_inv[tgt[pos]];
flag[pos]=true;
visited++;
} while (head != pos && tgt[pos]);
}
}
private static void rearrange(int[] src, int[] trg){
int[] indexTable = new int[src.length];
int swapLocation = -1;
for (int i = 0; i < src.length; i++) {
indexTable[src[i]] = i;
if (src[i] == 0) swapLocation = i;
}
for (int i = 0; i < trg.length; i++) {
int trgNum = trg[swapLocation];
int srcLoc = indexTable[trgNum];
src[srcLoc] = 0;
src[swapLocation] = trgNum;
System.out.println(srcLoc + "<->" + swapLocation +"; " + Arrays.toString(src));// +"; " + Arrays.toString(location));
swapLocation = srcLoc;
if (trg[swapLocation] == 0){
boolean finished = true;
for (int j = 0; j < trg.length; j++) {
if(src[j] != trg[j]){
finished = false;
src[swapLocation] = src[j];
indexTable[src[j]] = swapLocation;
src[j] = 0;
System.out.println(swapLocation + "<->" + j +"; " + Arrays.toString(src));// +"; " + Arrays.toString(location));
swapLocation = j;
break;
}
}
if (finished) break;
}
}
}
import java.io.*;
class eg11{
public static void main(String args[])throws IOException{
int[] src = new int[]{1,0,2,3};
int[] trg = new int[]{0,2,3,1};
System.out.println("the no of steps required for conversion are:"+rearranged(src,trg));
}
public static int rearranged(int[] src,int[] trg){
int count=0;
int k = findElement(0,src);
int l = findElement(0,trg);
while(k!=l){
int m = trg[k];
int n = findElement(m,src);
src[n] = 0;
src[k] = m;
k = n;
count++;
}
return count;
}
public static int findElement(int n,int[] a){
int i;
for(i=0;i<a.length;i++){
if(a[i]==n)break;
}
return i;
}
}
#include <iostream>
#include <vector>
void printVector(const std::vector<int>& value) {
for (int i=0; i<value.size(); i++) {
std::cout << value.at(i) << " ";
}
std::cout << std::endl;
}
void reorderVectorsToMatch(const std::vector<int>& source, const std::vector<int>& target) {
if (source.size() != target.size()) {
std::cout << "Source and target differ in size." << std::endl;
}
// Make a copy of the initial state
std::vector<int> currentState = source;
int zeroIndex = -1;
int outOfPlaceIndex = -1;
for (int i=0; i<currentState.size(); i++) {
if (currentState.at(i) == 0) {
// We don't want to use the 0 if it's out of place as
// it is where we want to shift things to
zeroIndex = i;
} else if (currentState.at(i) != target.at(i)) {
outOfPlaceIndex = i;
}
// Have we found both?
if (zeroIndex >= 0 && outOfPlaceIndex >= 0)
break;
}
// Bail out if everything is in order
if (outOfPlaceIndex < 0)
return;
// If zero is in place, swap it with something that is out of place
if (currentState.at(zeroIndex) == target.at(zeroIndex)) {
std::cout << "Swap " << currentState.at(outOfPlaceIndex) << std::endl;
currentState[zeroIndex] = currentState[outOfPlaceIndex];
currentState[outOfPlaceIndex] = 0;
zeroIndex = outOfPlaceIndex;
printVector(currentState);
}
while (currentState.at(zeroIndex) != target.at(zeroIndex)) {
// Find the index of what should be where the zero index is
for (int i=0; i<currentState.size(); i++) {
if (target.at(zeroIndex) == currentState.at(i)) {
// Swap what should be at the zero index into place
std::cout << "Swap " << currentState.at(i) << std::endl;
currentState[zeroIndex] = currentState.at(i);
currentState[i] = 0;
zeroIndex = i;
printVector(currentState);
break;
}
}
}
// Do it again until the whole thing is in order
reorderVectorsToMatch(currentState, target);
}
It can be achieved in O(n) time algo.
Put both arrays ( src A[ ] , tgt B[ ] ) in map ( mapA , mapB ) , key will be value of array element and value will be index of array element.
Index of 0 in A=x;
Index of 0 in B=y;
Int i=0;
While ( i < A.lenght){
if ( A[i] != B[i]]){
replace (B[i] , B[x]);
if(B[i] != A[i]){
var index = mapB.get(A[i]);
replace(B[i], B[index]);
}
}
i = i+1;
}
Simply modify answer of edlai
def swap_0(src, dst):
src_0_index = 0
dst_0_index = 0
table_index = [0 for e in src]
swap_chain = list()
pos_set = set(range(len(src)))
for i in range(len(src)):
if src[i] == 0:
src_0_index = i
else:
table_index[src[i]] = i
if dst[i] == 0:
dst_0_index = i
pos_set.discard(i)
print str(src)
print str(dst)
print ''
for i in range(len(pos_set)):
if src_0_index == dst_0_index:
next_index = pos_set.pop()
src[src_0_index] = src[next_index]
table_index[src[next_index]] = src_0_index
src[next_index] = 0
src_0_index = next_index
print str(src), 'p', src_0_index
dst_value = dst[src_0_index]
cur_pos = table_index[dst_value]
src[src_0_index] = dst_value
table_index[dst_value] = src_0_index
src[cur_pos] = 0
pos_set.discard(src_0_index)
src_0_index = cur_pos
print str(src), ' ', src_0_index
if __name__ == '__main__':
src = [1, 0, 2, 3, 5, 4, 6]
dst = [1, 0, 3, 2, 4, 6, 5]
swap_0(src, dst)
#include<stdio.h>
#define SIZE(A) (sizeof(A)/sizeof(A[0]))
void swap(int &a, int &b)
{
int tmp=a;
a=b;
b=tmp;
}
int main()
{
int source[]={1,0,2,3,5,4,7,9,6,8};//{1,0,2,3};
int target[]={0,2,3,1,4,5,9,8,7,6};//{0,2,3,1};//{1,3,2,0};
int i,j;
int size=sizeof(source)/sizeof(source[0]);
int ind=-1;
for(i=0;i<size;i++)
{
if(source[i]==0)
{
ind=i;
break;
}
}
for(i=0;i<size;i++)
{
for(j=0;j<size;j++)
{
if(source[j]==target[i])
{
if(i!=j)
{
printf("\nSwapping %d and %d\n",source[j],source[ind]);
swap(source[i],source[ind]);
ind=i;
swap(source[j],source[ind]);
ind=j;
break;
}
}
}
}
return 1;
}
template<class T>
bool computeSwapSequence(
const T& space_value,
const vector<T>& source,
const vector<T>& target,
vector<int>* sequence) {
hash_map<T, int> source_map;
int ii = 0;
for (const T& elem : source) {
auto insert_result = source_map.insert(make_pair(elem, ii++));
if (!insert_result.second) {
return false;
}
}
auto space_iter = source_map.find(space_value);
if (space_iter == source_map.end()) {
return false;
}
int space_index = space_iter->second;
source_map.erase(space_iter);
while (source_map.size() > 0) {
if (target.at(space_index) == space_value) {
swap(space_index, source_map.begin()->second);
} else {
const T& target_elem = target.at(space_index);
auto map_iter = source_map.find(target_elem);
if (map_iter == source_map.end()) {
return false;
}
space_index = map_iter->second;
source_map.erase(map_iter);
}
sequence->push_back(space_index);
}
return (target.at(space_index) != space_value);
}
I find an algorithm could achieve the goal in O(n) time, and here is the procedure:
1) scan the tgt array to find out the target position of i( i is an element in src ), and store it as an array tgt_index, so tgt[2] means where 2 should be in the tgt array;
2) scan the src array to find out the position of zero, denoted as zero_pos;
3) for each element src[i], let its target position in tgt be ti = tgt_index[src[i]]
3.1) if src[i] == 0, just swap src[i] and src[ti], and change zero_pos to ti;
3.2) if src[i] == 0, first swap src[ti] with src[zero_pos]( src[ti]has zero now ), then swap src[i] with src[ti]( src[i] has zero now ), and at last swap src[zero_pos] with src[i]( src[zero_pos] has zero new ).
Here is my code in C++:
#include <iostream>
#include <vector>
void print( int a[], int n )
{
for( int i = 0; i < n; ++i ) std::cout << a[i] << " ";
std::cout << std::endl;
}
void rearrange( int src[], int tgt[], int n )
{
std::vector<int> tgt_index( n, - 1 );
for( int i = 0; i < n; ++i ) tgt_index[ tgt[i] ] = i;
int zero_pos = 0;
for( ; zero_pos < n; ++zero_pos ) if( src[zero_pos] == 0 ) break;
std::cout << "src : ";
print(src,n);
int ti;
for( int i = 0; i < n; ++i )
{
ti = tgt_index[ src[i] ];
if( src[i] == 0 )
{
std::swap( src[i], src[ti] );
zero_pos = ti;
}
else
{
std::swap( src[ti], src[zero_pos] );
std::swap( src[i], src[ti] );
std::swap( src[zero_pos], src[i] );
}
std::cout << "src : ";
print(src,n);
}
std::cout << "tgt : ";
print(tgt,n);
}
int main( int argc, char* argv[] )
{
int src[] = { 1, 0, 2, 3 };
int tgt[] = { 0, 2, 3, 1 };
rearrange( src, tgt, 4 );
return 0;
}
Algo 1: O(n^2)
void RearrangeAnArrayUsingSwapZeroON2(int userInputSource[],int userInputTarget[],int sizeOfArray){
if(userInputSource == NULL && userInputTarget == NULL){
return;
}
if(userInputSource == NULL || userInputTarget == NULL){
return;
}
int zeroIndex=0,targetElementIndex,tempForSwap;
int outerCounter,innerCounter;
for(outerCounter = 0;outerCounter < sizeOfArray;outerCounter++){
if(userInputTarget[outerCounter] == 0){
continue;
}
if(userInputSource[outerCounter] == userInputTarget[outerCounter]){
continue;
}
if(userInputSource[zeroIndex] != 0){
for(innerCounter = 0;innerCounter < sizeOfArray;innerCounter++){
if(userInputSource[innerCounter] == 0){
zeroIndex = innerCounter;
}
if(userInputSource[innerCounter] == userInputTarget[innerCounter]){
targetElementIndex = innerCounter;
}
}
}
tempForSwap = userInputSource[zeroIndex];
userInputSource[zeroIndex] = userInputSource[outerCounter];
userInputSource[outerCounter] = tempForSwap;
tempForSwap = userInputSource[targetElementIndex];
userInputSource[targetElementIndex] = userInputSource[zeroIndex];
userInputSource[zeroIndex] = tempForSwap;
zeroIndex = targetElementIndex;
}
}
Algo 2: O(NlogN)
------------------------
1) Sort the first set of numbers
2) Perform a binary Search (Handle when middle index points to zero .... no need to move the numbers)
int BinarySearchForZeroSwap(int userInput[],int startArray,int endArray,int key){
if(startArray > endArray){
return INT_MIN;
}
int middleIndex = (startArray + endArray)/2;
if(userInput[middleIndex]==key){
return middleIndex;
}
if(userInput[middleIndex] == 0){
if(middleIndex-1 > startArray){
if(userInput[middleIndex-1] > key){
return BinarySearchForZeroSwap(userInput,startArray,middleIndex-1,key);
}else{
return BinarySearchForZeroSwap(user,middleIndex+1,endArray,key);
}
}else{
return BinarySearchForZeroSwap(userInput,middleIndex+1,endArray,key);
}
}
if(userInput[middleIndex] > key){
return BinarySearchForZeroSwap(userInput,startArray,middleIndex-1,key);
}else{
return BinarySearchForZeroSwap(userInput,middleIndex+1,endArray,key);
}
}
void RearrangeAnArrayUsingSwapZeroSortingONLOGN(int userInputSource[],int userInputTarget[],int sizeOfArray){
if(userInputSource == NULL && userInputTarget == NULL){
return;
}
if(userInputSource == NULL || userInputTarget == NULL){
return;
}
sort(userInputSource,userInputSource+sizeOfArray);
int zeroIndex = 0;
int targetElement,targetElementIndex,tempForSwap;
for(int counter = 0;counter < sizeOfArray;counter++){
targetElement = userInputTarget[counter];
targetElementIndex = BinarySearchForZeroSwap(userInputSource,counter,sizeOfArray-1,targetElement);
tempForSwap = userInputSource[zeroIndex];
userInputSource[zeroIndex] = userInputSource[targetElementIndex];
userInputSource[targetElementIndex] = tempForSwap;
zeroIndex = targetElementIndex;
}
}
Algo O(N) :
--------------
1) Use hash map
2) Store the indexes and swap by traversing the target array
void RearrangeAnArrayUsingZeroHashMapON(int userInputSource[],int userInputTarget[],int sizeOfArray){
if(userInputSource == NULL && userInputTarget == NULL){
return;
}
if(userInputSource == NULL || userInputTarget == NULL){
return;
}
hash_map<int,int> elementMapOfSource;
for(int counter =0;counter < sizeOfArray;counter++){
elementMapOfSource.insert(pair<int,int>(userInputSource[counter],counter));
}
int targetElement,tempForSwap,indexOfTargetElement,zeroIndex;
zeroIndex = elementMapOfSource.find(0)->second;
for(int counter =0;counter < sizeOfArray;counter++){
targetElement = userInputTarget[counter];
indexOfTargetElement = elementMapOfSource.find(targetElement)->second;
tempForSwap = userInputSource[zeroIndex];
userInputSource[zeroIndex] = userInputSource[indexOfTargetElement];
userInputSource[indexOfTargetElement] = tempForSwap;
zeroIndex = indexOfTargetElement;
elementMapOfSource[0] = zeroIndex;
}
}
for (int i = 0; i < tgt.length; i++) {
if (tgt[i] == 0) continue;
int pos = findPos(src, tgt[i]);
if (i == pos) continue;
int posZero = findPos(src, tgt[i]);
if (posZero != i) {
swap(src[posZero], src[i]);
}
swap(src[pos], src[i]);
}
an improvement maybe to cache zero position in src to avoid an lookup.
// My idea is based on regular permutation implementation, and it is easy to understand. By iteratively swap 0 with others element in the array, we can get desired permutation(target). Also, swapping two non-zero values require some trick.
say src={1,0,2,3}, dest={3,2,0,1}
By swapping forward, we get: {1}+0+perb(2,3),{1,2}+perb(0,3), {1,3}+perb(2,0);
by swapping backward, we get: 0+perb(1,2,3)
src={...., 0, ...}, the first part contains i elements before 0 and the second part contains j elements after 0, and i+1+j=n
//swap forward and permutation
for(int k=i+1;k<n;k++){ // 0 is at the pos of i+1
swap(0,src[k]);
int first[]=src[0...k-1];
int second[]=perb(src,k+1,n,k);
int result[]=first+second;
}
//swap backward
...
// note we are unable to do swap(a[i],a[j]) directly, and use swap_ex to replace swap
void swap_ex(int a[], int i, int j, int h){// h is the position of 0
swap(&a[i],&a[h]);
swap(&a[h],a[j])
}
void perb(int src[], int k, int n, const int h){ // h is the pos of 0
{
if (k==n){
// we have a chance here to find if src matches target
return;
}
else{
for(int j=k;j<n;j++){
swap_ex(src[k],src[k+1],h);
perb(src,k+1,n);
swap_ex(src[k],src[k+1],h);
}
}
}
Time and space complexity is ok(if the input is a huge string, it might be a problem!)
public class SwapZero {
public static void main(String[] args) {
int[] i1 = { 0, 1, 2, 3 };//{1, 0, 2, 3}
int[] i2 = { 0, 2, 3, 1 };
swap(i1, i2);
}
public static void swap(int[] i1, int[] i2){
int c = 0;
int ip1 = 0;
int ip2 = 0;
for( int i = 0 ; i < i1.length; i++){
if( i1[ i ] == 0)
ip1 = i;
if (i2[i] == 0)
ip2 = i;
}
if( ip1 == ip2 ){
if(ip1 + 1 < i1.length){
swap(ip1, ip1 + 1, i1);
ip1 = ip1 + 1;
}else{
swap(ip1, ip1 - 1, i1);
ip1 = ip1 - 1;
}
}
while( c < i1.length - 1){
for(int i = 0; i < i2.length; i++ ){
if ( i2[ip1] == i1[i]){
swap(i, ip1, i1);
ip1 = i;
c++;
break;
}
}
}
}
private static void swap(int i, int j, int [] i1){
int t = i1[i];
i1[i] = i1[j];
i1[j] = t;
for(int intg : i1 )
System.out.print(intg + " ");
System.out.println();
}
}
My idea is same as Jie
c++ code:
#include<iostream>
using namespace std;
void swap(int A[], int i, int j){
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
void AdjustAtoB(int A[], int B[], int n){
if(n <= 1) return;
int zeroInd = 0, tmp = 0, i, j;
for(i = 0; i < n; ++i)
if(A[i] == 0) zeroInd = i;
for(i = 0; i < n; ++i){
if(A[i] != B[i] && B[i] != 0){
for(j = 0; j < n; ++j){
if(A[j] == B[i]){
tmp = j;
break;
}
}
if(A[i] != 0){
swap(A, zeroInd, i);
cout << "For A" << i << ": swap A[" << zeroInd << "](" << A[zeroInd] << ") with A[" << i << "](" << A[i] << ");" << endl;
}
swap(A, i, tmp);
cout << "For A" << i << ": swap A[" << i << "](" << A[i] << ") with A[" << tmp << "](" << A[tmp] << ");" << endl;
zeroInd = tmp;
}
}
}
int main(){
int A[] = {1, 0, 2, 5, 3, 4};
int B[] = {3, 0, 1, 2, 5, 4};
int size = sizeof(A)/sizeof(int);
AdjustAtoB(A, B, size);
int i = 0;
cout << "------B------" << endl;
for(i = 0; i < size; cout << B[i++] << ' ');
cout << endl;
cout << "------A------" << endl;
for(i = 0; i < size; cout << A[i++] << ' ');
cout << endl;
return 0;
}
I believe a O(n) solution is possible.
The idea is to always arrange the next unarranged position.
For example, if we have:
src = {1,2,3,4,0}, tgt = {1,2,4,3,0
}, the next unassigned position is the third one.
In order to arrange it, you must place the 0 in that position:
{1,2,0,3,4} (by swaping)
then place the correct number:
{1,2,4,3,0
}
Repeat until finished.
This assumes that the zero will always be at the end in the tgt array, but it could be placed anywhere trivially, by doing a shift with swaps. E.g.:
{1,2,0} -> {0,1,2} :
{1,0,2}
{0,1,2}
Oh, I'm sorry, I was assuming that we had a map that would tell us where was each element from tgt in src.
I was assuming that a map from array to array existed.
It doesn't but it can be calculated in O(nlogn) for integers, so the total complexity is O(nlogn + n) = O(nlogn).
The idea for calculating the map between arrays of integers is that integers can be sorted in O(nlogn) then, finding all of them takes (again) O(logn)n= O(nlogn).
public class Main {
public static int findNuminA(int a[], int numToFind){
for(int i=0;i<a.length;i++){
if(a[i]==numToFind)
return i;
}
return 0;
}
public static void main(String args[]){
int a[] = {1,0,2,3};
int b[] = {0,1,2,3};
int count=0;
int indZeroIna = 1;
while(count<b.length){
int numatZeroIndInb = b[indZeroIna];
int indx = findNuminA(a,numatZeroIndInb);
a[indZeroIna] = a[indx];
a[indx]= 0;
indZeroIna=indx;
count++;
}
for(int i=0;i<a.length;i++){
System.out.print(a[i] + ",");
}
}
}
O(n) time complexity, O(n) space complexity
public static void main(String[] args) {
int[] a = new int[] {1,3,2,0,5};
int[] b = new int[] {2,1,3,0,5};
arrangeArrays(a, b);
}
public static void arrangeArrays(int[] a, int[] b) {
Map<Integer,Integer> aPositions = new HashMap<>();
for(int i=0;i<=a.length-1;i++) {
if(a[i] != b[i] || a[i]==0) {
aPositions.put(a[i],i);
}
}
arrange(a, b, aPositions);
for(int i =0; i<a.length;i++) {
System.out.println("a: " + a[i] + ", b: " + b[i]);
}
}
public static void arrange(int[] a, int[] b, Map<Integer,Integer> aPositions) {
while(aPositions.size() !=1) {
final Integer zeroIndex = aPositions.get(0);
final int bZero = b[zeroIndex];
if(bZero == 0) {
final Iterator<Integer> iterator = aPositions.keySet().iterator();
Integer next = iterator.next();
if(next == 0) {
next = iterator.next();
}
final Integer nextIndex = aPositions.get(next);
swap(a,zeroIndex,nextIndex);
aPositions.put(0,nextIndex);
aPositions.put(next,zeroIndex);
} else {
final Integer zeroSwap = aPositions.get(bZero);
swap(a,zeroIndex,zeroSwap);
aPositions.put(0,zeroSwap);
aPositions.remove(bZero);
}
}
}
public static void swap(int[] a, int i, int j) {
int swapInt = a[i];
a[i] = a[j];
a[j] = swapInt;
}
1. Find no. of elements k in each cycle of mispositioned numbers.
2. Add k+1 to result.
Why this will work?
Let's consider the fixing of one such cycle.
To fix one cycle, swap one of the numbers in cycle with 0 if 0 is not already present then simply swap each element with 0 to bring each element to its correct position.
The first extra swap is the reason for extra 1 in contribution of each cycle.
A simple recursion should be suffice:
1) Find the 0's index (pos_0) in src[]
2) If tgt[pos_0] == 0, stop recursion, otherwise swap 0 with tgt[pos_0], then recursion.
Time complexity is O(N^2), space is O(1).
public static void PrintSwap(int[] src, int[] tgt){
for(int n : src) System.out.print(s+" "); // Print every move
int pos_0 = findPosition(src, 0);
if(tgt[pos_0] != 0){
int pos_n = findPosition(tgt[pos_0]);
int temp = src[pos_0];
src[pos_0] = src[pos_n];
src[pos_n] = src[pos_0];
PrintSwap(src, tgt); // Recursion
}
}
private static int findPosition(int[] array, int key){
for(int i=0;i<array.length;i++)
if(array[i] == key)
return i;
return -1;
}
if tgt and src have zero in same position, but other numbers are not in same position, whether it work.............?
Nice catch. Thanks.
Still recursion;
public static void printMove(int[] src, int[] tgt, int index){
Print(src); // Print move
if(index < src.length && src[index] != tgt[index]){
int numPos = findPos(src, tgt[index]);
int zeroPos = findPos(src, 0);
int temp = 0;
if(zeroPos != index){
temp = src[index];
src[index] = src[zeroPos];
src[zeroPos] = temp;
Print(src); // Print move
}
temp = src[index];
src[index] = src[numPos];
src[numPos] = temp;
printMove(src, tgt, index+1);
}
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int a[100],b[100],n,s[100];
int posb(int i)
{
int j,l;
for(j=0;j<n;j++)
{
if(b[j]==i)
return j;
}
}
swap(int i,int j)
{
int t;
t=b[i];
b[i]=b[j];
b[j]=t;
}
rea(int l,int p)
{
int i,j,k,m;
if(l!=0)
{
k=a[p];
if(k!=0)
{
m=posb(k);
l--;
swap(p,m);
s[p]=1;
printf("\npositin %d <--> %d",p+1,m+1);
for(i=0;i<n;i++)
{
if(b[i]==0)
{
m=i;
break;
}
}
}
else
{
i=p+1;
while(s[i]==1)
{
if(i==n-1)
{
i=0;
}
else
i++;
}
m=i;
}
rea(l,m);
}
}
main()
{
FILE *fp;
fp=fopen("input.txt","r");
int i,d,k;
fscanf(fp,"%d",&n);
printf("%d\n",n);
for(i=0;i<n;i++)
{
fscanf(fp,"%d",&a[i]);
}
for(i=0;i<n;i++)
{
fscanf(fp,"%d",&b[i]);
}
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
for(i=0;i<n;i++)
{
printf("%d ",b[i]);
}
for(i=0;i<n;i++)
{
s[i]=0;
}
for(i=0;i<n;i++)
{
if(b[i]==0)
{
k=i;
break;
}
}
rea(n-1,k);
printf("\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
for(i=0;i<n;i++)
{
printf("%d ",b[i]);
}
}
#A.Nasimunni
n=input("\n\n\t\tEnter length of your array : ")
l=[]
l1=[]
print "\n\t\tEnter your src array zero must be present in your array "
for i in range(n):
l.append(input(" \n\t\tEnter your value into array : "))
print "\n\t\tEnter your tgt array zero must be present in your array "
for i in range(n):
l1.append(input(" \n\t\tEnter your value into array : "))
c=0
if l==l1:
print l
else:
for i in range(n):
for j in range(n):
if l==l1:
c=c+1
break
else:
m=l[l.index(0)]
l[l.index(0)]=l[j]
l[j]=m
if c>0:
print "Your src = ",l,"Your tgt = ",l1
Javascript version without recursion
Less memory because it doesn't need to keep a stack of calls
Count and logs for easier understanding
//var src = [1,0,2,3];
//var tgt = [0,2,3,1];
var src = [1,0,2,3,5,4,7,9,6,8];
var tgt = [0,2,3,1,4,5,9,8,7,6];
var replaceCount=0;
function findPos(arr, obj) {
for (var i=0; i<arr.length; i++)
if (arr[i] == obj) return i;
return -1;
}
function rearrange(src, tgt) {
for (i=0; i<src.length; i++) {
if (src[i] != tgt[i] && tgt != 0) {
if (src[i] != 0) {
//find 0, replace with i
var zPos = findPos(src, 0);
src[zPos] = src[i];
src[i] = 0;
console.log(src);
replaceCount++;
}
//replace current zero with index
var nPos = findPos(src, tgt[i]);
src[i] = src[nPos];
src[nPos] = 0;
console.log(src);
replaceCount++;
}
}
return src;
}
document.write(src);
document.write('<br>');
document.write(tgt);
document.write('<br>');
document.write(rearrange(src,tgt));
document.write('<br>');
document.write(replaceCount);
The question does not require the minimum swap number.
- Jie August 15, 2013So, an easy way to do is, find the index of first does not match (except ZERO),
then swap ZERO with it, then swap ZERO with the tgt value of that index.
Just loop for all positions. Then, it is done.
eg. {0, 1, 2} -> {0, 2, 1}
first does not match index is 1, and tgt value is 2.
So, {0, 1, 2}-> {1, 0, 2}->{1, 2, 0}
If it require the minimum swap number, then, shortest path algorithm will resolve it.
Every permutation is one node, and all possible links are just a swap of ZERO.
For performance improvement, A* can be used.
So, never swap ZERO with any value that matched already.
And it is better to generate nodes in run time.