Amazon Interview Question
Software Engineer / DevelopersTeam: Bangalore
Country: India
Interview Type: In-Person
Example 1: Start--(1)--D1--(2)--D2--(3)--D3--(2)—end and z=18 then possible output are
a) start— (1) —D1— (2) —D2— (3)—D3— (3)—D2—(2)—D1—(2)—D2—(3)—D3—(2) —end
b) start— (1) —D1— (2) —D2—(2)—D1—(2)—D2—(3)— D3— (3)—D2—(3)—D3(2)— end etc…
Example 2: Start—(1)—D1—(1)—D2—(1)—D3—(1)—D4—(1)—D5—(1)—end and z=12 then possible output are
a) start—D1—start—D1—D2—D3—D2—D3—D4—D3—D4—D5—end
b) start—D1—D2—D1—D2—D3—D2—D3—D4—D5—D4—D5—end
few doubts, what you mean by x1 distance D1,x2 distance D2...
distance is measure between which two points ? if the stones are present in the river and distance is measured from 1 bank and object is to reach the opposite bank using the given distance, we need the distance between the stones as well ??
Here First corner of the river is start
D1 is the first stone
x1 is distance between start and D1.
x2 is distance between D1 and end.
And last corner of the river can be treated as end
start
its a dynamic algorithmic problem , on every stone there,s several ways to travel a considerable distance that can fulfill criteria of travelling z distance exactly problem come becoz of no optimization criteria on every step so using only 2-d arrays is not gona work
what data strucure should be used for storing intermediate result and how??
This sounds like a Permuation problem where repetitions are allowed: nPr= n^r
Here, total number of stones to choose from is Dn and we must ASSUME that we are going to choose only 2 stones at a time because we have two legs. then we are talking Dn^2 number of patterns. Since we are allowing repetitions, the sum total will always be greater than Z.
How about this for the DP recursion:
DP[i,z]=DP[i-1,z-dist(Di,Di-1)]+DP[i+1,z-dist(Di,Di+1)]
i = 0 for start,1 for D1, n for Dn,n+1 for end
Basically when you are at ith stone and you have to walk z distance more, you can either goto i-1th or i+1th having walked dist(i to i-1) or dist(i to i+1)
Use memoization to store arr[i][z] = DP[i,z] etc.
Breaking conditions:
DP[n+1(end),0] = 1
DP[i,z] = 1 if( dist(i,end_or_n+1) == z) meaning from i you go to end via i+1,i+2 ...
DP[i,z] = 0 if( dist(i,end_or_n+1) > z)
DP[i,z] = 0 if i <0 or i> n+1
MAIN call : DP[0,Z]
I am thinking of this way:
- little-eyes September 18, 20121. we need to go from "start" to "end", then we have to cover a base distance = sum(x_i), which is go directly from start -> d_1 to d_n -> end.
2. the different patterns can be split into pieces like d_i to d_j, which means you can go back and forth between d_i and d_j as many times as you want, as long as the total distance does not exceed Z.
3. So the value P = Z - sum(x_i) can be regarded as the total distance used to go back-and-forth in any pair (d_i, d_j). Each time you made a back-and-forth between (d_i, d_j), it cost 2*x_i.
4. Then you can use DP to calculate the combinations of using x_i to make up the sum equals to P. Each x_i can be used for multiple time. Then final combinations is the total number of patterns.
5. If you need to print all the patterns, you need to search, but in a memoization way. The worst case time complexity could be O(n*P).
Does it make sense??