Flipkart Interview Question
SDE1sCountry: India
Interview Type: In-Person
The probability has to be split into 3 cases, corners, sides and internal cells. There are 4 corner cells, 2*(P-2) + 2*(Q-2) side cells and (P-2) * (Q-2) internal cells.
The probability to survive in a corner cell is 0.5 since there are 2 edges which will push someone out and 2 edges which will keep them internal.
The probability to survive in a side cell is 0.75 since there is just one edge facing outward and the probability to survive in an internal cell is 1. Given a cell (x,y), the probability to survive in the next move is
(4*0.5 + (2*(p-2) + 2*(q-2)) * 0.75 + (p-2)*(q-2) * 1)/ (p*q), which when solved gets us (pq-0.5q-0.5p)/(pq). Since there are N turns, we need to make it an exponent of N. For N turns, the probability of surviving would be ((pq-0.5q-0.5p)/pq) ^ N
See every position you can reach in n steps. If reaching to a dead end, increase its count. Calculate the probability as (totalSteps-stepsThatLeadToEnd)*100/totalSteps
#include <iostream>
using namespace std;
int tSteps=0;
int total=0;
int d=0;
int P, Q, N;
void Pr(int x, int y, int steps);
int main(){
int x, y;
cin>>P>>Q>>N>>x>>y;
Pr(x, y, 0);
cout<<(tSteps-d)*100/tSteps<<"%";
return 0;
}
void Pr(int x, int y, int steps){
if(steps==N){
tSteps++;
if(x<0||x>P){
d++;
}
else if(y<0||y>Q){
d++;
}
return;
}
else{
Pr(x+1, y, steps+1);
Pr(x-1, y, steps+1);
Pr(x, y+1, steps+1);
Pr(x, y-1, steps+1);
}
}
- DR A.D.M May 26, 2015