I like the matrix math one mentioned in the post, although I implemented the matrix arithmetic by hand. That provides an opportunity to discuss the optimizatio

I like the matrix math one mentioned in the post, although I implemented the matrix arithmetic by hand. 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.