Huawei Interview Question for Software Engineers
- 0of 0 votes
AnswerProblem:
- yangsuli August 13, 2017
Given 100 stones, two players alternate to take stones out. One can take any number from 1 to 15; however, one cannot take any number that was already taken. If in the end of the game, there is k stones left, but 1 - k have all been previously taken, one can take k stones. The one who takes the last stone wins. How can the first player always win?
My Idea
Use recursion (or dynamic programming). Base case 1, where player 1 has a winning strategy.
Reducing: for n stones left, if palyer 1 takes m1 stones, he has to ensure that for all options player 2 has (m2), he has a winning strategy. Thus the problem is reduced to (n - m1 - m2).
Follow Up Question:
If one uses DP, the potential number of tables to be filled is large (2^15), since the available options left depend on the history, which has 2^15 possibilities.
How can you optimize?
I don't have a great answer to the follow up question。。。| Report Duplicate | Flag | PURGE
Huawei Software Engineer Dynamic Programming
I don't understand how the game works:
- Chris August 13, 2017- is k a number given, e.g. one can take 100-k stones, the first who exceeds this
range, looses - or the last who is within the range wins?
- or is it that the person who can't take the last k <= 15 stones wins?
- or anything other?