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).

Googly

1. There are set of coins of {50,25,10,5,1} paise in a box.Write a program to find the number of ways a 1 rupee can be created by grouping the paise.

2. Write a function that takes three integers corresponding to the lengths of sides and returns what kind of triangle can be made out of those 3 sides. (Equilateral, etc)

3. Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?

4. You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it?

Weigh the Balls :)

Given 3 red and 3 black balls. The 3 red balls weigh different, one heavy, one medium and other light. Similar is the case with black balls. The heavy, medium and light balls of both colors weigh the same. One heavy and one light ball weigh the same as two medium balls. Given a weighing balance, in 4 weighs, categorize each ball of both colors as heavy, medium and light.

Mighty "Arrays" of Questions -- Part I

1. Given an array containing both positive and negative integers, find the sub-array with the largest sum. Try in O(n).

2. Given an array of size N in which every number is between 1 and N-1 and appears only once except for one that appears twice. Find the duplicate number. (Multiple solutions exist).

3. Given an array of characters which form a sentence of words, reverse the order of words in O(n).

4. Write, efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9).

Apples and Oranges

There are 3 baskets. One of them has apples, one has oranges and the last has mixture of apples and oranges. The labels on their baskets always lie. (i.e. if the label says oranges, you are sure that it doesn't have oranges only,it could be a mixture). The task is to pick one basket and pick only one fruit from it and then correctly label all the three baskets.

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.

Coins problem

1. 8(Eight) Coins Problems :

Given 8 coins and a weighing balance (wherein weights of two objects can be compared by placing them in two different weighing pans). All coins except 1 weigh same. The exceptional coin weighs more than the others. Find that coin, in minimum number of weighs.

Given 8 coins and a weighing balance (wherein weights of two objects can be compared by placing them in two different weighing pans). All coins except 1 weigh same. The exceptional coin may weigh more or less than other coins. Find that coin and also whether it weighs more/less, in minimum number of weighs.

2. 12(Twelve) Coins Problem :

Given 12 coins and a weighing balance (wherein weights of two objects can be compared by placing them in two different weighing pans). All coins except 1 weigh same. The exceptional coin may weigh more or less than other coins. Find that coin and also whether it weighs more/less, in minimum number of weighs.

3. 'n' Coins Problem (Numeric Equation) :

Given 'n' number of coins and a weighing balance (wherein weights of two objects can be compared by placing them in two different weighing pans). All coins except 1 weigh same. The exceptional coin weighs more than the others. Find how many weighs, 'x', are required to find the exceptional coin. Device a numeric equation in 'n' and 'x'.

Given 'n' number of coins and a weighing balance (wherein weights of two objects can be compared by placing them in two different weighing pans). All coins except 1 weigh same. The exceptional coin may weigh more or less than the others. Find how many weighs, 'x', are required to find the exceptional coin and whether it weighs more/less. Device a numeric equation in  'n' and 'x'.