Amazon Interview Question
Country: United States
1. Bob can move in 4 directions North,South,East,West with equal probability
2. Calculate the probability of survival in each direction.
3. return total probability divided by 4.
4. If at any point Bob is out of the matrix then return 0 (dead)
5. If he cannot move further and still in matrix then return 1 (alive).
the whole idea is to use DP to count each step that could cause the guy dead. The DP program will keep generating branches of possible paths and after the guy dead that branch will be closed and no more counting will be occurred. Also, the total steps will be counted.
correct me if im wrong, the following is the python code...
def dp_walking_dead(x, y, N,m, n):
deadCount = 0
totalCount = 0
while (N>0):
if x>0:
featureWalkResult = dp_walking_dead(x-1, y, N-1, m, n)
deadCount += featureWalkResult[0]
totalCount += featureWalkResult[1]
else:
deadCount += 1
if x<m-1:
featureWalkResult = dp_walking_dead(x+1, y, N-1, m, n)
deadCount += featureWalkResult[0]
totalCount += featureWalkResult[1]
else:
deadCount += 1
if y>0:
featureWalkResult = dp_walking_dead(x, y-1, N-1, m, n)
deadCount += featureWalkResult[0]
totalCount += featureWalkResult[1]
else:
deadCount += 1
if y<n-1:
featureWalkResult = dp_walking_dead(x, y+1, N-1, m, n)
deadCount += featureWalkResult[0]
totalCount += featureWalkResult[1]
else:
deadCount += 1
totalCount += 4
N -= 1
return [deadCount, totalCount]
Are the four directions equal in probability? In any case, this seems to be reducible into a straight forward Markov chain.
This can be solved in O(N).
1. Possible positions after N steps can be (-1,-1) to (m+1,n+1)
2. Now with (x,y) We can divide N steps in N+1 ways. For every division we can have max of 4 possiblities. 2 if division is equal or one of them is 0.
calcAliveProbability(int N,int m,int n, int x, inty){
int dead = 0;
int alive = 0;
for(int dx = 0;dx<=N;dx++){
int newx = x + dx;
int newy = y + (N - dx);
if(getState(newX,newY,m,n) == 0)
dead++;
if(getState(newX,newY,m,n) == 1)
alive++;
int newx = x + dx;
int newy = y - (N - dx);
if(getState(newX,newY,m,n) == 0)
dead++;
if(getState(newX,newY,m,n) == 1)
alive++;
int newx = x - dx;
int newy = y +(N - dx);
if(getState(newX,newY,m,n) == 0)
dead++;
if(getState(newX,newY,m,n) == 1)
alive++;
int newx = x - dx;
int newy = y -(N - dx);
if(getState(newX,newY,m,n) == 0)
dead++;
if(getState(newX,newY,m,n) == 1)
alive++;
}
return (alive/(alive+dead));
}
int getState(int newX, int newY,int m,int n){
if(newX<-1 || newX > m+1 || newY<-1 || newY >n+1)
return -1;
if(newX==-1 && newY==-1)//Special case NOT possible
return -1;
if(newX==m+1 && newY==n+1)//Special case NOT possible
return -1;
if(newX==-1 || newX == m+1 || newY==-1 || newY==n+1)
return 0;
else
return 1;
}
This is incorrect because it assumes that each position after N steps is equally probable.
//N - Total size of grid - x axis
//M - Total size of grid - y axis
//K - Number of moves (Given as 4 in the question)
//x - current x-axis location
//y - current y-axis location
float findProbability(int N, int M, int x, int y,int K){
if(k==0){
if((x<0 || y<0 || x>=N || y>=M){
return 0;
}
if((x<N-1 && y<M-1) && (x>0 && y>0)){
return 1;
}
}
//For higher K - using recursion
float prob;
if((x<N && y<M) && (x>=0 && y>=0) ) {
prob = 0.25*findProbability(N,M,x+1,y,K-1) + 0.25*findProbability(N,M,x,y+1,K-1) + 0.25*findProbability(N,M,x-1,y,K-1) + 0.25*findProbability(N,M,x,y-1,K-1);
}
return prob;
}
This can be solved by Linear Algebra.
if p_ij is the probability of landing at position ij, then you can write a system of equations. Which you then solve...
Let me know if I'm wrong. I use DP algorithm like I said. Time complexity is O(m*n*N).
public class CareerCupAmazon {
public double calcAliveProbability(int N,int m,int n, int x, int y)
{
if(x>m-1||x<0||y>n-1||y<0)
return -1;
double[][][] dp = new double[m+2][n+2][N+1];
for(int j=0; j<m+2; j++)
{
for(int k=0; k<n+2; k++)
{
if(k==0 || k==n+1 || j==0 ||j==m+1)
{
dp[j][k][0] = 1;
}
else
dp[j][k][0] = 0;
}
}
for(int i=1; i<=N; i++)
{
for(int j=0; j<m+2; j++)
{
for(int k=0; k<n+2; k++)
{
if(k==0 || k==n+1 || j==0 ||j==m+1)
{
dp[j][k][i] = 1;
}
else
{
dp[j][k][i] = (dp[j-1][k][i-1]+dp[j+1][k][i-1]+dp[j][k-1][i-1]+dp[j][k+1][i-1])/4;
}
System.out.print(dp[j][k][i]+"\t");
}
System.out.println();
}
System.out.println();
System.out.println();
}
return 1-dp[x+1][y+1][N-1];
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
CareerCupAmazon a = new CareerCupAmazon();
System.out.println("the probability that bob is alive is "+a.calcAliveProbability(10, 20, 20, 10, 2)*100+"%");
}
}
I have the feeling that your code is close to the right answer, but there is one point I don't understand. Could you please elaborate what does dp[i][j][k] mean? Does it mean the probability of Bob stand on (i, j) point at the k-th step?
dp[i][j][k] means the probability Bod will die if initial position is (x,y) and steps he moves is k.
O(n*m*N)
double prob_died(size_t m, size_t n, size_t N, int x_in, int y_in) {
double* curr_prob = new double[n*m];
double* new_prob = new double[n*m];
memset(curr_prob, m*n*sizeof(double), 0);
curr_prob[x_in+y_in*n] = 1.0;
for (int i = 0; i < N; i++) {
memset(new_prob, m*n*sizeof(double), 0);
for (int x = 0; x < n; x++)
for (int y = 0; y < m; y++) {
double prob = curr_prob[x+y*n];
if (x > 0) new_prob[(x-1)+y*n] += prob/4;
if (x < n-1) new_prob[(x+1)+y*n] += prob/4;
if (y > 0) new_prob[x+(y-1)*n] += prob/4;
if (y < m-1) new_prob[x+(y+1)*n] += prob/4;
}
std::swap(curr_prob, new_prob);
}
double sum_prob = 0;
for (int i = 0; i < n*m; i++) sum_prob += curr_prob[i];
delete[] curr_prob;
delete[] new_prob;
return 1.0 - sum_prob;
}
// :) code !! shivi :)
#include<iostream>
#define M 4
#define N 4
using namespace std;
int count1=0,count2=0;
int visited[M+2][N+2];
void Probability(int i,int j,int steps)
{
cout<<i<<" "<<j<<endl;
if(steps<0)
return ;
count2++;///total valid steps with steps>=0
if(!visited[i][j] && (i>M-1 || j>N-1 || i<0 || j<0))
{count1++; return;}//total death steps
visited[i][j]=1;
if(!visited[i+1][j])
Probability(i+1,j,steps-1);
if(!visited[i][j+1])
Probability(i,j+1,steps-1);
if(!visited[i][j-1])
Probability(i,j-1,steps-1);
if(!visited[i-1][j])
Probability(i-1,j,steps-1);
}
int main()
{
Probability(1,1,3);
cout<<count1/count2<<endl;
}
A very ugly brute force solution:
================================
class WaysBobDie
{
private int m;
private int n;
private int N;
private double die;
private double live;
public WaysBobDie(int m, int n, int N)
{
this.m = m;
this.n = n;
this.N = N;
die = 0;
live = 0;
}
public void calculate(int x, int y)
{
calculateHelper(x, y, 0);
System.out.println("Probability of alive: " + live/(live+die));
}
private void calculateHelper(int x, int y, int numSteps)
{
if(isLive(x, y) && numSteps != N)
{
calculateHelper(x+1, y, numSteps+1);
calculateHelper(x-1, y, numSteps+1);
calculateHelper(x, y+1, numSteps+1);
calculateHelper(x, y-1, numSteps+1);
}
else if(isLive(x, y) && numSteps == N)
{
++live;
return;
}
else if(!isLive(x, y))
{
++die;
return;
}
}
private boolean isLive(int X, int Y)
{
if(X < 0 || Y < 0 || X >= m || Y >= n)
{
return false;
}
else
{
return true;
}
}
}
I guess the time complexity is O(4^N), which is incredibly ugly. Looking forward to better solution.
As the other anonymous guy said, this process can be modeled as a two-dimensional random walk (thus Markov Chain) with equal probability in each direction. The probability transition matrix M of this process will be of size m*n-by-m*n, and it involves the calculation of M^N (multiply M by itself N times). Since the time complexity of matrix multiplication is O((m*n)^3) (well, you can make it a little faster), it is a polynomial time algorithm now (even though still not very fast).
float StayLiveProb(int x, int y, int steps)
{
if(0<=x && x<M && 0<=y && y<N)
{
if(steps>0)
{
return 0.25*(StayLiveProb(x-1, y, steps-1) + StayLiveProb(x,y-1,steps-1) + StayLiveProb(x+1, y, steps-1) + StayLiveProb(x, y+1, steps-1));
}
return 1;
}
return 0;
}
float DeadProb(int x, int y, int steps)
{
return 1-StayLiveProb(x, y, steps);
}
- MadCoder September 02, 2012