Roy's musings

Puzzle statement: You are given the reference to the head of a singly linked list. Come up with an algorithm to find out if the linked list has a loop.  Credit:  I believe I read this problem in Sedgewick's Algorithms in C book first.

I love to come up with elegant and simple algorithms for hard problems. Recently one thought came to my mind: why don't I create a catalog of interesting puzzles that I come across. I am sure it will be useful to some people. At least to those who are preparing for an interview. So here is my first in the series. Disclaimer: I do not claim ownership of any of these puzzles that you will see in this series, unless explicitly noted. If I know the source, I give credit to the source. If I don't know the source and you do, please drop a comment pointing me to the original source of the puzzle. Here is the problem: You are given a binary search tree. For the sake of simplicity, assume that each node in the binary search tree holds an integer value and all the values are unique. Each node in the binary search tree has a reference to its right child and left child, but not to its parent. Given root, and two random nodes, find the first common parent of these two nodes. In case ...

My friend Siva asked me this puzzle. There is a set of N numbers. All numbers in this set repeat even number of times, except two numbers that repeat odd number of times. Develop an algorithm that will find these two numbers in O(N) space & time complexity. I couldn't find the solution, but the solution Siva gave and another variant of that solution that his friend gave were simply amazing. Not to spoil the fun, I am not giving any of those solutions here :-)

I was thinking about an interesting question regarding the Fibonacci series. Here it is. Assume that we draw the Fibonacci series of n as an inverted tree, where each node has its two additive terms as child nodes. For e.g. root node F(n) has F(n-1) and F(n-2) as children, and so on. Give an expression for the number of times node i occurs in the entire tree, where 1 Try to solve this problem. There is an interesting pattern to observe here.