Microsoft Interview Question
Software DevelopersTeam: Office
Country: United States
Interview Type: In-Person
c#
public static void Start()
{
TestStones(true, new bool[] { true, true, true, true });
TestStones(false, new bool[] { false, false, false });
TestStones(true, new bool[] { true, true, false, true, false });
TestStones(false, new bool[] { false, true, false, false, true, false });
}
public static bool CheckPath(bool[] stones)
{
for (int initialJump = 1; initialJump < (stones.Length / 2) + 1; initialJump++)
{
if (CheckPath(stones, initialJump, initialJump))
return true;
}
return false;
}
public static bool CheckPath(bool[] stones, int currentStone, int prevJumpLen)
{
if (currentStone >= stones.Length)
return true;
if (!stones[currentStone])
return false;
for (int lenMod = (prevJumpLen > 1) ? -1 : 0; lenMod < 2; lenMod++ )
{
int jumpLen = prevJumpLen + lenMod;
if(CheckPath(stones, currentStone + jumpLen, jumpLen))
return true;
}
return false;
}
private static void TestStones(bool expectedResult, bool[] stones)
{
if (expectedResult != CheckPath(stones))
throw new Exception("Failed");
Console.WriteLine("ok");
}
Actually there should ne different approach to find initial jump length - at least it should iterate from longest initial step.
But should be also cleared what is last jump - if it is every jump from stone to somewhere after end of the array (as I expected in my code), then actually each river with one stone has solution :) So let's assume that latest jump must point exactly to index equals to river width:
public static void Start()
{
TestStones(true, new bool[] { true, true, true, true });
TestStones(false, new bool[] { false, false, false });
TestStones(true, new bool[] { true, true, false, true, false });
TestStones(false, new bool[] { false, true, false, false, true, false });
Console.ReadLine();
}
public static bool CheckPath(bool[] stones)
{
for (int initialJump = (stones.Length / 2) + 1; initialJump > 0; initialJump--)
{
if (CheckPath(stones, initialJump, initialJump))
return true;
}
return false;
}
public static bool CheckPath(bool[] stones, int currentStone, int prevJumpLen)
{
if (currentStone >= stones.Length)
return currentStone == stones.Length;
if (!stones[currentStone])
return false;
for (int lenMod = (prevJumpLen > 1) ? -1 : 0; lenMod < 2; lenMod++ )
{
int jumpLen = prevJumpLen + lenMod;
if(CheckPath(stones, currentStone + jumpLen, jumpLen))
return true;
}
return false;
}
private static void TestStones(bool expectedResult, bool[] stones)
{
if (expectedResult != CheckPath(stones))
throw new Exception("Failed");
Console.WriteLine("ok");
}
What does the question say about the starting point? Is the question about one of these 3 options to be true to reach to the end? Not very clear with what being asked here.
frog should reach one point ( starting point ) to another point ( destination point ).
To reach destination frog requires to jump to stones only.
Frog jump shouldn't be random, but must fulfill either one condition out of 3 condition mentioned in a question.
e.g. If first jump is 3 , then next jump must be either 2(jump - 1) or 3(same jump) or 4( jump + 1 ) and so on. jump must be on stone not on water in river.
Is frog able to skip stones?
e.g. If there are stones on index 1,2,3,4,5,6. Is frog able to jump to 2,4,6?
If the first jump can be any number, then the frog can just jump from start to end directly.
You must have some kind of constraint on the first jump.
Please clarify.
Dynamic Programming / Recrusion should give us a natural solution.
Walk the bool array till you find a value of 1.
This represents a possible starting point for sequence of jumps.
Now make a recursive call with this position as the starting point and see if from can reach the other end.
If yes, search over.
if no continue walking the array till next true value found and similarly recurse over it.
This is the simplest solution I can think of. It can take some improvements, but the question itself is not
clear.
For convenience I have used int Array with 1 and 0. PFB program:
package com.frogjump;
public class CanFrogJumpThePond {
static int pond[] = { 1, 0, 1, 0, 1, 0, 0, 1 };
public static void main(String[] args) {
System.out.println("Frog Path : "+findPathAcrossThePond());
}
public static String findPathAcrossThePond() {
String path = "";
int halfway = pond.length / 2;
int firstJumpPos = 0;
while (firstJumpPos < halfway) {
if (pond[firstJumpPos] == 1) {
path=findPathAcrossThePond(firstJumpPos, firstJumpPos+1);
if(!path.isEmpty()){
path=String.valueOf(firstJumpPos)+"->"+path;
break;
}
} else {
firstJumpPos++;
}
}
return path;
}
public static String findPathAcrossThePond(int currPos, int previousJumpLen) {
String partialPath = "";
int nextJumpPos = 0;
int nextJumpLen = 0;
// Same Jump length
nextJumpPos = currPos + previousJumpLen;
nextJumpLen = previousJumpLen;
if (nextJumpPos < pond.length - 1) {
if (pond[nextJumpPos] == 1) {
partialPath = findPathAcrossThePond(nextJumpPos, nextJumpLen);
if (!partialPath.isEmpty()) {
return String.valueOf(nextJumpPos) + "->" + partialPath;
}
}
} else if (nextJumpPos == pond.length - 1) {
return String.valueOf(nextJumpPos);
}
// +1 Jump length
nextJumpPos = currPos + previousJumpLen + 1;
nextJumpLen = previousJumpLen + 1;
if (nextJumpPos < pond.length - 1) {
if (pond[nextJumpPos] == 1) {
partialPath = findPathAcrossThePond(nextJumpPos, nextJumpLen);
if (!partialPath.isEmpty()) {
return String.valueOf(nextJumpPos) + "->" + partialPath;
}
}
} else if (nextJumpPos == pond.length - 1) {
return String.valueOf(nextJumpPos);
}
// -1 Jump length
nextJumpPos = currPos + previousJumpLen - 1;
nextJumpLen = previousJumpLen - 1;
if (nextJumpPos < pond.length - 1) {
if (pond[nextJumpPos] == 1) {
partialPath = findPathAcrossThePond(nextJumpPos, nextJumpLen);
if (!partialPath.isEmpty()) {
return String.valueOf(nextJumpPos) + "->" + partialPath;
}
}
} else if (nextJumpPos == pond.length - 1) {
return String.valueOf(nextJumpPos);
}
return partialPath;
}
}
Result:
Frog Path : 0->2->4->7
int CheckJumpPath(int InitialJump, int CurrentStone,bool stones[], int stonesLen)
{
PrevJump = InitialJump;
InitialJump;
int PathResult = 0;
NextJumpAttempt1 = CurrentStone+InitialJump+1;
NextJumpAttempt2 = CurrentStone+InitialJump+0;
NextJumpAttempt3 = CurrentStone+(InitialJump-1);
if(NextJumpAttempt1 < stonesLen && stones[NextJumpAttempt1]==true)
{
if(NextJumpAttempt1 == stonesLen-1) return true;
PathResult += CheckPathInitialJump,NextJumpAttempt1, stones, stonesLen);
}
if (NextJumpAttempt2 < stonesLen && stones[NextJumpAttempt2]==true)
{
if(NextJumpAttempt2 == stonesLen-1) return true;
PathResult += CheckPath(InitialJump, NextJumpAttempt2, stones, stonesLen);
}
if (NextJumpAttempt3 > 0 && NextJumpAttempt3 < stonesLen && stones[NextJumpAttempt3]==true)
{
if(NextJumpAttempt3 == stonesLen-1) return true;
PathResult += CheckPath(InitialJump, NextJumpAttempt3, stones, stonesLen);
}
return PathResult;
}
Bool CheckIfFrogCanJump(int stones[], int stonesLen)
{
int i=0;
int PathResult = 0;
for(i=0; i<stonesLen/2; i++)
{
if(stones[i])
{
PathResult += CheckJumpPath(i, i,stones, stonesLen);
}
}
if(PathResult)
{
printf("Frog can reach destination %d ways",PathResult);
}
else
{
printf("Frog cannot reach the destination");
}
}
{
int CheckJumpPath(int InitialJump, int CurrentStone,bool stones[], int stonesLen)
{
PrevJump = InitialJump;
InitialJump;
int PathResult = 0;
NextJumpAttempt1 = CurrentStone+InitialJump+1;
NextJumpAttempt2 = CurrentStone+InitialJump+0;
NextJumpAttempt3 = CurrentStone+(InitialJump-1);
if(NextJumpAttempt1 < stonesLen && stones[NextJumpAttempt1]==true)
{
if(NextJumpAttempt1 == stonesLen-1) return true;
PathResult += CheckPathInitialJump,NextJumpAttempt1, stones, stonesLen);
}
if (NextJumpAttempt2 < stonesLen && stones[NextJumpAttempt2]==true)
{
if(NextJumpAttempt2 == stonesLen-1) return true;
PathResult += CheckPath(InitialJump, NextJumpAttempt2, stones, stonesLen);
}
if (NextJumpAttempt3 > 0 && NextJumpAttempt3 < stonesLen && stones[NextJumpAttempt3]==true)
{
if(NextJumpAttempt3 == stonesLen-1) return true;
PathResult += CheckPath(InitialJump, NextJumpAttempt3, stones, stonesLen);
}
return PathResult;
}
Bool CheckIfFrogCanJump(int stones[], int stonesLen)
{
int i=0;
int PathResult = 0;
for(i=0; i<stonesLen/2; i++)
{
if(stones[i])
{
PathResult += CheckJumpPath(i, i,stones, stonesLen);
}
}
if(PathResult)
{
printf("Frog can reach destination %d ways",PathResult);
}
else
{
printf("Frog cannot reach the destination",PathResult);
}
}
}
int CheckJumpPath(int InitialJump, int CurrentStone,bool stones[], int stonesLen)
{
PrevJump = InitialJump;
InitialJump;
int PathResult = 0;
NextJumpAttempt1 = CurrentStone+InitialJump+1;
NextJumpAttempt2 = CurrentStone+InitialJump+0;
NextJumpAttempt3 = CurrentStone+(InitialJump-1);
if(NextJumpAttempt1 < stonesLen && stones[NextJumpAttempt1]==true)
{
if(NextJumpAttempt1 == stonesLen-1) return true;
PathResult += CheckPathInitialJump,NextJumpAttempt1, stones, stonesLen);
}
if (NextJumpAttempt2 < stonesLen && stones[NextJumpAttempt2]==true)
{
if(NextJumpAttempt2 == stonesLen-1) return true;
PathResult += CheckPath(InitialJump, NextJumpAttempt2, stones, stonesLen);
}
if (NextJumpAttempt3 > 0 && NextJumpAttempt3 < stonesLen && stones[NextJumpAttempt3]==true)
{
if(NextJumpAttempt3 == stonesLen-1) return true;
PathResult += CheckPath(InitialJump, NextJumpAttempt3, stones, stonesLen);
}
return PathResult;
}
Bool CheckIfFrogCanJump(int stones[], int stonesLen)
{
int i=0;
int PathResult = 0;
for(i=0; i<stonesLen/2; i++)
{
if(stones[i])
{
PathResult += CheckJumpPath(i, i,stones, stonesLen);
}
}
if(PathResult)
{
printf("Frog can reach destination %d ways",PathResult);
}
else
{
printf("Frog cannot reach the destination",PathResult);
}
}
#include<iostream>
#include<vector>
using namespace std;
bool jump( bool river[], int n, int initial, int curr) {
if(initial >= n)
return false;
if(initial <=0)
return false;
if( ((curr + initial) < n) && !river[curr + initial])
return false;
if( (curr + initial) >= n)
return true;
else
return (jump(river,n,initial,curr+initial) || jump(river,n,initial-1,curr+initial-1) || jump(river,n,initial+1,curr+initial+1));
}
bool is_possible(bool river[] , int n) {
for(int i=0; i< n; i++) {
if(river[i]) {
if(jump(river, n, i+1, 0))
return true;
}
}
return false;
}
int main() {
bool river[] = { true, false, false, true, false, false, true, true, true, false, false, false, true, false, false, false, true, true, false, false, false}; // River of stones where jump is either allowed or not allowed
int n = sizeof(river)/sizeof(river[0]);
if( is_possible(river, n) )
cout << " Frog CAN jump " << endl;
else
cout << " Frog CANNOT jump " << endl;
bool river2[] = { true, false, false, true, false, false, true, true, true, false, false, false, true, false, false, false, true, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}; // River of stones where jump is either allowed or not allowed
n = sizeof(river2)/sizeof(river2[0]);
if( is_possible(river2, n) )
cout << " Frog CAN jump " << endl;
else
cout << " Frog CANNOT jump " << endl;
return 0;
}
what's wrong in this??
class Solution {
public:
bool canCross(vector<int>& A) {
int n1=A.size();
if(n1==1)
return true;
if(A[1]!=1)
return false;
vector<unordered_map<int,bool>> dp(n1);
dp[1].insert({1,true});
for(int i=2;i<n1;i++)
{
for(int j=0;j<i;j++)
{
// cout << A[i]-A[j] << endl;
if(dp[j].find(A[i]-A[j])!=dp[j].end())
dp[i][A[i]-A[j]]=true;
if(dp[j].find(A[i]-A[j]+1)!=dp[j].end())
dp[i][A[i]-A[j]]=true;
if(dp[j].find(A[i]-A[j]-1)!=dp[j].end())
dp[i][A[i]-A[j]]=true;
}
}
if(dp[n1-1].size())
return true;
return false;
}
};
We can keep tracking of previous jump .
public static bool FrogJump(bool[] array)
{
int lastJump = 0;
bool canCross = true;
for (int i = 0; i < array.Count(); i++)
{
if (array[i] == true)
{
int tempJump = 0;
for (int j = 1; j < array.Count()-i; j++)
{
tempJump = j;
if (tempJump > lastJump + 1)
{
canCross = false;
break;
}
if (array[i + tempJump] == false)
{
i = i + j;
break;
}
}
lastJump = tempJump;
}
}
return canCross;
}
Use DP with n^2 storage dp[current pos in array][current jump from that pos] and and is any cell in first column with value 1
- Anonymous December 02, 2015