How are we supposed to come up with the O(n) approach for this question? It seems too hard during an interview..


  • 0
    I

    I used an idea similar to paint house ii to do this question, but modified it to get total # of ways instead of minimum Cost. I got a runtime of O(nk^2) and it got a TLE. Afterwards, I looked at other's solutions and was dismayed to discover that my idea seemed completely the wrong way to approach this, and if I got asked this in an interview I probably would have completely failed. What should I do? This is my code btw:

    class Solution(object):
        def numWays(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: int
            """
            if n == 0 or k == 0:
                return 0
            
            ways = [[0 for i in xrange(n)] for j in xrange(k)]
            
            #Base case
            for i in xrange(k):
                ways[i][0] = 1
                
            totalWays = 0
            for i in xrange(1, n):
                for j in xrange(k):
                    for prevColor in xrange(k):
                        if prevColor != j:
                            ways[j][i] += ways[prevColor][i - 1]
                            if i == n - 1:
                                totalWays += ways[prevColor][i - 1]
               
            return totalWays

  • 0
    V

    This is true for so many of us out here. No one says how they reached at there solution and how long it took to crack the logic. If you have solved the question in one way and it is not the best solution then interviewer will provide hints to optimize your solution. This is were they decide to select or reject the candidates if you are able to follow hints and optimize your solution then you are through for the next round.

    Good luck with your preparation.


Log in to reply
 

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