Microsoft Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

DP Soln. -

public static void main(String[] args) {
		int[][] snakes = {{99, 78}, {95, 75}, {93, 73}, {87, 24}, {64, 60}, {62, 19}, {54, 34}, {17, 7}};
	    int[][] ladders = {{4, 14}, {9, 31}, {20, 38}, {28, 84}, {51, 67}, {63, 81}, {71, 91}};

		int m = minThrowsDP(snakes, ladders);
		System.out.println(m);
		
	}

	public static int minThrowsDP(int[][] snakes, int[][] ladders){
		int[] dp = new int[101];
		for(int i = 7; i < 101; i++){
			dp[i] = Integer.MAX_VALUE;
		}
		
		for(int i = 7; i <= 100; i++){
			for(int k = 1; k <= 6; k++){
				dp[i] = Math.min(dp[i], dp[i-k]+1);
			}
			for (int p = 0; p < ladders.length; p++){
				if (ladders[p][0] == i){
					dp[ladders[p][1]] = dp[i];
				}
			}
		}
	    return dp[100];		
	}

- sudip.innovates October 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could you please explain this section?

for (int p = 0; p < ladders.length; p++){
				if (ladders[p][0] == i){
					dp[ladders[p][1]] = dp[i];
				}
			}

- Anu November 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

bool sixesThrowAgain = true;

void init() {
srand((unsigned int)time(NULL));
}

int rollDice() {
return rand() % 6 + 1;
}

int nextSquare(int square) {
switch (square) {
case 4: return 14;
case 9: return 31;
case 17: return 7;
case 20: return 38;
case 28: return 84;
case 40: return 59;
case 51: return 67;
case 54: return 34;
case 62: return 19;
case 63: return 81;
case 64: return 60;
case 71: return 91;
case 87: return 24;
case 93: return 73;
case 95: return 75;
case 99: return 78;
default: return square;
}
}

int turn(int player, int square) {
int roll, next;
while (true) {
roll = rollDice();
printf("Player %d, on square %d, rolls a %d", player, square, roll);
if (square + roll > 100) {
printf(" but cannot move.\n");
} else {
square += roll;
printf(" and moves to square %d\n", square);
if (square == 100) return 100;
next = nextSquare(square);
if (square < next) {
printf("Yay! Landed on a ladder. Climb up to %d.\n", next);
square = next;
} else if (next < square) {
printf("Oops! landed on a snake. Slither down to %d.\n", next);
square = next;
}
}
if (roll < 6 || !sixesThrowAgain) return square;
printf("Rolled a 6 so roll again.\n");
}
}

int main() {
int players[3] = { 1, 1, 1 };
int i, ns;

init();

while (true) {
for (i = 0; i < sizeof(players) / sizeof(int); ++i) {
ns = turn(i + 1, players[i]);
if (ns == 100) {
printf("Player %d wins!\n", i + 1);
goto out;
}
players[i] = ns;
printf("\n");
}
}

out:
return 0;
}

- yatendra.br April 10, 2020 | 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