Doing Code Katas reminded me of some programmer’s puzzles (or exercises if you will) I once stumbled upon. I can’t remember where I first saw them, and Google isn’t much help. So, I decided to dig them out from ${HOME} and post them here for other peoples enjoyment.
- Given a pointer to the first node in a singly-linked list, determine in linear time whether the list terminates or has a cycle, without storing to memory.
- How can you construct a linked list that can be traversed forward and backward using only enough space for one pointer per node, but still allowing the nodes to have arbitrary addresses?
- Prove or disprove: Any Boolean expression with multiple occurences of at least one variable can be simplified.
- Can you always divide an integer by a power of two using the sign-extending “arithmetic right shift” instruction? Construct a sequence that works for all inputs on your machine. Would this have been easier to write back in the 60’s?
- If your processor doesn’t have a bit population count instruction that counts the 1 bits in a word, construct a fast sequence that does so without looping or loading from memory.
- Write code that counts the number of rightmost zero bits in a word, again without looping or loading or using a special bit scan instruction. Is it easier to count the number of leftmost zero bits?