Question: RazorPay Online Assessment 22nd September | Falling Apples
0
Entering edit mode

Summer Internship

Question 1:

Click here to Practice

Question

ADD COMMENTlink 20 months ago Vijay • 0
1
Entering edit mode
  • Assuming number of apples to be at most 1000

Q1) Hint : Observe this line Also you need to help them catch the apples in the sequence they fall

Solution:
Representing max(alice_pos,bob_pos) as P
Let F(alice_pos,bob_pos) represent minimum distance that need to be travelled to end if till now start to max(alice_pos,bob_pos) apples have been picked and alice is currently at alice_pos and bob is currently at bob_pos. Then from here as it is given in the question that they need to catch apples in sequence (i.e they cannot catch second apple before the first one) ,some of them will go to next apple. Since currently they have covered start to P then then they need to pick P+1 apple after that(P+2,P+3...and so on). Hence we have two options over here that is either take alice to P+1 or take bob to P+1 and check which gives the minimum distance.
Pseudo Code

Consider positions as the array of apples {pos[0],pos[1]....pos[n-1]} 
and push alice and bob positions into it also. positions{alice_initial,bob_initial,pos[0],pos[1],pos[2].....,pos[n-1]} 
and let F(alice_pos,bob_pos) represent as stated above in the Solution section.
int F(int alice,int bob)
{  
if(max(alice,bob)==(n+1))//consider 0 based indexing
    return 0; //we have covered all the apples hence distance travelled to end from here would be 0.
int P=max(alice,bob);
    //dist(A,B) represent manhattan distance between points A and B.
int choice1=F(P+1,bob)+dist(positions[alice],positions[P+1]); //take Alice to P+1
int choice2=F(alice,P+1)+dist(positions[bob],positions[P+1]); //take Bob to P+1
return min(choice1,choice2);
}

And we could optimize it by memoizing the above recursion over state{alice_pos,bob_pos} to O(n^2)

ADD COMMENTlink 20 months ago Shikhar Mehrotra 480
0
Entering edit mode

May i have the fourth test case please? 

ADD COMMENTlink 16 months ago Red • 0
Entering edit mode
0

6
-1000000000 1000000000
1000000000 -1000000000
-1000000000 -1000000000
200 -100
-1000000000 1000000000
100 200
-1000000000 1000000000
1000000000 -1000000000

 

Output: 6000000600

ADD REPLYlink 16 months ago
Shikhar Mehrotra
480
0
Entering edit mode

 

 
ADD COMMENTlink 10 months ago Nachiketh K S • 0

Login before adding your answer.

Similar Posts
Loading Similar Posts