Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
What are the constraints?
What is the state of the game?
How many allowed values sets are possible?
Example 1:
Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.
Example 2:
Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true
Example 3:
Input: maxChoosableInteger = 10, desiredTotal = 1
Output: trueMatch what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
The strategy is to avoid repeatedly solving sub-problems. That is a clue to use memoization. Memoization is a way to potentially make functions that use recursion run faster. How we define the state of the game determines how we will do memoization as well. Clearly list of current allowed numbers are needed to define the state. Therefore only allowed values uniquely determine the state. Memoizing allows us to store input alongside the result of the calculation. Therefore, rather than having to do the same work again using the same input, it can simply return the value stored in the cache.
⚠️ Common Mistakes
Plan the solution with appropriate visualizations and pseudocode.
We create an array allowed which has all the integers from 1 to maxChoosableInteger.
At each state, if the maximum usable number plus the numbers you already summed up (denote as already) is greater than the desired total, it means you can definitely win at this state.
Else, you loop through the usable numbers, each time pick one number, and see whether your opponent can win at the new state. If he can't, then you can win. And remember to cache the result.Implement the code to solve the algorithm.
class Solution(object):
def canIWin(self, maxChoosableInteger, desiredTotal):
from math import *
usable = [x for x in range(1,maxChoosableInteger +1)]
if (1+ maxChoosableInteger) * maxChoosableInteger <= desiredTotal:
return False
else:
return self.hint(maxChoosableInteger,desiredTotal,usable,{},0)
def hint(self,maxChoosbleInt,desiredTotal,usable,cache,already):
if len(usable) == 0:
return False
else:
state = tuple(usable)
if state in cache:
return cache[state]
else:
cache[state] = False
if max(usable) + already >= desiredTotal:
cache[state] = True
elif len(usable) >1 and max(usable) + already >= desiredTotal:
cache[state] = False
else:
for x in usable:
newstate = [y for y in usable if y!= x]
if not self.hint(maxChoosbleInt,desiredTotal,newstate,cache,already + x):
cache[state] = True
break
return cache[state] Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Given n is maxChoosableInteger,
Time Complexity: O(2^n), for any given state of choices, the remainder must be the same since there is a relationship between the two variable of remainder = summed_choices - sum(choices), all of which are constant.
Space Complexity: O(n)
