Analytical Puzzles

1. Given a binary tree. Give an algorithm to find the first common ancestor of any two nodes in the tree.

2. Write a method to combine two two sorted linked list into one in sorted form with out using  temporary Node.

3. There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].
Solve it without division operator and in O(n) and constant space.

4. Given two sorted arrays. Find the 'k'th largest in the array formed by merging these two arrays. Find in O(log k).

Problems on Linked lists

1. Midpoint of a linked list

Given pointer to the head of a linked list, find the middle element in single traversal (single loop).

2. Cycle in a linked list

Given pointer to the head of a linked list, find whether there is a cycle in the list in O(n). For e.g. if in a list the last element->next pointer points to one of the elements in between, there there is no end to the list and a cycle exist.

3. Point of intersection of 2 linked lists

Given pointers to the heads of two linked lists. They intersect at some element, and proceed as a single list there-onwards. Find the point of intersection in O(n). For visualization purpose, consider the linked lists forming a shape 'Y'.

4. 'n'th element from the end in a linked list

Given pointer to the head of a linked list, find the 'n'th element from the end in the list in single traversal.