Microsoft Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
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.
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.
/**
*
* @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
}
}
/**
*
* @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
}
}
/**
*
* @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
}
}
/**
*
* @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
}
}
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);
}
}
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);
}
}
- tiandiao123 August 30, 2017