Google Interview Question
Software EngineersCountry: 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