(on the phone screen, my code was written on a Google Doc that was setup by the interviewer) Write an algorithm that returns every possible painted fence with "x number of posts" with the following conditions, only white and black paints are available and more than 2 fence posts of the same color can appear in a row. Once this was completed I was then asked to generalize this algorithm to work with "k number of colors" and a max run of "n of the same color".

Question

(on the phone screen, my code was written on a Google Doc that was setup by the interviewer) Write an algorithm that returns every possible painted fence with "x number of posts" with the following conditions, only white and black paints are available and more than 2 fence posts of the same color can appear in a row.  Once this was completed I was then asked to generalize this algorithm to work with "k number of colors" and a max run of "n of the same color".

Anonymous · Accepted Answer

I began with seeing this as a permutations problem and started with an iterative solution.  The interviewer asked if there was another approach which lead me to suggest a recursive approach which then triggered the follow up question "Are there any downsides to that?"  After I finished the recursive solution (it was less code and easier to reason about) I was presented with the challenge to generalize it, so I refactored my approach while explaining my work.  The technical challenge of this question seemed basic and the question seemed to be more focused on adapting and staying on top of the code.

Google

Google interview question

Interview Answer

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches