Constructing Tree From Inorder and Preorder

ConstructTree(preorder, 0, preOrder.Length-1, inorder, 0, inorder.Length-1);

Node ConstructTree(int[] preorder, int ps, int pe, int[] inorder, int is, int ie)
{
  if(ps < pe || is < ie)
    return NULL;
  Node root = new Node();
  root->data = preorder[ps];
  int mid = is;
  while(inorder[mid] != preorder[ps]) 
    mid++;
  root->left = ConstructTree(preorder, ps+1, ps+mid-is, inorder, is, mid-1);
  root->right = ConstructTree(preorder, ps+mid-is+1, pe, inorder, mid+1, ie);
  return root;
}

Princess, Flowers and Snake With Incorrect Name Plates

There are three rooms, and there are Princess, Flowers and Snake in those rooms. The doors of all the rooms have incorrect nameplates. i.e., the nameplate for the princess' room is not Princess. Similarly, the nameplate for the Flowers' room is not Flowers. You need to find the room of the Princess without going to the room of Snake. How do you find?



Answer:

Go to the room which has the nameplate Snake. That will not have Snake. If the room has princess, you are done. If the room has flowers, then go to the room which has nameplate flowers. Princess would be there in that room. [Since, Princess cannot be there in the room which has nameplate Princess.]

One Person Always Lies, Another always Tells Truth

You have to go to a place and there are two paths. You don't know which path leads to your destination. There are two watchmen at the entrance. One person always tells truth, and another one always tells lies. You can ask only one question to one person. What question would you ask to find the way to your destination?



Answer:
If I ask the other person, the way to the destination, what would he tell?

Whatever he says, that is not the correct path. Take the other path.

Four People crossing the river with different speeds

There is a dark tunnel and four people wants to cross the tunnel. In the tunnel, only two people can travel at a time, and there is only one torch light. Without the torch light, they cannot travel through the tunnel. The four people can travel with different speeds. The first person takes 1 hour to travel through the tunnel. Second person takes 2 hours, third person takes 5 hours, and fourth person takes 10 hours. How can they travel in the least amount of time?



Solution:

1 & 2 cross the tunnel

1 returns

5 & 10 cross the tunnel

2 returns

1 & 2 cross the tunnel

Total Time: 17 hours

Three Cannibals and Three Humans Crossing River

There is a small river. On one side of the river, there are three cannibals, and on another side three humans are there. Boat is with the cannibals. If there are more no.of cannibals than the humans, then the cannibals will eat the humans. If the no.of cannibals is equal or less than the no.of humans, then they cannot do anything. How do the humans move to the other side of the river safely?













Answer:

3 Cannibals - 3 Humans

One Cannibal crosses the river

2 Cannibals - 3 Humans, 1 Cannibal

2 Humans cross the river

2 Cannibals, 2 Humans - 1 Human, 1 Cannibal

1 Human and 1 Cannibal cross the river.

1 Cannibal, 1 Human - 2 Humans, 2 Cannibals

2 Humans cross the river

1 Cannibal, 3 Humans - 2 Cannibals

1 Cannibal crosses the river

3 Humans - 3 Cannibals.

Find the Distance Travelled By the Prince

A Prince is going to a temple in a forest by his horse which travels at a speed of 60 km per hour. When he reached the entrance of the forest, he saw a girl who is going to the temple at a speed of 6 kms per hour. He visits the temple and returns to see the girl immediately. After he sees the girl, he goes again to the temple. He roams between the temple and girl, till the girl reaches the temple after one hour. How much distance the prince travelled by roaming between the girl and the temple?











Answer:

If we try to calculate how many no.of times, the prince has visited the temple or girl etc., the problem becomes complicated. The simple to way to solve the problem is, how long the prince has travelled, and from that calculate the distance. The prince has travelled as long as the girl was walking towards the temple. The girl took one hour to reach the temple. For that one hour, the prince was travelling. So, he travelled total 60 kms.

Finding the Poison Bottle

A king has arranged a celebration with many visitors to his kingdom. In the celebration, they arranged drinks in 1000 bottles. Just one hour before the celebration, he came to know that, one person has included a poison drink of the same color in a bottle of the same shape. If anyone drinks poison, then nothing happens to that person for one hour. After one hour, suddenly that person would die.

The king has few criminals who are going to be hanged the next day. With the help of them, he can find which bottle has poison. How many minimum no.of criminals he needs to find out the poisoned bottle in one hour.









Answer:
He needs 10 criminals.

Every bottle is given a no from 0 to 1000. Convert each number to binary. The binary number would contain 10 bits. For the first criminal, give little drink from all the bottles for which the first bit is 1. Similarly, for the second criminal, give drink from all the bottle for which the second bit is 1. Do the same thing for all the ten criminals.

After one hour, form a binary number with the criminals. If the first criminal dies, then make the first bit 1. If the second criminal does not die, then make the second bit 0. Do the same for all the criminals. Convert the binary number to the corresponding decimal number. That bottle has the poison.