I like the matrix math one mentioned in the post, although I implemented the matrix arithmetic by hand.<p>That provides an opportunity to discuss the optimization involved in performing integer exponentiation, so you aren’t depriving an interviewer of an opportunity to have a productive conversation about programming.