## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
3
of 5 vote

It's a Dynamic Programming problem with recursive function as

CanReach(i,j) = { true if stone[i] is true && (CanReach[i-j][j-1] || CanReach[i-j][j] ||CanReach[i-j][j+1])
where,
i is the stone
j is the velocity when the frog reached i

``````bool CanCross(vector<bool> vecStones)
{
vecStones.push_back(true); // last true for the land, it makes things simpler
int size = vecStones.size();
vector<vector<bool>> vecCanReach(size, vector<bool>(size, false));

vecCanReach[0][1] = true;
for (int i = 1; i < size; i++)
{
if (vecStones[i] == false)
continue;
for (int j = i - 1; j >= 0; j--)
{
if (vecStones[j] == false)
continue;
if (vecCanReach[j][i - j] || ((i - j - 1 >= 0) && vecCanReach[j][i - j - 1]) || ((i - j + 1 < size) && vecCanReach[j][i - j + 1]))
vecCanReach[i][i - j] = true;
}
}

for (int i = 0; i < size; i++)
{
if (vecCanReach[size - 1][i])
return true;
}
return false;
}``````

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

This code does't work for
{true, false, true, false, false, true};

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

Search all options but do not revisit states (position, speed).

``````unordered_set<pair<int, int>> visited;
bool CanCross(vector<bool> field, int i, int speed) {
if (i >= field.size())
return true;
pair<int, int> state(i, speed);
if (!field[i] || speed <= 0 || visited.count(state))
return false;
visited.insert(state);
return CanCross(field, i+speed, speed)
|| CanCross(field, i+speed+1, speed+1)
|| CanCross(field, i+speed-1, speed-1);
}``````

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

Pretty smart, but please rename variable "i" to "index"

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

``````bool CanCross(vector<bool>& field, int index, int velocity,
vector<vector<bool>>& cache) {
if (index >= field.size())
return true;
if (!field[index] || velosity <= 0 || cache[index][velocity])
return false;
cache[index][velocity] = true;
return CanCross(field, index+velocity, velocity) ||
CanCross(field, index+velocity+1, velocity+1) ||
CanCross(field, index+velocity-1, velocity-1);
}``````

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

Here's a solution is python. Pretty easy to understand

``````def canCrossHelper(path, v, index):
if index >= len(path):
return True
if v <= 0:
return False
if path[index] == False:
return False
if canCrossHelper(path, v+1, index + v + 1) or canCrossHelper(path, v-1, index + v - 1) or canCrossHelper(path, v, index + v):
return True
return False

def canCross(path):
return canCrossHelper(path, 1, 0)``````

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

That approach is too slow for big inputs. You should not revisit the same search states (index, v)

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

``````def canCrossHelper(path, vp, answersArr):
if vp[1] >= len(path):
return True
if vp[0] <= 0:
return False
if path[vp[1]] == False:
return False

tup = (vp[0] + 1, vp[1] + vp[0] + 1)

tup2 = (vp[0], vp[1] + vp[0])

tup1 = (vp[0] - 1, vp[1] + vp[0] - 1)

return True
return False

def canCross(path):
return canCrossHelper(path, (1,0), dict())``````

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

I just use recursion plus memoization, by using a HashSet to store all the (index, velocity) pairs I have seen.

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

class CrossArray {
private static HashSet<String> visited = new HashSet<String>();

public static boolean canCross(boolean arr[]) {
return canCrossHelper(arr, 0, 1);
}

public static boolean canCrossHelper(boolean arr[], int index, int velocity) {
String key = "" + index + "-" + velocity;
if(visited.contains(key))
return false;
for(int v=velocity-1; v<=velocity+1; v++) {
if(v == 0)
continue;
int newIndex = v+index;
if(newIndex >= arr.length)
return true;
if(arr[newIndex] && canCrossHelper(arr, newIndex, v))
return true;
}
return false;
}

public static void main(String[] args) {
boolean arr[] = new boolean[]
{true, true, false, true, false, true, false, false, false, true};
boolean arr2[] = new boolean[]
{true, true, false, true, false, true, true, false, false, true, false};
System.out.println(canCross(arr));
System.out.println(canCross(arr2));
}
}``````

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

{true, true, false, true, false, true, false, false, false, true}: how this doesn't get a route? Can somebody explain the problem statement still clear?

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

Here is C# Code

``````public static void VelocityJump()
{
bool[] just = { true, true, false, true, false, true, true, false, false, true, false };
int velocity = 1;
for (int i = 0; i < just.Length; i += velocity)
{
if (i == just.Length - 1 || i + velocity == just.Length - 1 || i + velocity + 1 == just.Length - 1)
{
Console.WriteLine("Rabbit can cross");
break;
}
if (!just[i] || i + (velocity - 1) >= just.Length || i + velocity >= just.Length)
{
Console.WriteLine("Rabbit can not jump");
break;
}
if ((i+velocity+1 < just.Length) && (just[i + velocity + 1]))
velocity++;
else if ((i+velocity<just.Length) && !just[i+velocity])
{
if (i != 0) velocity--;
}
}
}``````

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.