## Google Interview Question

Software Engineers**Country:**United States

**Interview Type:**In-Person

DP solution. Time : O(n^2) Space: O(N^2)

```
boolean find(int[] a){
int n = a.length;
boolean[][] mat = new boolean[n][n];
if(a[0] != 1 || a[1] != 1) return false;
mat[1][0] = mat[1][1] = true;
for(int i = 1; i < n; i++){
if(a[i] == 0) continue;
for(int j = 1; j < n; j++){
if(mat[j][i]){
if(j > 1){
if(i + j -1 < n) mat[j-1][i+j-1] = (a[i+j-1] == 1);
else return true;
}
if(i + j < n) mat[j][i+j] = (a[i+j] == 1);
else return true;
if(i + j + 1 < n) mat[j+1][i+j+1] = (a[i+j+1] == 1);
else return true;
}
}
}
return false;
}
```

```
static boolean find(int[] a){
int n = a.length;
boolean[][] mat = new boolean[n][n];
if(a[0] != 1 || a[1] != 1) return false;
mat[1][0] = mat[1][1] = true;
for(int i = 1; i < n; i++){
if(a[i] == 0) continue;
for(int j = 1; j < n; j++){
if(mat[j][i]){
if(j > 1){
if(i + j -1 < n) mat[j-1][i+j-1] = (a[i+j-1] == 1);
else return true;
}
if(i + j < n) mat[j][i+j] = (a[i+j] == 1);
else return true;
if(i + j + 1 < n) mat[j+1][i+j+1] = (a[i+j+1] == 1);
else return true;
}
}
}
return false;
}
```

```
#include <iostream>
#include <string.h>
using namespace std;
int count = 0;
int cache[10];
bool canPass(int arr[], int n, int pos, int v) {
count++;
if (pos >= n)
return true;
if ((v <= 0) || arr[pos] == 0)
return false;
if (cache[v] != -1)
return cache[pos];
return cache[v] = canPass(arr, n, (pos + v), v) || canPass(arr, n, (pos + (v - 1)), (v - 1)) ||
canPass(arr, n, (pos + (v + 1)), (v + 1));
}
int main() {
int pass[] = {1,1,0,1,0,1,1,1,0,1};
int N = sizeof(pass) / sizeof(pass[0]);
memset(cache, -1, sizeof(cache));
cout << canPass(pass, (N - 1), 0, 1);
cout << endl << count;
return 0;
}
```

@missing, how can you pass 1,1,1,1,1,1,0,0,0,0? please provide the jumps

best I see from your description is 0-->2, 2--> 5, 5 --> 9, but 9 is 0, so can't

other interpretations of your question may be: 0-->3, 3-->7, but 7 is 0, so can't pass

I don't see how you can pass that array with the problem statement given, please clearify

EDITED July 7th '17:

- changed the assumption about start condition

- added the decrease jump into the recursion

- specified more clearly assumption what "jump of 1" means

- corrected some typos

Assumption:

- the first field must be 1, because that's where it starts, then one can decide to

jump to the 2nd field (keep jump of 1) or the 3rd (increase)

- jump of 1 means jumping from e.g. index 0 to 1, increase that jump by 1, it jumps

from 1 to 3 etc.

Solution:

First start by writing down the recursion of the problem:

this has O(3^n) time complexity, because at most recursion step, it spans three

execution, so it doubles at every step and there are n steps. space is O(n),

used by call stack. There is a tighter bound although.

improvement is memorization which brings it down to O(n^2) time complexity.

alternatively an iterative solution can be created with O(n^2) time and

space complexity.

in python 3

- Chris July 07, 2017