## Google Interview Question for Software Engineer / Developers

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
21
of 23 vote

I presume that the probabilities of move up/donw/left/right are equal(0.25).
Then P(x, y, n, step) = (P(x-1, y, n, step-1) + P(x+1, y, n, step-1) + P(x, y-1, n, step-1) + P(x, y+1, n, step-1)) / 4.
(x, y) is the position. (n) is the size of island. (step) is the remaining step.
The following code is my Java implementation with some simple tests.
Dynamic Programming is also used.

``````import java.util.*;

class ProbabilityOfAlive
{
public static double probabilityOfAlive(int x, int y, int n)
{
if (x < 0 || x > (n - 1) || y < 0 || y > (n - 1) || n < 1) {return 0.0;}
return probabilityOfAlive(x, y, n, n, new HashMap<String, Double>());
}

private static double probabilityOfAlive(int x, int y, int n, int step, HashMap<String, Double> map)
{
if (0 == step) {return 1.0;}
// if the state is already calculated, return from HashMap
String key = "";
{
StringBuffer sb = new StringBuffer();
sb.append(x + ",");
sb.append(y + ",");
sb.append(step + ".");
key = sb.toString();
}
if (map.containsKey(key)) {return map.get(key);}
// calculate the probability of a state
double probability = 0.0;
if (x > 0) {probability += 0.25 * probabilityOfAlive(x - 1, y, n, step - 1, map);}
if (x < (n - 1)) {probability += 0.25 * probabilityOfAlive(x + 1, y, n, step - 1, map);}
if (y > 0) {probability += 0.25 * probabilityOfAlive(x, y - 1, n, step - 1, map);}
if (y < (n - 1)) {probability += 0.25 * probabilityOfAlive(x, y + 1, n, step - 1, map);}
// save the result to HashMap and return
map.put(key, probability); return probability;
}

public static void main(String[] args)
{
System.out.println("probability1 = " + probabilityOfAlive(0, 0, 1));
System.out.println("probability2 = " + probabilityOfAlive(0, 0, 2));
System.out.println("probability3 = " + probabilityOfAlive(0, 0, 3));
}
}``````

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

How the probability for (0,0,1) be 0.
As the (0,0) coordinate person can move to (0,1) or (1,0) in one chance. So according to the assumption of 0.25 probability for each move the total P = 0.50 (Person dies only in case he chooses (0,-1) or (-1,0))

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

@ctrlV: dude u r calculating wrong..the code is correct... it is giving 0.5 probability.

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

@ctrlV:
(0, 0, 1) means the initial position is (0, 0) and the row/column of island is 1,
which means the island contains only one position: (0, 0).
Therefore (0, 1) and (1, 0) are also dead positions.

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

Idea of using DP with memorization is good, this should save us some time; btw, could we do it using tabulation approach?
I am still thinking but couldn't make one yet.

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

What is complexity of this algorithm? O(n^2)?

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

I think the time complexity for any solution to this problem should be exponential. Let me explain the mathematical way of calculating the probability here:
The total number of outcomes are n^n.
To calculate the number of outcomes which can lead to death of the person:
For each of the four directions, check how many steps can lead to him going out of the matrix. Then, apply the high school probability formula. For e.g. suppose the total number of steps he can take are 5; (x, y) = (2,1) [indexing is 0-based]. So, he needs to take 3 steps in north dir. to fall out of island. Keeping them in a group: (NNN) and making other 2 steps as any of the 4 choices, we have the formula: 4*4*3. Similarly, for other 3 directions. Finally, the probality = (sum of the calculated death outcomes) / (total outcomes)

Hence, the complexity will be exponential.

Comment hidden because of low score. Click to expand.
1
of 3 votes

the complexity should be O(n*N^2)

Comment hidden because of low score. Click to expand.
2
of 2 votes

Make some simplification of Alva0930's code:

``````import java.util.*;

public class ProbabilityOfAlive {
public static double aliveProb(int x, int y, int N, int n) {
if (x < 0 || x > (N - 1) || y < 0 || y > (N - 1) || N < 1) return 0.0;
return aliveProb(x, y, N, n, new HashMap<String, Double>());
}

private static double aliveProb(int x, int y, int n, int step, Map<String, Double> map) {
if (0 == step) return 1.0;

String key = x + "," + y + "," + step;
if (map.containsKey(key)) return map.get(key);

double p = 0.0;
if (x > 0)     p += 0.25 * aliveProb(x - 1, y, n, step - 1, map);
if (x < n - 1) p += 0.25 * aliveProb(x + 1, y, n, step - 1, map);
if (y > 0)     p += 0.25 * aliveProb(x, y - 1, n, step - 1, map);
if (y < n - 1) p += 0.25 * aliveProb(x, y + 1, n, step - 1, map);

map.put(key, p);
return p;
}

public static void main(String[] args) {
System.out.println("Alive probability = " + aliveProb(0, 0, 1, 1));
System.out.println("Alive probability = " + aliveProb(0, 0, 2, 1));
System.out.println("Alive probability = " + aliveProb(0, 0, 3, 3));
System.out.println("Alive probability = " + aliveProb(1, 1, 3, 1));
System.out.println("Alive probability = " + aliveProb(2, 2, 10, 20));
}
}``````

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

I am not sure the code is correct in the place it uses stored values from hashMap , specifically

``if(map.containsKey(key)) return map.get(key);``

. This actually stores the probability of being at one NxN point after x steps. However if I will get to that point from some second path in the same amount of steps, then the probability being there is twice as much (the probabilities should sum together and they are the same) since it was saved there only from the first arrival. Therefore I think that I should do something like

``map.put(key,map.get(key) *2); return map.get(key)``

What do you think?

Comment hidden because of low score. Click to expand.
10
of 12 vote

1. Generate NxN probability matrix P(x,y,1) for all (x, y) coordinates (x & y ranges from 0 to N-1). P(x,y,1) is the probability of staying alive after taking 1 step
2. Now using this, we need to calculate the NxN probability matrix P(x,y,2) for all x and y - will be P(x,y,1) * { {Valid among P(x+1, y, 1) + P(x, y+1, 1) + P(x-1, y, 1) + P(x, y-1, 1) } / num of valid adjascent slots }. Now we have P(x,y,2) probability matrix.
3. Using induction, we can calculate P(x, y, k) using P(x, y, k-1). Repeat this N times, we have our probability matrix after N steps

``````float probabilityofalive(int x, int y, int N, int num_steps)
{
if (N <= 0) return 0;
if (x < 0 || x >= N) return 0;
if (y < 0 || y >= N) return 0;

if (N == 1) return 0; // only one square. first step will cause exit from island and die.

/* Probability matrix for staying alive after K steps for all (x,y) coordinates. */
double *P_old = calloc(N*N, sizeof(double));

/* Probability matrix for staying alive after K+1 steps for all (x,y) coordinates. */
double *P_new = calloc(N*N, sizeof(double));

int i, j;
/* Initialize for K = 1 */
for (i = 0; i<N; i++) {
for (j=0; j<N; j++) {
double prob;
if (i>0 && i<N-1 && j>0 && j<N-1) {
prob = 1.0;
} else if ((i == 0 || i == N-1) && (j == 0 || j == N-1)) {
prob = 0.5;
} else
prob = 0.75;

P_new[N*i + j] = prob;
}
}

int k = 0;
for (k=2; k<=num_steps; k++) { /* First step already taken in K == 1 matrix above */
/* Copy new to old */
for (i = 0; i<N; i++) {
for (j=0; j<N; j++) {
P_old[N*i+j] = P_new[N*i+j];
}
}

/* Calculate new probability matrix */
for (i=0; i<N; i++) {
for (j=0; j<N; j++) {
double sum_prob = 0;
int num_prob = 0;
if (i > 0) {
sum_prob += P_old[N*(i-1) + j];
num_prob++;
}
if (i < N-1) {
sum_prob += P_old[N*(i+1) + j];
num_prob++;
}
if (j > 0) {
sum_prob += P_old[N*i + (j-1)];
num_prob++;
}
if (j < N-1) {
sum_prob += P_old[N*i + (j+1)];
num_prob++;
}

/* New probability when person starting at (i,j) coordinate after k steps*/
P_new[N*i + j] = P_old[N*i + j] * sum_prob/num_prob;
}
}
}

return P_new[N*x + y];
}

int main()
{
int x = 3;
int y = 3;
int N = 4;
int num_steps = N;
float prob =  probabilityofalive(x, y, N, num_steps);

printf("Probability of staying alive after %d steps starting at coordinates (%d, %d)  on an %d x %d grid is '%f'\n", num_steps, x, y, N, N, prob);
}

/*
For N = 4, probability fo survival after 1 step is given below

-------------------------------------
|        |        |        |        |
|  0.50  |  0.75  |  0.75  |  0.50  |
|        |        |        |        |
-------------------------------------
|        |        |        |        |
|  0.75  |  1.00  |  1.00  |  0.75  |
|        |        |        |        |
-------------------------------------
|        |        |        |        |
|  0.75  |  1.00  |  1.00  |  0.75  |
|        |        |        |        |
-------------------------------------
|        |        |        |        |
|  0.50  |  0.75  |  0.75  |  0.50  |
|        |        |        |        |
-------------------------------------

Probability fo survival after 2 steps will be

-------------------------------------
|        |        |        |        |
|  0.38  |  0.56  |  0.56  |  0.38  |
|        |        |        |        |
-------------------------------------
|        |        |        |        |
|  0.56  |  0.88  |  0.88  |  0.56  |
|        |        |        |        |
-------------------------------------
|        |        |        |        |
|  0.56  |  0.88  |  0.88  |  0.56  |
|        |        |        |        |
-------------------------------------
|        |        |        |        |
|  0.38  |  0.56  |  0.56  |  0.38  |
|        |        |        |        |
-------------------------------------

... and so on
*/``````

Believe this logic/code is correct. Please update if you find any issue

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

Looks good. Also, there are lots of symmetries here that allow you to reduce storage. A simple way to cut the processing in half is to only consider squares where x <= y, and if you need P(x,y,n) where x > y, then just find P(y,x,n). You can also take advantage of horizontal and vertical reflections.

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

The N of the NxN matrix and the n of the n steps are different, I believe.

For large n (as compared to N) you might be better off using matrix multiplcation...

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

Do we really have to store the values?
static double probability(int x, int y, int n, int xmax, int ymax)
{
double result = 0.0;
if (x < 0 || y < 0 || x >= xmax || y >= ymax)
return result;

if (n == 0)
return 1;

if ((x < xmax))
{
result += .25 * probability(x + 1, y, n - 1, xmax, ymax);
}
if (x > 0)
{
result += .25 * probability(x -1, y, n - 1, xmax, ymax);
}
if (y > 0)
{
result += .25 * probability(x, y-1, n - 1, xmax, ymax);
}
if (y <ymax)
{
result += .25 * probability(x, y + 1, n - 1, xmax, ymax);
}
return result;
}

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

I think , your answers are correct for 2,2 matrix the one you showed, but I doubt it will work for higher values. Just consider 3,3 matrix. The answer of the top left cell would be 0.1054 according to the induction but in reality its 0.28 (18/64). The number of possible moves is 64 and in only 18 (I counted) of them you will survive.
Why 2,2 is working and the rest are not . What I think is this, again considering the top left cell, probability of surviving in two
moves = probability of surviving in move1* probability of being in one of the two valid cells * probability of surviving in that cell in next move (probability of surviving in that cell in one move) +
probability of surviving in move1* probability of being in the other valid cell * probability of surviving in that cell in next move (probability of surviving in that cell in one move) which is 0.5*0.5*0.75 + 0.5*0.5*0.75 which is the same thing you did.

But now (according to your algorithm) probability of surviving in top left cell in three moves = probability of surviving in that cell in two moves * probability of being in adjacent cell (which in your case we are always taking 0.5 (one of two valid cells) which is wrong because in two moves there are more valid cells that we can be in) * probability of surviving in that cell in two moves (which again does not make sense, you have already consider two moves , so now its two + two moves -- weird). The solution looks very impressive in the beginning which caught me for a long time but I still can't understand how its going to work for higher numbers.

Thanks

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

Actually found the correct equation

P(x,y,k) = P(x,y,1) * { {Valid among P(x+1, y, k-1) + P(x, y+1, k-1) + P(x-1, y, k-1) + P(x, y-1, k-1) }/ num of valid adjascent slots }. Note: The first term remain P(x,y,1) and not P(x,y,k-1) which means 1,1 matrix for the rest of soln. I guess you were saying the same thing. Anyways thanks for solution. I guess this is the only correct one we have so far.

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

@Arjun, see also: "Efficient Solution in Python (with tests)".

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

Is the complexity of this solution O(N^2 x n) ? We are calculating an NxN matrix n times. Please correct me if I'm wrong.

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

``````public float prob(int x, int y, int n) {
if ((x<0)||(y<0)||(x>=n)||(y>=n))
return 0;
else if (n==1)
return 1;
return (prob(x-1, y, n-1)+prob(x, y-1, n-1)+
prob(x+1, y, n-1)+prob(x, y+1, n-1))/4;
}``````

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

--> else if (n==0) return 1;

consider prob(0,0,1) = 1/2

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

Well my assumption was that n equals 1 meant no more steps allowed.. but yeah, 0 makes more sense, my bad.

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

Efficient Solution in Python (with tests)

This is a DP solution that only computes one octant of the matrix, since all the other octants are just reflections. It also defers dividing by powers of four until the end.

``````def test():
assert 1.0 == probability_of_alive(5, 0, 0, 0)
assert 0.5 == probability_of_alive(5, 1, 0, 0)
assert 0.75 == probability_of_alive(5, 1, 1, 4)
assert 1.0 == probability_of_alive(5, 2, 2, 2)
assert 0.9375 == probability_of_alive(5, 3, 2, 2)

def probability_of_alive(N, n, x, y):
dct = get_survival_dct(N, n)
return 1.0 * lookup(dct, N, x, y) / (4**n)

def get_survival_dct(N, n):
# This returns a dictionary where keys
# are (x,y) tuples and it only has values
# for the WNW octant of the island, since
# other values can be calculated via
# horizontal, vertical, and diagonal
# reflection.  Values are probabilities
# of survival * (4**n).
dct = {}
for i in range((N+1)/2):
for j in range(i, (N+1)/2):
dct[(i,j)] = 1
for step in range(n):
new_dct = {}
for i in range((N+1)/2):
for j in range(i, (N+1)/2):
new_dct[(i,j)] = \
lookup(dct, N, i+1, j) + \
lookup(dct, N, i, j+1) + \
lookup(dct, N, i-1, j) + \
lookup(dct, N, i, j-1)
dct = new_dct
return dct

def lookup(dct, N, i, j):
if N - i - 1< i: i = N - i - 1
if N - j - 1< j: j = N - j - 1
if j < i: i, j = j, i
return dct.get((i,j), 0)

def print_probability_matrix(N, dct):
for i in range(N):
print [lookup(dct, N, i, j) for j in range(N)]

N = 5
for n in range(4):
dct = get_survival_dct(N, n)
print_probability_matrix(N, dct)
print
test()``````

The program's output shows that sample matrices for N=5.

``````[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]

[2, 3, 3, 3, 2]
[3, 4, 4, 4, 3]
[3, 4, 4, 4, 3]
[3, 4, 4, 4, 3]
[2, 3, 3, 3, 2]

[6, 9, 10, 9, 6]
[9, 14, 15, 14, 9]
[10, 15, 16, 15, 10]
[9, 14, 15, 14, 9]
[6, 9, 10, 9, 6]

[18, 30, 33, 30, 18]
[30, 48, 54, 48, 30]
[33, 54, 60, 54, 33]
[30, 48, 54, 48, 30]
[18, 30, 33, 30, 18]``````

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

Please put in algo form for easy understanding of logic first.

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

you start with 1 at all the positions as in 0 steps all positions have 0 probability of dying..
then it uses the updation rule where val(x,y) = sum of all valids((val(x+-1,y+-1))
which is evaluating 1 step at a time

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

``````#include <iostream>
#include <assert.h>
using namespace std;

#define N 5

float probabilityofalive(int x,int y, int n){
assert( x>=0 && x<N && y>=0 && y<N);

if (n==1) {
if (x==0 && y==0 || x==0 && y==N-1 || x==N-1 && y==0 || x==N-1 && y==N-1) {
return 0.5;
} else if (x==0 || x==N-1 || y==0 || y==N-1) {
return 0.25;
} else {
return 1;
}
}

float p_left, p_right, p_up, p_down;

if (0 <= x-1) {
p_left = probabilityofalive(x-1, y, n-1);
} else {
p_left = 0;
}

if (x+1<N) {
p_right = probabilityofalive(x+1, y, n-1);
} else {
p_right = 0;
}

if (0<=y-1) {
p_up = probabilityofalive(x, y-1, n-1);
} else {
p_up = 0;
}

if (y+1<N) {
p_down = probabilityofalive(x, y+1, n-1);
} else {
p_down = 0;
}

return 0.25*( p_left+p_right+p_up+p_down );

}

int main ()
{

cout << probabilityofalive(2, 2, 5) << endl;

return 0;
}``````

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

Exponential time complexity! Bad bad.

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

@hello world you code fails in the very 1st section . ex (0,1,1) where ans should be 0.75 but your code will give 0.25. your if else conditions are intersecting among themselves...chk carefully

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

``````double solve(int x, int y, int k)
{
if (x < 0 || x > n || y < 0 || y > n) return 0;
if (k == 0) return 1.0;
double ret(0.0);
if (x+1 < n) ret += solve(x+1, y, k-1);
if (x-1 >=0) ret += solve(x-1, y, k-1);
if (y-1 >=0 ) ret += solve(x, y-1, k-1);
if (y+1 < n) ret += solve(x, y+1, k-1);
return 0.25 * ret;
}``````

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

My solution in C++. We fill a matrix of size n*N*N in O(n*N^2) time :

``````float probabilityofalive(int x, int y, int n) {
float P[n + 1][N][N];
int i, j, k;
for (i = 0; i < N; ++i) {
for (j = 0; j < N; ++j) {
P[0][i][j] = 1.;
}
}
for (k = 1; k <= n; ++k) {
for (i = 0; i < N; ++i) {
for (j = 0; j < N; ++j) {
P[k][i][j] = 0.;
if (i < N - 1)
P[k][i][j] += P[k - 1][i + 1][j];
if (i > 0)
P[k][i][j] += P[k - 1][i - 1][j];
if (j < N - 1)
P[k][i][j] += P[k - 1][i][j + 1];
if (j > 0)
P[k][i][j] += P[k - 1][i][j - 1];
P[k][i][j] *= 0.25;
}
}
}
return P[n][x][y];
}``````

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

Psuedocode for probabilityofdead :

``````float probabilityofdead(int x, int y, int n)
{

if(x>0 && y>0 )
{

if (N-1-x >= n &&  N-1-y>=n  && x>=n && y>=n && n>=0)
return 1;

if( x==N-1 && y>0 && y< N-1 & n>=1)
return 0.25;

if( y==N-1 && x>0 && x< N-1 & n>=1)
return 0.25;

if( x==0 && y>0 && y< N-1 & n>=1)
return 0.25;

if( y==0 && x>0 && x< N-1 & n>=1)
return 0.25;

if(x==0 && y==0 || x==N-1 && y==0 || y==N-1 && x==0 || x==N-1 && y==N-1)
return 0.75;

n--;

return 	probabilityofdead(x+1,y,n)  +
probabilityofdead(x,y+1,n)  +
probabilityofdead(x-1,y,n)   +
probabilityofdead(x,y-1,n) ;

}
else

return 0;
}``````

Hence ,probabilityofalive= 1- probabilityofdead

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

The probability can be higher than 1 in this case. You should divide by 4 to get the right answer

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

Also, the recursive calls should use n-1 as a parameter. The probability of dying from a square in n steps when the first step is a neighbor involves the probability of dying in n-1 steps from the neighbor.

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

I am doing n---
check out..tht means n becomes n-1.

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

A DP problem. Let's say the person is at (x0, y0) initially(instead of (x, y) in the question)
Build a table W(n, N, N) whose entry W(k, x, y) is the number of ways to get to (x, y) from initial location(x0, y0) after k steps.
Now, without considering the border,

``W(k + 1, x, y) = W(k, x - 1, y) + W(k, x, y - 1) + W(k, x + 1, y) + W(k, x, y + 1)``

Then build W up to n steps, again, without considering the border.
After that, just count the percentage of the locations (a, b) in W(n, a, b) that are out of the border, this is the probability.

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

can u write a pseudocode?

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

You have a to be a little careful about considering the border. Once you step off the island, you're dead, whereas if you only consider the water at the end of N steps, you can count situations where folks stepped into the water and out of the water.

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

``````def deadprobability(n, N, x0, y0):
waystodie = 0
W = [[[0 for y in range(0, N)] for x in range(0, N)] for k in range(0, n + 1)]
W[0][x0][y0] = 1

for k in range(1, n + 1):
for x in range(0, N):
for y in range(0, N):
if x == 0:
waystodie +=  W[k - 1][x][y]
if x == N - 1:
waystodie += W[k - 1][x][y]
if y == 0:
waystodie += W[k - 1][x][y]
if y == N - 1:
waystodie += W[k - 1][x][y]
if x > 0:
W[k][x][y] += W[k - 1][x - 1][y]
if x < N - 1:
W[k][x][y] += W[k - 1][x + 1][y]
if y > 0:
W[k][x][y] += W[k - 1][x][y - 1]
if y < N - 1:
W[k][x][y] += W[k - 1][x][y + 1]
print str(W)

waysalive = 0
for x in range(0, N):
for y in range(0, N):
waysalive += W[n][x][y]

probalive = 1.0 - waystodie / ((waystodie + waysalive) * 1.0)
print waystodie, waysalive, probalive

def test(n, N, x0, y0):
print 'Initial at (%d, %d) in %dx%d island, after %d steps'%(x0, y0, N, N, n)
deadprobability(n, N, x0, y0)

test(1, 1, 0, 0)
test(2, 1, 0, 0)
test(2, 2, 0, 0)
test(2, 3, 1, 1)``````

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

This can be solved using DP

``````int fall =0;
int calProb(int n, int m, int **arr)
{
if(n ==0 && m == 0)
return 1;
else if( m<0 || n< 0)
{
fall++;
return 0;
}
else
{
return CallProb(n-1,m,**arr) + CallProb(n,m-1,**arr) + CallProb(n-1,m-1,**arr);
}
}``````

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

can u elaborate more. this code doesnt seem to work for probability..

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

Dude, read question carefully. Do not jump immediately over writing the code!

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

Oh I am sorry. A little modification to the code. Please do let me know If I am making some mistake here.
Starting from x,y, the initial inputs for the array will be x, y

int fall =0;
int calProb(int n, int m, int **arr, int steps)
{

if( m<0 || n< 0)
{
fall++;
return 0;
}
else if(step ==0)
return 1;
else
{
return CallProb(n-1,m,**arr,step--) + CallProb(n,m-1,**arr, step--) + CallProb(n-1,m-1,**arr,step--);
}
}

Now we can calculate
Let say the output of this function be livProb i.e.
livProb = calProb(x,y, arr, n);

therfore living probability = livprob \ (livprob + fall)

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

``````def probDeadHelper(x,y,n,N,deadAlive):
if n==0:
deadAlive[1] = deadAlive[1]+1
return
if (x<0 or x >=N or y <0 or y >=N):
deadAlive[0] = deadAlive[0] +1
return
probDeadHelper(x-1,y,n-1,N,deadAlive)
probDeadHelper(x+1,y,n-1,N,deadAlive)
probDeadHelper(x,y-1,n-1,N,deadAlive)
probDeadHelper(x,y+1,n-1,N,deadAlive)
def probDead(x,y,n,N):
deadAlive = [0,0]
probDeadHelper(x,y,n,N,deadAlive)
dead = deadAlive[0]
alive = deadAlive[1]
return (alive/(alive+dead))``````

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

deadAkive is an array with two value:
deadAlive[0] = number of times dead
deadAlibe[1] = number of timesAlive

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

change the order of helper base case:

``````def probDeadHelper(x,y,n,N,deadAlive):
if (x<0 or x >=N or y <0 or y >=N):
deadAlive[0] = deadAlive[0] +1
return
if n==0:
deadAlive[1] = deadAlive[1]+1
return
probDeadHelper(x-1,y,n-1,N,deadAlive)
probDeadHelper(x+1,y,n-1,N,deadAlive)
probDeadHelper(x,y-1,n-1,N,deadAlive)
probDeadHelper(x,y+1,n-1,N,deadAlive)
def probDead(x,y,n,N):
deadAlive = [0,0]
probDeadHelper(x,y,n,N,deadAlive)
dead = deadAlive[0]
alive = deadAlive[1]
return (alive/(alive+dead))``````

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

Pseudo code

- Add x, y, N-x, N-y into sorted array
- assume highest to lowest order is N-x, y, N-y, x for now
- if n > N-x return 1 (means if person moves n steps at all any direction he will be dead)
- if n < x return 0 ( means if person moves n steps any dir he will be alive)
- if n is between N-x and y return .75
And so on

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

My Idea :
1> For area outside the NXM, the death Prob is 1, what ever the step is. (step>=0)
2> For area inside the NxM and step=0, death Prob is zero.
3> For Other x, y, and step, probDeath(x,y,step)=1/4*(probDeath(x-1,y, step-1) + probDeath(x+1,y, step-1)+probDeath(x,y-1, step-1) +probDeath(x,y+1, step01)). Assume the person runs randomly.
4> The logic above also added a array to store the shared calculated result (as does dynamic programming) to save the computation time during the recursive call.
5> ProbLive(x,y, step)=1-ProbDeath(x,y,step).

My Code:

``````typedef struct{
double  *pProb;
int     w;
int     h;
int     step;
} squareProb_t;

void   squareProbInit(squareProb_t *pCb, int w, int h, int maxStep)
{
int     count;
if(NULL==pCb||1>w||1>h)
return;
pCb->w=w;
pCb->h=h;
pCb->step=maxStep;
pCb->pProb=malloc(sizeof(double)*w*h*(maxStep));
if(NULL==pCb->pProb)
return;
for(count=0;count<w*h*(maxStep);count++)
pCb->pProb[count]=-1.0;
return;
}
double squareProbDead(squareProb_t *pCb, int x, int y, int step)
{
int     count;
if(NULL==pCb)
return 0;
if(0>step||pCb->step<step)
return 0;
if(x<0||x>=pCb->w||y<0||y>=pCb->h)
{
printf("(x=%d, y=%d, step=%d) ==> %f\n", x, y, step, 1.0);
return 1;
}
if(step==0)
{
printf("(x=%d, y=%d, step=%d) ==> %f\n", x, y, step, 0.0);
return 0;
}
count=(y*pCb->w+x)*pCb->step+step-1;

if(-1.0==pCb->pProb[count])
{
step--;
pCb->pProb[count]=(squareProbDead(pCb, x-1,y, step)+
squareProbDead(pCb, x+1,y, step)+
squareProbDead(pCb, x,y-1, step)+
squareProbDead(pCb, x,y+1, step))/4;
printf("  ==>");
}
printf("(x=%d, y=%d, step=%d) ==> %f\n", x, y, step+1, pCb->pProb[count]);
return pCb->pProb[count];
}``````

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

Test Code:
int main()
{
squareProb_t cb;
double p1, p2, p3;
squareProbInit(&cb, 2,2, 5);
p1=squareProbDead(&cb, 0, 0, 1);
p2=squareProbDead(&cb, 0, 0, 2);
p3=squareProbDead(&cb, 0, 0, 5);
printf("p1 is %f\n", p1);
printf("p2 is %f\n", p2);
printf("p3 is %f\n", p3);

}

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

Test Result:Test Result of my code:
p1 is 0.500000
p2 is 0.750000
p3 is 0.968750

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

``````def deadprobability(n, N, x0, y0):
waystodie = 0
W = [[[0 for y in range(0, N)] for x in range(0, N)] for k in range(0, n + 1)]
W[0][x0][y0] = 1

for k in range(1, n + 1):
for x in range(0, N):
for y in range(0, N):
if x == 0:
waystodie +=  W[k - 1][x][y]
if x == N - 1:
waystodie += W[k - 1][x][y]
if y == 0:
waystodie += W[k - 1][x][y]
if y == N - 1:
waystodie += W[k - 1][x][y]
if x > 0:
W[k][x][y] += W[k - 1][x - 1][y]
if x < N - 1:
W[k][x][y] += W[k - 1][x + 1][y]
if y > 0:
W[k][x][y] += W[k - 1][x][y - 1]
if y < N - 1:
W[k][x][y] += W[k - 1][x][y + 1]
print str(W)

waysalive = 0
for x in range(0, N):
for y in range(0, N):
waysalive += W[n][x][y]

probalive = 1.0 - waystodie / ((waystodie + waysalive) * 1.0)
print waystodie, waysalive, probalive

def test(n, N, x0, y0):
print 'Initial at (%d, %d) in %dx%d island, after %d steps'%(x0, y0, N, N, n)
deadprobability(n, N, x0, y0)

test(1, 1, 0, 0)
test(2, 1, 0, 0)
test(2, 2, 0, 0)
test(2, 3, 1, 1)``````

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

This is Wrong:

``````if x == 0:
waystodie +=  W[k - 1][x][y]
if x == N - 1:
waystodie += W[k - 1][x][y]
if y == 0:
waystodie += W[k - 1][x][y]
if y == N - 1:
waystodie += W[k - 1][x][y]
if x > 0:
W[k][x][y] += W[k - 1][x - 1][y]
if x < N - 1:
W[k][x][y] += W[k - 1][x + 1][y]
if y > 0:
W[k][x][y] += W[k - 1][x][y - 1]
if y < N - 1:
W[k][x][y] += W[k - 1][x][y + 1]``````

Try making better use of O(n^3) space.

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

``````#include <iostream>
#include <vector>

bool isDead(unsigned int N, int x, int y)
{
if (x < 0 || x >= N || y < 0 || y >= N)
{
return true;
}
return false;
}

static unsigned int deadCount = 0;
static unsigned int overallCount = 0;

void computeAllPaths(int x, int y, int n, int N)
{
if (isDead(N, x, y))
{
deadCount += 1;
overallCount += 1;
}
else
{
if ( n > 0)
{
computeAllPaths(x-1, y, n-1, N);
computeAllPaths(x + 1, y, n-1, N);
computeAllPaths(x, y - 1, n-1, N);
computeAllPaths(x, y + 1, n-1, N);
}
else
{
overallCount += 1;
}
}
}

float probabilityofalive(int x, int y, int n, int N)
{
if (x >= 0 && x < N && y >=0 && y< N)
{
deadCount = 0;
overallCount = 0;

computeAllPaths(x, y, n, N);

return (float) deadCount / (float) overallCount;

}

return 1.0;
}

void main()
{
int x = 4;
int y = 4;
int n = 5;
int N = 6;
printf("probability (x:%d, y:%d, N:%d, n:%d) = %f", x, y, N, n, probabilityofalive(x,y,n,N));

getchar();
}``````

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

public static double prop2Alive(int x,int y, int N,int step){
if(x<0 ||y<0||x>=N||y>=N) return 0;
else {
if(step==0) return 1;

return (prop2Alive(x-1,y,N,step-1)+prop2Alive(x,y-1,N,step-1)+prop2Alive(x+1,y,N,step-1)+prop2Alive(x,y+1,N,step-1))/4;
}
}

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

This is my code, it could be optimized by only calling checkBoundary on the borders and exiting the main loop once you reach i==x && j==y && steps == n, but i was going for simplicity of the code here.

``````public class ProbabilityOfAlive {
public static double probabilityOfAlive(int x, int y, int n){
int[][][] island = new int[n][n][2];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
island[i][j][1] = checkBoundary(i,j, n);
for(int steps=2;steps <= n; steps++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++){
int up = (i == 0) ? (int)Math.pow(4, steps-1) : island[i-1][j][(steps-1)%2];
int down = (i == n-1) ? (int)Math.pow(4, steps-1) : island[i+1][j][(steps-1)%2];
int left = (j == 0) ? (int)Math.pow(4, steps-1) : island[i][j-1][(steps-1)%2];
int right = (j == n-1 ) ? (int)Math.pow(4, steps-1) : island[i][j+1][(steps-1)%2];
island[i][j][steps%2] = up + down+left+right;
}
return 1-island[x][y][n%2]/Math.pow(4, n);
}
private static int checkBoundary(int x, int y, int n){
n--;
if(x % n == 0 && y % n == 0)
return 2;
if(x % n == 0 || y % n == 0)
return 1;
return 0;
}
}``````

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

Good Idea, but generalize your code where n != N.
N: Size of matrix;
n: no. of steps to take.

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

For below method,
k: number steps.
N: size of square matrix island.

Considering array alive[N][N][2], where each element in alive[i][j][steps%2] will keep count of the favourable cases.
To calculate this count we just need the result from previous steps, i.e.,
top = alive[i-1][j][(steps-1)%2];
down = alive[i+1][j][(steps-1)%2];
left = alive[i][j-1][(steps-1)%2];
right = alive[i][j+1][(steps-1)%2];

So, favourable cases for alive[i][j][steps%2] = up + down + left + right;

``````// DYNAMIC PROGRAMMING WITH TABULATION IN C++ LANGAUGE.
// S = O(N^2); T = O(K*N*N)
double getProbabilityOfAlive(int x, int y, int k, int N){
int[][][] alive = new int[N][N][2];

// FOR STEPS=0, THIS IS JUST FOR UNDERSTANDING PURPOSE AND CAN BE REMOVED FROM METHOD.
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
alive[i][j][0] = 0; // steps==0.

// FOR STEPS=1, NON-CORNER ELEMENTS AND EDGE ELEMENTS OF MATRIX.
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
if( (i>=1) && (i<=(N-2)) && (j>=1) && (j<=(N-2)) ) {
alive[i][j][1] = 4; // steps==4.
} else if( (i==0) || (i==(N-1)) || (j==0) || (j==(N-1)) ) {
alive[i][j][1] = 3; // steps==3.
}
}
}
alive [0][0][1]     = 2; // for corners of matrix.
alive [0][N-1][1]   = 2; // for corners of matrix.
alive [N-1][0][1]   = 2; // for corners of matrix.
alive [N-1][N-1][1] = 2; // for corners of matrix.

// COUNT ALL FAVOURABLE CASES.
for(steps=2;steps <= k; steps++)
for(i=0; i<N; i++)
for(j=0; j<N; j++){
up    = (i == 0)    ? 0 : alive[i-1][j][(steps-1)%2];
down  = (i == N-1)  ? 0 : alive[i+1][j][(steps-1)%2];
left  = (j == 0)    ? 0 : alive[i][j-1][(steps-1)%2];
right = (j == N-1 ) ? 0 : alive[i][j+1][(steps-1)%2];

alive[i][j][steps%2] = up + down + left + right;
}

totalCases = pow(4, n);
return (alive / totalCases);
}``````

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

update for last line:

``return (alive[x][y][k%2] / totalCases);``

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

Model it as a graph search see how many nodes you visited and how many times you result in a death
{{

def probabilityalive(x,y,nmoves,N):
deaths,moves = getprob((x,y),nmoves,N,0,set())
return 1 - deaths/(1.0 * (moves - 1))

def getprob(xy,nmoves,N,depth,visited):
if xy in visited or depth > nmoves: return 0,0
deaths = 0
x,y = xy
if xy[0] > N-1 or xy[0] < 0 or xy[1] > N-1 or xy[1] < 0:
return 1,1
moves = 1
visited.add(xy)
successors = [(x,y+1),(x,y-1),(x-1,y),(x+1,y)]
for s in successors:
d,m = getprob(s,nmoves,N,depth+1,visited)
deaths += d
moves += m
return deaths,moves

print probabilityalive(5,5,10,10)*100

}}

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

``````def probabilityalive(x,y,nmoves,N):
deaths,moves = getprob((x,y),nmoves,N,0,set())
return 1 - deaths/(1.0 * (moves - 1))

def getprob(xy,nmoves,N,depth,visited):
if xy in visited or depth > nmoves: return 0,0
deaths = 0
x,y = xy
if xy[0] > N-1 or xy[0] < 0 or xy[1] > N-1 or xy[1] < 0:
return 1,1
moves = 1
visited.add(xy)
successors = [(x,y+1),(x,y-1),(x-1,y),(x+1,y)]
for s in successors:
d,m = getprob(s,nmoves,N,depth+1,visited)
deaths += d
moves += m
return deaths,moves

print probabilityalive(5,5,10,10)*100``````

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

``````#!/usr/bin/env python

from collections import defaultdict

calc_table = defaultdict(lambda : 1.0)

def p(n, steps, si, sj):

for k in range(1, steps+1):
for i in range(n):
for j in range(n):
calc_table[(n, k, i, j)] = 0
if i-1 >= 0:
calc_table[(n, k, i, j)] += calc_table[(n, k-1, i-1, j)]
if i+1 < n:
calc_table[(n, k, i, j)] += calc_table[(n, k-1, i+1, j)]
if j-1 >= 0:
calc_table[(n, k, i, j)] += calc_table[(n, k-1, i, j-1)]
if j+1 < n:
calc_table[(n, k, i, j)] += calc_table[(n, k-1, i, j+1)]
calc_table[(n, k, i, j)] /= 4.0

return calc_table[(n, steps, si, sj)]

if __name__ == "__main__":
print p(4, 4, 0, 0)
print p(4, 4, 1, 1)
print p(4, 4, 2, 2)``````

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

Create a quadrant decision tree from the current co-ordinate with depth = n.
While you are constructing the tree, if a branch reached an out of bound condition, increase
deadly branches count by 1. And then move backwards using recursion to construct the next branch and so on. The final count of the bad branches/ the total number of branches is your probability. This is similar to what is used in gaming.

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

public class Island {
private int islandSize = N;
public float getSurvivalProbability(int x, int y, int n) {
if ( x < 0 || x > N - 1 || y < 0 || y > N - 1) {
return 0;
}
else if (n == 0) {
return = 1;
}
else {
return
0.25 * getSurvivalProbability(x - 1, y, n -1) +
0.25 * getSurvivalProbability(x, y - 1, n -1) +
0.25 * getSurvivalProbability(x, y + 1, n -1) +
0.25 * getSurvivalProbability(x + 1, y, n -1);
}
}
public float getDeathProbability(int x, int y, int n) {
return 1 - getSurvivalProbability(x, y);
}
}

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

This can be easily done using BFS. The equation I followed is as below:
ProbAlive(after N steps) = ProbAlive(after 1 step)
* ProbAlive(after 2 steps, given alive after 1 step) *
* ...
* ProbAlive(after N steps, given alive after N-1 steps)

To compute the term ProbAlive(after K steps, given alive after K-1 steps), BFS is used.
When the BFS queue has only elements with positions for kth step, sample space is the queue-size. Iterate through all elements in the queue and if position is valid, add a probability of 1/queue-size to ProbAliveCurStep. During that time, enqueue all subsequent positions with step marked as k+1. Before processing queue with positions marked as k+1, update ProbAlive = ProbAlive * ProbAliveCurStep and reset ProbAliveCurStep.

e.g. For a 4x4 Matrix, max_step 2 and initial pos 0, 0
Iteration 1:
Queue Contents: (x: 0, y: 0, step: 0)
Pop Element: (0, 0, 0)
Sample Space = 0; // Initial position is ignored for probability computation
ProbAliveCurStep = 0;
Enqueue Neighbours

Iteration 2:
Queue Contents: (1, 0, 1), (-1, 0, 1), (0, 1, 1), and (0, -1, 1)
Pop Element: (1, 0, 1) // Valid element, proceed
Sample Space = 4
ProbAliveCurStep = 0.25
Enqueue Neighbours

Iteration 3:
Queue Contents: (-1, 0, 1), (0, 1, 1) and (0, -1, 1)
Pop Element: (-1, 0, 1) // Invalid element, continue
...
...
After 13 iterations,
ProbAliveCurStep for Step 1 = 0.5, ProbAliveCurStep for Step 2 = 0.75
ProbAlive = 0.357

``````float getProb(int x, int y, int n, int maxSteps) {
deque<Pos*> posQueue;
int sampleSpace = 0, curStep = 0;
float probAlive = 0, probAliveCurStep = 0;
posQueue.push_back(new Pos(x, y, curStep));

while(!posQueue.empty()) {
// Pop current element from quque
Pos* curPos = posQueue.front(); posQueue.pop_front();
assert(curPos);
assert((curPos->step == curStep) || (curPos->step == curStep + 1));

// Update the sampleSpace if stepping to the next phase
if (curPos->step != curStep) {
printf("\n Step change detected from %d to %d, updating sample space  to %d", curStep, curPos->step, posQueue.size() + 1);
sampleSpace = posQueue.size() + 1; // One element already popped.
probAlive = probAlive ? probAlive * probAliveCurStep : probAliveCurStep;
probAliveCurStep = 0;
++curStep;
}

// If curPos in safe zone, add to the running probability
if (!(curPos->x < 0 || curPos->y < 0 || curPos->x >= n || curPos->y >= n)) {
// Note: For step-0, no probability is computed.
if (curPos->step) {
float curProb = 1/(float)sampleSpace;
probAliveCurStep += curProb;
}

// Enqueue all neighbours
if (curPos->step < maxSteps) {
posQueue.push_back(new Pos(curPos->x-1, curPos->y, curPos->step + 1));
posQueue.push_back(new Pos(curPos->x+1, curPos->y, curPos->step + 1));
posQueue.push_back(new Pos(curPos->x, curPos->y-1, curPos->step + 1));
posQueue.push_back(new Pos(curPos->x, curPos->y+1, curPos->step + 1));
}
}
}

probAlive *= probAliveCurStep;
return probAlive;
}``````

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

Heres my attempt, not sure if its completely sound. Any advice would be greatly appreciated :)

``````using System;

namespace AliveProblem
{
class MainClass
{
public static int[,] island = new int[4,4];

public static void Main (string[] args)
{
Console.WriteLine(probabilityofalive(1, 1, 5));
}

public static double probabilityofalive(int x, int y, int n) {

//Break case
if (n == 0) return 1;
//corner case
//Top left
if (x == 0 && y == 0) {
return 0.5+0.25*probabilityofalive(x+1, y, n-1)*0.25*probabilityofalive(x, y+1, n-1);
}
//Bottom left
else if (x == 0 && y == island.Length-1) {
return 0.5+0.25*probabilityofalive(x+1, y, n-1)*0.25*probabilityofalive(x, y+1, n-1);
}
//Top right
else if (x == island.Length-1 && y == 0) {
return 0.5+0.25*probabilityofalive(x-1, y, n-1)*0.25*probabilityofalive(x, y-1, n-1);
}
//Bottom right
else if (x == island.Length-1 && y == island.Length-1) {
return 0.5+0.25*probabilityofalive(x-1, y, n-1)*0.25*probabilityofalive(x, y+1, n-1);
}
//Left side
else if (x == 0 && (y != 0 && y!= island.Length-1)  ) {
return 0.25+0.25*probabilityofalive(x, y+1, n-1)*0.25*probabilityofalive(x, y-1, n-1)*0.25*probabilityofalive(x+1, y, n-1);
}

//Right side
else if (x == island.Length-1 && (y!=0 && y!= island.Length-1)) {
return 0.25+0.25*probabilityofalive(x, y+1, n-1)*0.25*probabilityofalive(x, y-1, n-1)*0.25*probabilityofalive(x-1, y, n-1);
}
else if (y == 0 && ( x!= 0 && x!=island.Length-1)) {
return 0.25+0.25*probabilityofalive(x-1, y, n-1)*0.25*probabilityofalive(x+1, y, n-1)*0.25*probabilityofalive(x, y+1, n-1);
}
else if (y == island.Length-1 && (x != 0 && x!= island.Length-1)) {
return 0.25+0.25*probabilityofalive(x-1, y, n-1)*0.25*probabilityofalive(x+1, y, n-1)*0.25*probabilityofalive(x, y-1, n-1);

}
else {
return 0.25*probabilityofalive(x-1, y, n-1)*0.25*probabilityofalive(x+1, y, n-1)*0.25*probabilityofalive(x, y+1, n-1)*0.25*probabilityofalive(x, y-1, n-1);
}``````

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

``````public class Island {
private int[][] fields;

public Island(int size) {
this.fields = new int[size][size];
}

public boolean isInRange(int x, int y) {
return x >= 0 && y >= 0 && x < size() && y < size();
}

public int size() {
return fields.length;
}
}``````

``````public class Walk {
private Island island;

Walk(Island island) {
this.island = island;

}

double walk(int x, int y, int numSteps) {
if(numSteps == 0) {
return 1;
}

double sum = 0;

// Go left
if(island.isInRange(x-1, y)) {
sum += walk(x-1, y, numSteps-1);
}

// Go right
if(island.isInRange(x+1, y)) {
sum += walk(x+1, y, numSteps-1);
}

// Go up
if(island.isInRange(x, y+1)) {
sum += walk(x, y+1, numSteps-1);
}

// Go right
if(island.isInRange(x, y-1)) {
sum += walk(x, y-1, numSteps-1);
}

return sum/4;
}
}``````

``````public class Walk2DArray {
private Island island;

public Walk2DArray(Island island) {
this.island = island;
}

ProbabilityContainer createArray(int numSteps) {
Walk walk = new Walk(island);

ProbabilityContainer result = new ProbabilityContainer(island.size());
for(int i = 0; i < island.size(); i++) {
for(int j = 0; j < island.size(); j++) {
result.set(i, j, walk.walk(i, j, numSteps));
}
}
return result;
}
}``````

-----------------------------------

Unit tests:

``````import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class Walk2DArrayTest {
@Test
public void test1x1_0() {
Island island = new Island(1);
Walk2DArray walk2DArray = new Walk2DArray(island);
ProbabilityContainer probabilityContainer = walk2DArray.createArray(0);
ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
new double[] { 1.0 }
});
assertEquals(expected, probabilityContainer);
}

@Test
public void test1x1_1() {
Island island = new Island(1);
Walk2DArray walk2DArray = new Walk2DArray(island);
ProbabilityContainer probabilityContainer = walk2DArray.createArray(1);
ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
new double[] { 0.0 }
});
assertEquals(expected, probabilityContainer);
}

@Test
public void test2x2_0() {
Island island = new Island(2);
Walk2DArray walk2DArray = new Walk2DArray(island);
ProbabilityContainer probabilityContainer = walk2DArray.createArray(0);
ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
new double[] { 1.0, 1.0},
new double[] { 1.0, 1.0}
});
assertEquals(expected, probabilityContainer);
}

@Test
public void test2x2_1() {
Island island = new Island(2);
Walk2DArray walk2DArray = new Walk2DArray(island);
ProbabilityContainer probabilityContainer = walk2DArray.createArray(1);
ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
new double[] { 0.5, 0.5},
new double[] { 0.5, 0.5}
});
assertEquals(expected, probabilityContainer);
}

@Test
public void test3x3_1() {
Island island = new Island(3);
Walk2DArray walk2DArray = new Walk2DArray(island);
ProbabilityContainer probabilityContainer = walk2DArray.createArray(1);
ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
new double[] { 0.5, 0.75, 0.5},
new double[] { 0.75, 1.0, 0.75},
new double[] { 0.5, 0.75, 0.5}
});
assertEquals(expected, probabilityContainer);
}

@Test
public void test3x3_2() {
Island island = new Island(3);
Walk2DArray walk2DArray = new Walk2DArray(island);
ProbabilityContainer probabilityContainer = walk2DArray.createArray(2);
ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
new double[] { 0.375, 0.5, 0.375},
new double[] { 0.5, 0.75, 0.5},
new double[] { 0.375, 0.5, 0.375}
});
assertEquals(expected, probabilityContainer);
}
}``````

``````import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class WalkTest {
private static final double EPSILON = 0.0000001;

@Test
public void test1x1_0() {
Island island = new Island(1);
Walk walk = new Walk(island);
double prob = walk.walk(0, 0, 0);
assertEquals(1.0, prob, EPSILON);
}

@Test
public void test1x1_1() {
Island island = new Island(1);
Walk walk = new Walk(island);
double prob = walk.walk(0, 0, 1);
assertEquals(0.0, prob, EPSILON);
}

@Test
public void test1x1_2() {
Island island = new Island(1);
Walk walk = new Walk(island);
double prob = walk.walk(0, 0, 2);
assertEquals(0.0, prob, EPSILON);
}

@Test
public void test2x2_1() {
Island island = new Island(2);
Walk walk = new Walk(island);
double prob = walk.walk(1, 1, 1);
assertEquals(0.5, prob, EPSILON);
}

@Test
public void test2x2_2() {
Island island = new Island(2);
Walk walk = new Walk(island);
double prob = walk.walk(0, 0, 2);
assertEquals(0.25, prob, EPSILON);
}

@Test
public void test3x3_2() {
Island island = new Island(3);
Walk walk = new Walk(island);
double prob = walk.walk(0, 0, 2);
assertEquals(0.375, prob, EPSILON);
}

@Test
public void test2x2_3() {
Island island = new Island(2);
Walk walk = new Walk(island);
double prob = walk.walk(0, 0, 3);
assertEquals(0.125, prob, EPSILON);
}
}``````

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

``````public class IslandWanderSurvivalProbability {

static double survivalProbability(int x, int y, int N, int n){
if(x < 0 || x >= N || y < 0 || y >= N){
return 0;
}

double p[][] = new double[N][N];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
p[i][j] = 0.0;
}
}
p[x][y] = 1.0;

p = computeStateSurvivalProbabilities(p, N, n);
double pSum = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
pSum += p[i][j];
}
}

if(n < 3){
for(int i = 0; i < N; i++)
System.out.println(Arrays.toString(p[i]));
}

return pSum;
}

static double[][] computeStateSurvivalProbabilities(double p[][], int N, int n){
double pUptoNMinus1[][] = p;

if(n == 0){
return p;
} else if(n > 1){
pUptoNMinus1 = computeStateSurvivalProbabilities(p,N,n-1);
}

double pNextStep[][] = new double[N][N];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
pNextStep[i][j] = 0.0;
}
}

for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(i+1 < N){
pNextStep[i+1][j] += 0.25*pUptoNMinus1[i][j];
}
if(j+1 < N){
pNextStep[i][j+1] += 0.25*pUptoNMinus1[i][j];
}
if(i-1 >=0){
pNextStep[i-1][j] += 0.25*pUptoNMinus1[i][j];
}
if(j-1 >=0){
pNextStep[i][j-1] += 0.25*pUptoNMinus1[i][j];
}
}
}

return pNextStep;
}

public static void main(String[] args) throws Exception{

for(int n = 0; n < 20; n++){
double pSurvival = survivalProbability(1,1,3,n);
System.out.println(n + "\t" + pSurvival);
}
}
}``````

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

Inspired by you all, I think 3-dimensional DP is trival!

``````double probabilityAliveDP(int x, int y, int N, int step){
if(N==0 || x<0 ||x>=N || y<0 || y>=N ) return 0;
vector<vector<vector<double> > > dp(N+2, vector<vector<double> >(N+2, vector<double>(step+1, 0)));
for(int i=1;i<N+1;i++)
for(int j=1; j<N+1; j++)
dp[i][j][0] = 1.0;

for(int i=1;i<=step;i++){
for(int r = 1; r < N+1; r++){
for(int c = 1; c < N+1; c++){
dp[r][c][i] = 0.25*(dp[r-1][c][i-1]+dp[r+1][c][i-1]+dp[r][c-1][i-1]+dp[r][c+1][i-1]);
}
}
}
return dp[x+1][y+1][step];
}``````

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

My idea is a 3-dimensional dp

``````double probabilityAliveDP(int x, int y, int N, int step){
if(N==0 || x<0 ||x>=N || y<0 || y>=N ) return 0;
vector<vector<vector<double> > > dp(N+2, vector<vector<double> >(N+2, vector<double>(step+1, 0)));
for(int i=1;i<N+1;i++)
for(int j=1; j<N+1; j++)
dp[i][j][0] = 1.0;

for(int i=1;i<=step;i++){
for(int r = 1; r < N+1; r++){
for(int c = 1; c < N+1; c++){
dp[r][c][i] = 0.25*(dp[r-1][c][i-1]+dp[r+1][c][i-1]+dp[r][c-1][i-1]+dp[r][c+1][i-1]);
}
}
}
return dp[x+1][y+1][step];
}``````

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

``````public static double probabilityOfAlive(int x,int y, int step, int n) {
if (x<0 || y<0 || x>=n || y>=n || (n==1 && step==1)) return 0;
if (step == 0) return 1;
double[][][] probTable = new double[n][n][step+1];
int sp = 0;
// init for step=1
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
probTable[i][j][sp] = 0;
if (i>0) probTable[i][j][sp] = 1;
if (j>0) probTable[i][j][sp] = 1;
if (i+1<n) probTable[i][j][sp] = 1;
if (j+1<n) probTable[i][j][sp] = 1;
}
}
// calculate with DP
for(sp=1;sp<=step;sp++) {
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
probTable[i][j][sp] = 0;
if (i>0) probTable[i][j][sp] += 0.25*probTable[i-1][j][sp-1];
if (j>0) probTable[i][j][sp] += 0.25*probTable[i][j-1][sp-1];
if (i+1<n) probTable[i][j][sp] += 0.25*probTable[i+1][j][sp-1];
if (j+1<n) probTable[i][j][sp] += 0.25*probTable[i][j+1][sp-1];
if (sp==step && i==x && j==y) return probTable[x][y][sp];
}
}
}
return probTable[x][y][step];
}``````

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

Wouldn't the following code be sufficient enough?

``````public class ProbabilityOfAlive
{
public final int N = 5;

public static void main(String[] args)
{
ProbabilityOfAlive obj = new ProbabilityOfAlive();
float result = obj.probabilityOfAlive(4, 4, 2);
System.out.println("Result: "+result);
}

public float probabilityOfAlive(int x, int y, int n)
{
// Last step
if(n == 0)
{
if(x>=0 && x<N && y>=0 && y<N)
return 1;
else
return 0;
}

// Dies
else if(x<0 || x>=N || y<0 || y>=N)
{
return 0;
}

// Alive
else
{
float up = probabilityOfAlive(x, y+1, n-1);
float down = probabilityOfAlive(x, y-1, n-1);
float left = probabilityOfAlive(x-1, y, n-1);
float right = probabilityOfAlive(x+1, y, n-1);
return 0.25f*(up+down+left+right);
}

}``````

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

Here's a simple Python solution with memorization

``````mem = None

def prob(x,y,n,N):
global mem
if mem is None:
mem = [[[-1.0 for a in range(n+1)] for b in range(N)] for c in range(N)]
if x < 0 or x >= N or y < 0 or y >= N:
return 0.0
if n == 0:
return 1.0
if mem[x][y][n] > 0:
return mem[x][y][n]
res =  (0.25*prob(x+1,y,n-1,N) +
0.25*prob(x,y+1,n-1,N) +
0.25*prob(x-1,y,n-1,N) +
0.25*prob(x,y-1,n-1,N))
mem[x][y][n] = res
return res

print prob(3,3,50,20)``````

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

``````public static double islandSurvive(int x, int y, int N, int steps) {
double survs = (double) islandHelp(x,y,N,steps);
return survs / Math.pow(4.0, (double) steps);
}

public static int islandHelp(int x, int y, int N, int rem) {
if (x > N-1 || x < 0 || y < 0 || y > N-1) {
return 0;
}
if (rem == 0) { return 1; }
else {
return islandHelp(x+1,y,N,rem-1) +
islandHelp(x-1,y,N,rem-1) +
islandHelp(x,y-1,N,rem-1) +
islandHelp(x,y+1,N,rem-1);
}
}``````

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

``````public static double islandSurvive(int x, int y, int N, int steps) {
double survs = (double) islandHelp(x,y,N,steps);
return survs / Math.pow(4.0, (double) steps);
}

public static int islandHelp(int x, int y, int N, int rem) {
if (x > N-1 || x < 0 || y < 0 || y > N-1) {
return 0;
}
if (rem == 0) { return 1; }
else {
return islandHelp(x+1,y,N,rem-1) +
islandHelp(x-1,y,N,rem-1) +
islandHelp(x,y-1,N,rem-1) +
islandHelp(x,y+1,N,rem-1);
}
}``````

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

Here is an O(1) solution:

``````float probabilityofalive(int x,int y, int n) {
return math.pow(1.0 - 1.0 / x, n);
}``````

Let the simplicity of the answer sink in.

Given a square matrix of size NxN, for any single direction, the probability of dying is 1/N -- that is to say, those on an edge will go into the water. There are four possible directions, each with the same probability, so 4*((1/4)(1/N)) still equals 1/N chance of death on any given turn, or (1 - 1/N) chance of survival.

To survive X times, we raise this probability to that power: (1 - 1/N)^X

Again, look at the code above. Not all problems need to be complex. If you get this problem, don't go right for the formula. Show a 1x1 grid and convince someone that the odds of survival are 0. Repeat this for a 2x2 and a 3x3. Do it for just one step. Why can we just multiply probabilities for subsequent steps? It's because there is an equal probability of landing on any square after a given round. This means that each round is independent, and we can reach back to our statistics classes wherein we learn the the probabilities of independent events can be multiplied to come up with the combined probability.

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

I like the way you're thinking but the question is the probability of dying when starting from a particular square. If I were the person on the island, I would pace in a circle or sit down so as not to fall off but apparently the movements are supposed to be random.

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