Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
The cycle length can be exponential in the number of digits. Even for a very modest number of digits (say 100), you could run out of space and time. You need a better algorithm.
Consider the case where there's some sub-cycle of period 2, then some sub-cycle of period 3, period 5, period 7, period 11, etc. for primes. Then the entire cycle's period is at least 2 * 3 * 5 * 7 * 11 and so on. This argument shows the cycle length can be roughly exponential.
@eugene: why do you think the cycle length can be exponential in the no of digits ?
we can build a directed graph with nodes = # of digits
this graph will several simple components (cycles).
i.e. for 2315 -> 5213
we have a graph with 2 cycles:
3->3 (digit 3 maps to itself)
1 -> 2 -> 4 -> 1
then we need to find smth like lcm of all cycle lengths
that would give us the number of times we need to cycle around to get to the original state
Awesome. This is what I got too. There will always be cycles. Find the no of nodes in all cycles and get LCM of these.
Isn't it sufficient to find the reverse path from source to destination of 1 digit? When considering the whole number each digit has just moved once
The claim, a transformation of a1a2..an to akaj..am can be reversed if 1 digit is moved to its correct position is true for 2 digits. Assume claim is true for k digits. For k+1 digits, move the 1st digit in transformed number to its correct position then by previous assumption k digits are moved to their correct positions i.e. 1 through k then there is only 1 position left for last digit i.e. k+1, hence the claim is true for k+1 digits is true, simply put, by induction.
To find if the mapping exists or not can be done in nlogn by sorting. To find the number of steps is an n^2 problem. Solution is given below
PS: Wrote the code in a hurry. So there could be some useless variables sitting around.
import java.util.Arrays;
public class MappingPermutation {
int[] initArr = null;
int initArrLen = 0;
int[] permArr = null;
int permArrLen = 0;
public MappingPermutation(int[] init) {
initArr = init;
initArrLen = init.length;
}
public boolean isPermutation(int[] permutation) {
if(permutation == null)
return false;
if((permArrLen = permutation.length) != initArrLen)
return false;
// No mergesort code here. I am assuming its written already.
int[] sortedPerm = mergeSort(permutation);
int[] sortedInit = mergeSort(initArr);
boolean retVal = true;
for(int i = 0; i < permArrLen; i++) {
retVal &= (sortedPerm[i] == sortedInit[i]);
}
return retVal;
}
public int noOfCombinations(int[] perm) {
int count = 0;
if(this.isPermutation(perm) == false)
return -1;
for(int i = 0;i < initArrLen; i++) {
if(initArr[i] == perm[i])
continue;
for(int j = i; j < initArrLen; j++) {
if(perm[i] == initArr[j]) {
int tmp = initArr[j];
initArr[j] = initArr[i];
initArr[i] = tmp;
}
}
count++;
}
return count;
}
public static void main(String[] args) {
int[] temp = {1, 4, 9, 2, 3, 22, 43, 54, 66};
int[] perm = {54, 66, 1, 2, 22, 4, 43, 3, 9};
MappingPermutation test = new MappingPermutation(temp);
System.out.println(test.noOfCombinations(perm));
}
}
1. Find mapping in o(n2) TC
e.g actual array = 2315
permuted array 5213
mappings 1->2, 2->4,3->3, 4->1
2. to get same element in same poition in array ,
transiton path for first element 1->2->4->1
transiton path for second element 2->4->1->2
similarly for other elements
2315
5213 ( 1st permutation)
3512 (2nd permutation)
2315( 3rd permutation )
3. from the above transiton path, it is clear that , we get same elememt back into same positon after 3 permutation ( it is transiotn path length ).
4. transiotn length give us no. of pemutations required to get original array.
code ::
/// assumption given array is distinct array ( I mean there is no duplicats in array )
int matching[n];
int NoOfPermutation( int OrgArray[], int PermutedArray, int n )
{
int i,j;
int transitonPathLength =0 ;
// find matchings, store them in Matching[]
for ( i =0 ; i <n ;i ++ )
{
for(j =0 ; j< n; j++ )
{
if( OrgArray[i] == PermutedArray[j] )
{
matching[i] = j;
break;
}
}
}
// we know the matchings, now just we need to calculate transiton path length
i=0;
// if an element is in same position in Original array and Permuted array, it is not possible to calculate transiton path length.
while ( i == matching[i] )
{
i++;
}
j = i;
while ( i ! = matching[j] )
{
transitonPathLength++;
j = matching[j] ;
}
return transitonPathLength ;
}
I'm going to give you the same objection as I've given others: the cycle length can be exponential with the number of digits. Even for 100 digits your program would take pretty close to forever. Can you make it scale?
We can solve this problem in O(n) time complexity.
Step1:
Array[] = {2,3,1,5} Permute[] ={5,2,1,3}
Step2:
2315 -->exchange 2 & 3
3215 -->exchange 3 & 5
5213
total 2 swap operations
Step3:
int i = 0, swapCount = 0, j;
while(i < n)
{
if( Array[i] == Permute[i] )
{
i++;
}
else
{
j = findElementIndex( Permute, A[i] );
Swap(A,i,j); // Swap i & j indexes elements
swapCount++;
}
}
I guess this could be done by finding the cycles in the directed graph that represents the transformation. Use floyd warshall algorithm to get the length of the shortest cycle for each position. if any of the positions do not have a cycle, then it cannot be done, but if all of them have cycles, then the total no of transformation required would be the LCM of the lengths of the cycles .
let abcd -> acdb then transformations are ( 1->1, 2->4, 3->2, 4->3).
With the principle that some-position-element needs to be replaced by another-position-element there will always be loops(It can be drawn from graph theorms that if for every position(node in graph) has only 1 in and 1 exit, then they always form a loop).
so in a loop of length x nodes, after x mappings all the nodes in loop are at the same state as in the initial word. so answer for that loop alone is X.
but if there are multiple loops then the answer is LCM of all the loop lengths.
Why the cycle length should go exponential.
Any cycle should be less than or equal to n.
And finding it should be an order of n.
Just declare a boolean array visit of size n:
boolean visit[n]
Now prepare the auxillary array to store mappings say a[] where
a[i]=x means that i will be transformed to xth position.
Now take first element and keep on going to next element by marking the current visited element to true until you do not get the current element that is already set as true.
That makes your one cycle and you can store the length of cycle .
Now find another non visited element in array and find the length of cycle with that element and keep on updating lcm with previously find cycle length.
In worst case it will be O(n) with space of O(n)
But as someone pointed out that question will become tricky with repetition of digits as you can form multiple mapping arrays and cycle length can change depending on that which again can effect your answer.
Any thoughts on the problem when digits could be repeated.
The cycle length could be exponential. Let me illustrate with an example. Consider a sequence p1p2p3...p_n, where each p_k represents the sequence of numbers 1 2 ... the k-th smallest prime. A sample sequence, for example, is 1 2 1 2 3 1 2 3 4 5 1 2 3 4 5 6 7. Now, consider the following permutation: for each sequence p_k, map index 1 to index 2, 2 to 3, ..., k to 1. Do this independently for each p_k. So the sample sequence would become 2 1 3 1 2 5 1 2 3 4 7 1 2 3 4 5 6. The next permutation after that would be 1 2 2 3 1 4 5 1 2 3 6 7 1 2 3 4 5. If you look at the chain of permutations, you can see that the original permutation will recur after len(p1) * len(p2) * len(p3) *.. *len(p_n) transformations. However, the length of the input is only len (p1) + len (p2) + len(p3) +.. + len (p_n).
_
If instead of picking the first primes we just picked any d primes close to a value r, we'd have close to r^d cycle length and r*d input size. r^d/ (r*d) = r^(d-1) / d. Let's say we just set r = d, then the ratio of time to size is r^(r-2), which is actually even slightly superexponential O(2^(theta(nlogn)))
If we assume that digits are not repeated then it can be done in O(n) and with a constant space complexity O(10).
Solution:
let suppose number is 2356 and permutation of number is 5623
Take an array of length 10 A[0-9], initialized with zero .
Start traversing from the original number and store its index in array A .
so it will be like A[0,0,1,2,0,3,4,0,0,0]
1-> index of 2
2-> index of 3
3-> index of 5
4-> index of 6
Now traverse permutation of the original number
5 -> check value of A[5] =>3 , so 3rd index -> 1st
6-> check value of A[6]=>4, 4th index ->2nd
2-> A[2]=>1 , 1st index -> 3rd
3->A[3]=>2, 2nd index -> 4th
Think of each "mapping" as a transformation/FSM from initial "state" (position) to final "state" (position).
- Anonymous April 18, 2012For each digit in the permuted number, run it through the transformations, counting the number of transformations needed to reach its final "state"/position. If it visits a previous "state" which is not a cycle, then report it is not possible.
If the number of steps for each digit is the same, then it is possible.
It can get a little tricky if digits can repeat I think.