## Microsoft Interview Question for SDE-2s

• 0

Country: United States
Interview Type: In-Person

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

``````public static void main (String[] args) throws java.lang.Exception
{
System.out.println(whoWin(2,3,5));
}

public static int whoWin(int k,int l,int n){
if(n==1){
return 1;
}
Boolean[] used = new Boolean[n];
if(canWin(used,0,k,l)){
return 1;
}
return 2;
}

public static boolean canWin(Boolean[] used,int start,int k,int l){
if(start==used.length){
return false;
}
if(used[start]!=null){
return used[start];
}

if(start+1 == used.length || start+k == used.length || start+l == used.length){
return true;
}

int[] nums = new int[]{1,k,l};
for(int ele:nums){
if(ele+start<=used.length){
if(!canWin(used,ele+start,k,l)){
used[start] = true;
return true;
}
}
}

used[start] = false;
return false;
}``````

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

From N stones, if use can select [1,L] number of stones, I believe whichever user is left with the L + 1, stones is the loser. For example:

``````N = 5; L = 2; x = stone; L + 1 = 3
- xxxxx
- lets put visual group to see better
- (xx)x(xx)
- Starting from left, whichever user empties the first group (xx) first, will win.
- ex: user1 picks 2 stone so we have: x(xx). User1 emptied first group.
- Now user2 can pick 1 or 2 stones but will lose
- ex: user1 picks 1 stone so we have: (x)x(xx).
- Now user2 can pick 1 stone to win; he would empty group first.

- Using the same idea lets try it for higher N
- N = 8
- L = 2
- xxxxxxxx
- (xx)x(xx)x(xx)
- With the same idea, whichever user leaves group1 first can win if played perfect.

Trying it with different parameter:
- N = 8
- L = 3
- x(xxx)x(xxx)
- with the above since we don't start in a group, the first user can lose. Assume user2 emptied group first.``````

I think with the above idea would work, we just need to calculate whether the current user is in first group or not, and from that can deduce if he can win if played perfectly.

Below is a sample code

``````function stonePlay(N, L) {
var numberOfStonesInPlay = N;
var maxPickCount = L;
var i = 0;
var isInGroup = true;
var direction = 1;
while(i < numberOfStonesInPlay) {
if (direction === 1) { //sum group
i += maxPickCount;
isInGroup = true;
direction = 2;
}else {
i++;
isInGroup = false;
direction = 1;
}
}
return isInGroup;
}

console.log('can player1 win: ' + stonePlay(5, 2) ); //true
console.log('can player1 win: ' + stonePlay(8, 2) ); //true
console.log('can player1 win: ' + stonePlay(8, 3) ); //false``````

I compared the result with the result of @tiandiao123 shows, and it seems to match up for the few adhoc input I've tested with. Note I ignored K because for this problem I don't think K is relevant. Maybe someone can comment further. The above might be totally naive, in that case I apologize. I just dont think we need to apply recursion here.

Best.

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

This is a greedy solution and I think it will fail for some case. Even I think K is irrelevant here. The question could have been phrased as upto L stones can be selected every turn. The challenge is to identify which player would win the game. In that case, consider N=2,L=2. Player 1 wins if he selects 2 stones and loses if he selects 1. In this way, either of the players can win so the answer should be both p1 and p2.

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

``````/**
*
* @param n
* @param k
* @param l
* @return Returns 0 if player1 wins, 1 if player2 wins
*/
public static int whoWin(int n, int k, int l) {
if (n < 1 || k < 1 || l < 1 || k >= l) {
throw new IllegalArgumentException();
}

// winTable[i] == ture means for the number i, the current player wins
boolean[] winTable = new boolean[n + 1];

for (int i = 1; i <= n; i++) {
if (i == 1 || i == k || i == l) {
winTable[i] = true;
} else if (!winTable[i - 1]) { // Try pick 1, if the other player loses, I will.
winTable[i] = true;
} else if (i > k && !winTable[i - k]) { // Try pick k
winTable[i] = true;
} else if (i > l && !winTable[i - l]) { // Try piock l
winTable[i] = true;
} else {
winTable[i] = false;
}
}

if (winTable[n]) {
return 0;   // Player 1 wins
} else {
return 1;   // Player 2 wins
}
}``````

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

``````/**
*
* @param n
* @param k
* @param l
* @return Returns 0 if player1 wins, 1 if player2 wins
*/
public static int whoWin(int n, int k, int l) {
if (n < 1 || k < 1 || l < 1 || k >= l) {
throw new IllegalArgumentException();
}

// winTable[i] == ture means for the number i, the current player wins
boolean[] winTable = new boolean[n + 1];

for (int i = 1; i <= n; i++) {
if (i == 1 || i == k || i == l) {
winTable[i] = true;
} else if (!winTable[i - 1]) { // Try pick 1, if the other player loses, I will.
winTable[i] = true;
} else if (i > k && !winTable[i - k]) { // Try pick k
winTable[i] = true;
} else if (i > l && !winTable[i - l]) { // Try piock l
winTable[i] = true;
} else {
winTable[i] = false;
}
}

if (winTable[n]) {
return 0;   // Player 1 wins
} else {
return 1;   // Player 2 wins
}
}``````

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

``````/**
*
* @param n
* @param k
* @param l
* @return Returns 0 if player1 wins, 1 if player2 wins
*/
public static int whoWin(int n, int k, int l) {
if (n < 1 || k < 1 || l < 1 || k >= l) {
throw new IllegalArgumentException();
}

// winTable[i] == ture means for the number i, the current player wins
boolean[] winTable = new boolean[n + 1];

for (int i = 1; i <= n; i++) {
if (i == 1 || i == k || i == l) {
winTable[i] = true;
} else if (!winTable[i - 1]) { // Try pick 1, if the other player loses, I will.
winTable[i] = true;
} else if (i > k && !winTable[i - k]) { // Try pick k
winTable[i] = true;
} else if (i > l && !winTable[i - l]) { // Try piock l
winTable[i] = true;
} else {
winTable[i] = false;
}
}

if (winTable[n]) {
return 0;   // Player 1 wins
} else {
return 1;   // Player 2 wins
}
}``````

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

``````/**
*
* @param n
* @param k
* @param l
* @return Returns 0 if player1 wins, 1 if player2 wins
*/
public static int whoWin(int n, int k, int l) {
if (n < 1 || k < 1 || l < 1 || k >= l) {
throw new IllegalArgumentException();
}

// winTable[i] == ture means for the number i, the current player wins
boolean[] winTable = new boolean[n + 1];

for (int i = 1; i <= n; i++) {
if (i == 1 || i == k || i == l) {
winTable[i] = true;
} else if (!winTable[i - 1]) { // Try pick 1, if the other player loses, I will.
winTable[i] = true;
} else if (i > k && !winTable[i - k]) { // Try pick k
winTable[i] = true;
} else if (i > l && !winTable[i - l]) { // Try piock l
winTable[i] = true;
} else {
winTable[i] = false;
}
}

if (winTable[n]) {
return 0;   // Player 1 wins
} else {
return 1;   // Player 2 wins
}
}``````

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

``````void whoWinTheGame(int n, int l) {

if ((n - 1) % (l+1) != 0) {
System.out.println("Player A win the game.");
} else {
System.out.println("Player b win the game.");
}

}``````

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

``````void whoWinTheGame(int n, int l) {

if ((n - 1) % (l +1)!= 0) {
System.out.println("Player A win the game.");
} else {
System.out.println("Player b win the game.");
}

}``````

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

Its a simple greedy algorithm, just need to figure out in right way. lets say game started with player 0 . other player is player 1. Here is sample C code snippet.
initial call playGame(n,0);
assuming k, l are global vars;

``````playGame(int n, int k, int l, int p){
if(n==1 || n==k || n==l){
printf("player, %d , won the game",p);
return;
}else {
pick in such a way that, next pick should not make a win for other player
//try to pick l, i
if(n>l && n-l!=l && n-l!=k && n-l!=1)
playGame(n-l,1-p);
else if(n>k && n-k!=l && n-k!=k && n-k!=1)
playGame(n-k,1-p);
else //left with no choice
playGame(n-1,1-p);
}

}``````

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

Its a simple greedy algorithm, just need to figure out in right way. lets say game started with player 0 . other player is player 1. Here is sample C code snippet.
initial call playGame(n,0);

``````playGame(int n, int k, int l, int p){
if(n==1 || n==k || n==l){
printf("player, %d , won the game",p);
return;
}else {
//pick in such a way that, next pick should not make a win for other player
//try to pick l
if(n>l && n-l!=l && n-l!=k && n-l!=1)
playGame(n-l,1-p);
//try to pick k
else if(n>k && n-k!=l && n-k!=k && n-k!=1)
playGame(n-k,1-p);
else //pick 1 when left with no choice
playGame(n-1,1-p);
}

}``````

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

Any one please make me understand the question.

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.