Amazon Interview Question
SDE-2sCountry: India
1. represent the rocks in an array rocks [n]( where n= (m2-m1) + (m3-m2).......) such that rocks[i]=1 if a rock is present at i distance from m1 else
2. Take another array jumps[n]. Initialize all jumps[i]= infinity and jumps[0]=0
3. now start
from i=1 to i=n
............if(rocks [i] != 0)
.................. jumps[i]= min( jumps[i-Wj]) where Wj is the array containing Ways to jump
............else
...................jumps[i]= infinity
4. jumps[n] contains your minimum jumps
I think N here means there are N types of jumps the rabbit can perform.
So in the example, N = 2 and the jump lengths rabbit can perform are 3 and 1.
If N = 3, then maybe the rabbit can perform a jump of length 4
...
Let A be the array for storing results which has been initialized to a highest integer value, Let D be the array for storing diff, eg. D[1] contains m2-m1 and so on. Let R contains the list of possible values where rabbit can jump.
for(i=1;i<N;i++) {
diff =0;
for(j=i;j>0;j--) {
diff+=D[j];
if(R.exists(diff)) {
if(A[i]>A[j]+1) {//careful about the overflow
A[i]=A[j]+1;
}
}
}
}
And A[N-1] contains the minimum value. :)
You actually don't need Djisktra for this. The Length of the Jump doesn't need to be optimized, just the number of them.
We can create a graph, with edge I->J abd J<-I if j can be reached from I based on the number of Steps between I and J and what is allowed. And then we just find the shortest path from S - E in terms of number of nodes using BFS (Mark visited node, else will fail).
I am still wondering on the reason for the "can also jump backwards", if the number of jump lengths possible backwards is the same as forwards, I don't see how a shortest path will have a jump backwards. Even if the Jump backwards were different than forwards, I don't see how a shortest path will include a cycle. Added to confuse ?
try below test case to understand "can also jump backwards"
Input
For each test case, the first line contains 2 space separated integers, M and N. The second line contains M-1 space separated integers denoting the distance between consecutive rocks in the river. The third line contains N space separated integers denoting the possible jump lengths.
4 3
12 3 2
15 5 3
1. Build graph of reachable stones from every stone
2. Find shortest path in graph using dijkstra algorithm.
Here is my solution
- Pavel Aslanov July 15, 2014