Amazon Interview Question


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[5][5]={
                                {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);
        
}

- MadCoder September 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- MadCoder September 02, 2012 | Flag
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):
    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]

- suzker August 30, 2012 | Flag Reply
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.

- Anonymous August 28, 2012 | Flag Reply
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 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;
}

- loveCoding August 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't believe this is correct.

- Anonymous August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I believe This is correct

- Manan August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- loveCoding August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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?

Can you please elaborate?

- Anonymous August 29, 2012 | Flag
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;
}

- deadman August 29, 2012 | Flag Reply
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...

- Anonymous August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 30, 2012 | Flag
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).

- LoocalVinci August 30, 2012 | Flag Reply
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][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+"%");
}

}

- LoocalVinci August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Richard August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- LoocalVinci August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- LoocalVinci August 30, 2012 | Flag
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; 
}

- Martin August 30, 2012 | Flag Reply
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.

- iictarpit September 18, 2012 | Flag Reply
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;
}

- shivi October 18, 2012 | Flag Reply
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).

- Richard August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, transition matrix is one approach.

- Anonymous August 30, 2012 | Flag
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);
}

- jiangok2006 August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is step?

- Avenger August 29, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More