Microsoft Interview Question for Software Developers


Team: Office
Country: United States
Interview Type: In-Person




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

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 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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");
        }

- mtecl.prg December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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");
        }

- mtecl.prg December 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There may be no solution for an array like:
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}.
In this case, since we cannot jump outright, the only possible solution is 4. The next jump has to be 3, 4 or 5 which will land us in the water.

- haroud December 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- trollingpeeper December 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anuprao85 December 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- anonymity December 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes correct.

- anuprao85 December 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- lepeisi December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes first jump can be any number but it shouldn't be direct jump to destination obviously.

- Anonymous December 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- puneet.sohi December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Some code:

A is our bool arr
i = 0
flag = false;
while (i < size of A)
    if A(i) == true
	possible starting point 
	call recusive fn with starting jump of len i
    	if the above call returns with true value, exit and return true
   else
	i++

- puneet.sohi December 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Akhil December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
}

- Anonymous December 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
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);
}
}

}

- Pkar December 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}
}

- Anonymous December 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is not really the question. I suspect the interviewee got confused. The question is more like a frog can jump 1stone or 2 stones at a time. can he get to the end, if yes print all possible paths.

- Abhi March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- kbkunalb September 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        
    }
};

- Keshav Taparia November 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }

- Neelavan April 06, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More