Microsoft Interview Question for SDE-2s


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

- tiandiao123 August 30, 2017 | Flag Reply
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.

- tnutty2k8 August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- samsamsamv2 September 11, 2017 | Flag
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
        }
    }

- Anonymous September 04, 2017 | Flag Reply
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
        }
    }

- Jim September 04, 2017 | Flag Reply
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
        }
    }

- Jim Z September 04, 2017 | Flag Reply
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
        }
    }

- Jim Z September 04, 2017 | Flag Reply
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.");
                }

        }

- Kapil September 13, 2017 | Flag Reply
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.");
                }

        }

- Kapil September 13, 2017 | Flag Reply
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);
	}
         
	}

- Anonymous November 16, 2017 | Flag Reply
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);
	}
         
 }

- Munavar.Ahmed.sk November 16, 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