Wednesday, November 09, 2011

Puzzle: Finding if a linked list has a loop

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.

Puzzle: First common parent

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 one of them is the ancestor of the other, return the ancestor node as the common parent.
Please note that you can only perform downward traversal, as none of the nodes have a reference to its parent.