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] = 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
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.