## Google Interview Question for Software Engineers

• 1

Country: United States
Interview Type: In-Person

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

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:

``````recursion = dp(i, j) = max[
dp(i + j, j),               // if i < n and arr[i]
dp(i + j + 1, j + 1),       // if i < n and arr[i]
dp(i + j - 1, j - 1)        // if i < n and arr[i] and j > 1
] // max just acts as or, since dp(...) will return True / False
False, if i < n and not arr[i]
True, if i >= n

i = position, j = jump, n = array length, arr = input-array
passable = dp(0, 1)``````

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

``````# the recursive solution
def is_passable(arr):
def dp(i, j):
if i >= n:
return True #  it
if not arr[i]:
return False # landed on 0
key = i * (n + 1) + j
val = memo.get(key)
if val is not None:
return val
val = dp(i + j, j) # try with same distance jump
if not val: # if not successful, try increasing jump
val = dp(i + j + 1, j + 1)
if not val and j > 1: # if not successful and jump can be decreased
val = dp(i + j - 1, j - 1)

memo[key] = val
return val

n = len(arr)
memo = {}
return dp(0, 1)

# the more elegant iterative solution
def is_passable_itr(arr):
n = len(arr)
dp = [[False for i in range(n + 2)] for j in range(n)]
dp = True # start condition
for i in range(1, n):
if not arr[i]:
continue
for j in range(1, i + 1): # this i + 1 is bad, because at i = 27, max jump is 8 ... etc...
if dp[i - j][j] or dp[i - j][j - 1] or dp[i - j][j + 1]:
dp[i][j] = True
if i + j + 1 >= n:
return True
return False

print(is_passable([1,1,0,1,0,0,1,0,0,1])) # sample with increasing steps
print(is_passable_itr([1,1,0,1,0,0,1,0,0,1]))
print(is_passable([1,1,1,1,1,1,0,0,0,0])) # sample given by missing, that shouldn't work according to my understanding of the problem
print(is_passable_itr([1,1,1,1,1,1,0,0,0,0]))
print(is_passable([1,0,1,0,0,1,0,1,0,0,1])) # sample with increasing steps, decreasing and increasing step
print(is_passable_itr([1,0,1,0,0,1,0,1,0,0,1])) # sample with increasing steps, decreasing and increasing step

#output:
#True
#True
#False
#False
#True
#True``````

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

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 != 1 || a != 1) return false;

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

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

``````static boolean find(int[] a){
int n = a.length;
boolean[][] mat = new boolean[n][n];

if(a != 1 || a != 1) return false;

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

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

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

int count = 0;
int cache;

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);
memset(cache, -1, sizeof(cache));
cout << canPass(pass, (N - 1), 0, 1);
cout << endl << count;
return 0;
}``````

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

@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

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

The code should pass the following test {1,1,1,1,1,1,0,0,0,0};
but does not.

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.