Another Google technical interview question that left me stumped. "Write an algorithm that counts the number of ways you can paint a fence with N posts using K colors such that no more than 2 adjacent fence posts are painted with the same color". Here is a recursive approach:

FencePainter.js

var paint = function (posts, colors, display) {
    var painter = function (posts, colors, fence, count, display) {
        var color, total = count;
        if (posts === 0) {
            //Would you like to see them? Pass a display function
            if(display) {
                display(fence);
            }
            return 1;
        } else {
            for (color = 0; color < colors.length; color++) {
                if (canPaint(fence, colors[color])) {
                    total += painter(posts - 1, colors, fence.concat(colors[color]), count, display);
                }
            }
            return total;
        }
    }, canPaint = function (fence, color) {
        var size = fence.length;
        if (fence.length < 2) {
            return true;
        } else if (fence[size - 1] === color && fence[size - 2] === color) {
            return false;
        } else {
            return true;
        }
    };
    return painter(posts, colors, [], 0, display);
};
//And to test it out:
console.log(paint(5, ['black','white'])); //prints 16

//Pass a display function to see the fences
paint(5, ['black', 'white'], function(fence) {console.log(fence);});

["black", "black", "white", "black", "black"]
["black", "black", "white", "black", "white"]
["black", "black", "white", "white", "black"]
["black", "white", "black", "black", "white"]
["black", "white", "black", "white", "black"]
["black", "white", "black", "white", "white"]
["black", "white", "white", "black", "black"]
["black", "white", "white", "black", "white"]
["white", "black", "black", "white", "black"]
["white", "black", "black", "white", "white"]
["white", "black", "white", "black", "black"]
["white", "black", "white", "black", "white"]
["white", "black", "white", "white", "black"]
["white", "white", "black", "black", "white"]
["white", "white", "black", "white", "black"]
["white", "white", "black", "white", "white"]

//Or if you want to be really fance(and use jQuery) (demo found here - http://jsfiddle.net/phbeW/)
$(function() {
    var body = $('body');
    //Pass a display function to see the fences
    paint(10, ['black', 'white'], function(fence) {
        var row = $('<div/>').addClass('Fence'), post, index;
        for(index = 0; index < fence.length; index++) {
            row.append($('<div/>').addClass('Post').css({'backgroundColor':fence[index]}));
        }
        body.append(row);
    });
});
//With the following CSS:
/*
div.Post {
    border: solid black thin;
    float: left;
    width: 10px;
    height: 30px;
    position: relative;
}
div.Post:after {
    bottom: 100%;
    left: 50%;
    border: solid transparent;
    content: " ";
    height: 0;
    width: 0;
    position: absolute;
    pointer-events: none;
    border-color: rgba(136, 183, 213, 0);
    border-bottom-color: #000;
    border-width: 6px;
    margin-left: -6px;
}
div.Fence {
    clear: both;
    padding-top: 8px;
}
*/

Stumbled upon your gist while preparing for interviews 😃

Here's a version I wrote in Python using dynamic programming for anyone curious:

def paint(post_count, color_count):
  p = [color_count, color_count * color_count]
  for x in xrange(len(p), post_count):
    p.append((p[x - 2] * (color_count - 1)) + (p[x - 1] * (color_count - 1)))

  return p[post_count - 1]

What is the purpose of count? Its not updated or used. It remains 0 through out the recursion tree