Amazon Interview Question Software Engineer / Developers
Although I agree with everyone that 'omkar' should word the question more clearly, it is almost easy to guess that he meant the following:
"Minimum no. of changes required to change L1 to L2 in terms of having nodes in same order with same data, with possible changes allowed as adding, deleting, swapping nodes".
Input [consider a toy example]:
L1 - 12->13->45->1->33->NULL
L2 - 13->12->0->45->NULL
Result:
1. Swap Node 12 and Node 13 in L1.
2. Delete Node 1 and Node 33 in L1.
3. Add Node 0 in L1.
This would be similar to the Edit Distance problem with strings. If allowed, we could simply store the data values as a string and try to find the minimum edit distance.
Nice question BTW!
why would you compute edit-distance and all that as the problem here is to simply convert L2 to L1?
instead of adding/removing/swapping and all that, plainly set the values of nodes in L2 till the length of L1 (deleting if L1 is shorter, inserting if greater)... you can avoid the time involved in performing checks with IF in cases where the target value to be assigned is the same as the one stored already (not sure if setting the value will be more expensive than doing a control switch for IF)...
How if we do this?
create an array of m* n elements ( m= num of elements of list l1) , n= number of elements of list l2.
then , place the difference of distances in the matrix Di,j
Now just check the difference and place in the distance matrix.
Also, after the step , just check the minimum distance Mini,j and get the corresponding value of i for that value of j.
thus we get the node corresponding to the similar node in the list.
That would work right???
What do you mean L1 look same as L2,please clarify your question first.
- Derek November 02, 2010