Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

Think of each "mapping" as a transformation/FSM from initial "state" (position) to final "state" (position).

For 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.

- Anonymous April 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.yarovoi April 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- xxx April 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous April 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, Get length of each cycle and find the LCM.

- Anil April 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Agreed that it's the LCM of the cycle lengths. That is the efficient way to solve this. The originally proposed method, which was to go through all the permutations until we see the same permutation we started with, would be very inefficient.

- eugene.yarovoi June 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1st to 2nd, 2nd to 4th and 4th to 1st. 3rd doesn't move. The 3 indices form a loop and hence the 3rd transform is going to bring the number back to original state. eg: if the number is of the form 1000*a+100*b+10*c+d
0. abcd
1. dacb
2. bdca
3. abcd

- Anonymous April 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous April 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not k+1 but the only remaining position which is correct(since 2 digits can't be in same position and no position can be empty)

- Anonymous April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous April 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am assuming input is given as an array. Even if its given as a single integer, its not a big deal to convert it into an array. Also, I have double digit array elements (digits can only be between 0-9) which cannot obviously exist. So ignore that as well.

- One more thing April 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ; 

}

- siva.sai.2020 April 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- eugene.yarovoi April 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@eugene, thanks for pointing my mistrake

- siva.sai.2020 April 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- siva.sai.2020 February 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 .

- adi April 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- SantiagoYemmiganur April 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Agreeing with SantiagoYemmiganur...
Thought of exactly same answer... It should be the LCM of all the loop lengths.

- Sunny April 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Anyone take into consideration that if the original array has repeated #. In that case, the directed graph would be more complicated. EX: 5512 -> 1255
5->1
5->2
1->5
2->5

- Simon April 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- nitin April 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi May 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Sharma April 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

And How does this solve the problem

- Anonymous May 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone explain the question?I am not getting .. what is mapping here ?

- leet November 03, 2012 | 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