If I'm a interviewer, I prefer the candidates using burte force instead of math method.


  • 20
    S

    Because it is a "coding interview", not acm/icpc or other competitions. Similar to Josephus Cycle, I prefer LinkedList Cycle than Mod-Method during interviews. Here's a backtraking-dp solution.

    public class Solution {
        public boolean canWinNim(int n) {
    		    if(n>=134882061){//I have no any other ways,please forgive my unchastity(无节操)!
    			   return n%4 != 0;
    		    }
    		    int[] array=new int[n+1];
    	        return dfs(n, array);
    	 }
    	 public boolean dfs(int n,int[] array){
    		 if(array[n]!=0){
    			 return array[n]==1?true:false;
    		 }
    		 if(n<=3){
    	        	array[n]=1;
    	        	return true;
    	        }else{
    	        	for(int i=1;i<=3;i++){
    	        		if(!dfs(n-i,array)){
    	        			array[n-i]=-1;
    	        			array[n]=1;
    	        			return true;
    	        		}
    	        	}
    	        	array[n]=-1;
    	        	return false;
    	        }
    	 }
    }

  • -3
    A

    Agreed. This is not a coding problem anymore, it's a math problem. It doesn't test your coding skills whatsoever.

    I was using recursion. It went LTE, but I still preferred it rather than return (n % 4 != 0);

    public boolean canWinNim(int n) {
        return canWinNim(n, 0);
    }
    
    public boolean canWinNim(int n, int roundCount) {
        roundCount++;
        if (n <= 0) {
            return false;
        } else if (0 < n && n <= 3) {
            return (roundCount % 2 == 1);
        }
    
        if (roundCount % 2 == 0) {
            return (canWinNim(n-1, roundCount) 
                    && canWinNim(n-2, roundCount) 
                    && canWinNim(n-3, roundCount));
        } else {
            return (canWinNim(n-1, roundCount) 
                    || canWinNim(n-2, roundCount) 
                    || canWinNim(n-3, roundCount));
        }
    }

  • 0
    S

    "array[n-i]=-1;" is redundant, "array[n]=-1;" has assigned "-1" already


  • 4
    V

    I am not a interviewer, however I hold a different opinion, if a problem can be solved with simple algorithm, why shall we implement recursion to make it complicated?

    I would rather say this question from my perspective is not suitable for coding interview, but if it does show, n%4 is preferred.

    Algorithm matters.


  • 0
    H

    the second guy win ,the first must be failed. so just return !(win(n-1)or ... or ... ) will be ok.


  • 0
    S

    Did you solve the 134882061 issue? I use recursion and it give me stack over flow error too...


  • 0
    Y

    memory leak? i would add delete [] array at the end


  • 2
    A

    Surely if you were an interviewer that wanted to see some dynamic programming or something besides the clever math trick, you would choose a different question, that cannot be solved like this. Why on earth would you penalise someone for a clever solution?


  • 0

    If it's recursively, i think DP also makes sense:

    public class Solution {
    public boolean canWinNim(int n) {
    if (n <= 3) {
    return true;
    }
    for (int i = 1; i <= 3; i++) {
    return !canWinNim(n-i);
    }
    return false;
    }
    }

    But of course, would be out of memory


  • 2
    C

    I dont agree. Math is a part of algorithm. So why dont use the best algorithm?


  • 1
    S

    Why don't we try both way? If I was interviewed with this problem, I will using dp to code and then tell the interviewer I figured out a mathematic method which is more efficient but unusual.


  • 1

    No matter what you are an interview or a candidate as a problem solver you should always solve a problem in the easiest way. There could be a lot of options to select to solve a problem but I think the easiest human friendly solution should be selected.


  • 1
    R

    Well, I derived the solution by approaching it as a graph problem, trying to build an algorithm, and the solution ended up being one line :) I think the interviewer will be pleased as long as you demonstrate your thought process.
    But I see your point and kind of agree. It's a good practice to try to solve it using DP.
    Here's my iterative DP solution, but it's failing with the big input test case, like yours:

    public class Solution {
        public bool CanWinNim(int n) 
        {
            if(n < 4) return true;
            if(n == 4) return false;
            
            bool[] dp = new bool[n+1];
            dp[1] = true;
            dp[2] = true;
            dp[3] = true;
            dp[4] = false;
            
            for(int i = 5; i <= n; ++i)
            {
                for(int j = 1; j <= 3; ++j)
                {
                    if(dp[i - j] == false)
                    {
                        dp[i] = true;
                        break;
                    }
                }
            }
            
            return dp[n];
        }
    }
    

  • 0
    T

    @lsy1991121 Can u explain OP's soln? I'm not sure I understand it correctly. Thx!


  • 0
    B
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.