Pocket Gems Interview Question: You and the interviewer play ... | Glassdoor

Interview Question

Software Engineer Interview San Francisco, CA

You and the interviewer play a game. There are piles of

  stones on a table, each with a different number of stones. On your turn, you can take from the table any positive number of stones from any single pile. The person who takes the last stone wins. What's your move?
Answer

Interview Answer

5 Answers

1

Suppose We have 3 piles
Case 1: When 0 stones left implies (Loosing Postion 'L')
              XOR of non of stones in piles is 0^0^0 =0
Case 2: When 1 stone remains in only one pile and rest piles are empty(Winning Pos W)
             XOR of stones 1^0^0=1

So in-general if we play first we should always leave that no.of stones is pile such that XOR of remaining stones is that pile with other piles is 0.

Pragnya Sagar Choudhury on Aug 15, 2012
1

Suppose We have 3 piles
Case 1: When 0 stones left implies (Loosing Postion 'L')
              XOR of non of stones in piles is 0^0^0 =0
Case 2: When 1 stone remains in only one pile and rest piles are empty(Winning Pos W)
             XOR of stones 1^0^0=1

So in-general if we play first we should always leave that no.of stones is pile such that XOR of remaining stones is that pile with other piles is 0.

Pragnya Sagar Choudhury on Aug 15, 2012
0

You want to make sure that all piles have an even number of stones: the XOR answer works only assuming that the amount in each pile is the same.

Anonymous on Sep 3, 2012
2

This problem is well explained in this video
https://www.youtube.com/watch?v=oDniZCmNmNw

Jing on Jun 11, 2015
0

Wondering if anyone tried using Rooftop Slushie? Seems like you can ask questions and get answers from Pocket Gems employees.

https://wwww.rooftopslushie.com

Anonymous on Jul 15, 2019

Add Answers or Comments

To comment on this, Sign In or Sign Up.