Google Question - Paint Fence with circular fences
Summary
I was asked a variation of the classic Paint Fence problem where the fences are arranged in a circular manner, making the first and last fence adjacent. I couldn't solve it during the interview.
Full Experience
Hi, yesterday I had interview with google, where I was asked question paint fence question (leetcode 276) but with a variation that fences are in circular order, that means first and last fence are adjacent. I was not able to solve it, later I asked claude, chatgpt, gemini, they were also not able to solve it. Do you guyz have any idea!
Interview Questions (1)
Paint Fence with Circular Adjacency
Given n fences and k colors, paint all the fences such that no two adjacent fences (including the first and last fence which are considered adjacent due to circular arrangement) have the same color. Return the total number of ways to paint the fence.