## Amazon Interview Question

• 0

Country: United States

Comment hidden because of low score. Click to expand.
3
of 3 vote

``````#include<stdio.h>

float probAlive(int m,int n,int x, int y, int N){

float p1,p2,p3,p4;

if(x<0||x>m-1||y<0||y>n-1){
return 0;
}
if(N==0)
return 1.0;

p1 = probAlive(m,n,x+1,y,N-1);
p2 = probAlive(m,n,x-1,y,N-1);
p3 = probAlive(m,n,x,y+1,N-1);
p4 = probAlive(m,n,x,y-1,N-1);

return (p1+p2+p3+p4)/4;
}
int main(){

int m,n,x,y,N;
float aliveProb;
/*int a={
{1,2,3,4,5},
{6,7,8,9,4},
{2,4,2,5,3},
{4,6,8,9,7},
{4,2,4,1,6}};
*/
m = 5;
n=5;
N=3;
x=0;
y=0;

aliveProb=probAlive(m,n,x,y,N);
printf("Alive prob = %f",aliveProb);

}``````

Comment hidden because of low score. Click to expand.
0

1. Bob can move in 4 directions North,South,East,West with equal probability
2. Calculate the probability of survival in each direction.
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).

Comment hidden because of low score. Click to expand.
1
of 1 vote

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):
totalCount = 0
while (N>0):
if x>0:
featureWalkResult = dp_walking_dead(x-1, y, N-1, m, n)
totalCount += featureWalkResult
else:

if x<m-1:
featureWalkResult = dp_walking_dead(x+1, y, N-1, m, n)
totalCount += featureWalkResult
else:

if y>0:
featureWalkResult = dp_walking_dead(x, y-1, N-1, m, n)
totalCount += featureWalkResult
else:

if y<n-1:
featureWalkResult = dp_walking_dead(x, y+1, N-1, m, n)
totalCount += featureWalkResult
else:

totalCount += 4
N -= 1

Comment hidden because of low score. Click to expand.
0
of 0 vote

Are the four directions equal in probability? In any case, this seems to be reducible into a straight forward Markov chain.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 2 vote

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 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)
if(getState(newX,newY,m,n) == 1)
alive++;

int newx = x + dx;
int newy = y - (N - dx);
if(getState(newX,newY,m,n) == 0)
if(getState(newX,newY,m,n) == 1)
alive++;

int newx = x - dx;
int newy = y +(N - dx);
if(getState(newX,newY,m,n) == 0)
if(getState(newX,newY,m,n) == 1)
alive++;

int newx = x - dx;
int newy = y -(N - dx);
if(getState(newX,newY,m,n) == 0)
if(getState(newX,newY,m,n) == 1)
alive++;

}
}

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;
}``````

Comment hidden because of low score. Click to expand.
0

I don't believe this is correct.

Comment hidden because of low score. Click to expand.
0

I believe This is correct

Comment hidden because of low score. Click to expand.
0

This is incorrect because it assumes that each position after N steps is equally probable.

Comment hidden because of low score. Click to expand.
0

It assumes that each step is equally likely. Not each point

Comment hidden because of low score. Click to expand.
0

@Manan:

For each position he seems to be calculating if that is an alive or dead position, incrementing the corresponding variable and computing (alive/(alive + dead)).

Is that making each position equally likely?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//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;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

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...

Comment hidden because of low score. Click to expand.
0

This approach is correct for the case N -> oo.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Intuitively, I'll choose DP algorithm for this kind of problems. Time complexity should be O(m*n*N).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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] = 1;
}
else
dp[j][k] = 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+"%");
}

}

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

dp[i][j][k] means the probability Bod will die if initial position is (x,y) and steps he moves is k.

Comment hidden because of low score. Click to expand.
0

Then if he moves k+1 steps, the probability will be
(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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

we can run a back tracking algorithm i.e bfs of level n. Now number of leave is total cases and leafs with user killed. thus probability.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// :) 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;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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).

Comment hidden because of low score. Click to expand.
0

Yes, transition matrix is one approach.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0

what is step?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.