Sep 282015
 

There are 10 prisoners are in 10 different cells of a prison. There is no way in which they can communicate with each other.

Each night, the warden picks one of the 10 prisoners and that prisoner is supposed to spend the entire night in the central living room. There is one bulb in the living room which can be switched on or off.

Warden puts a condition, “If any of the prisoner can tell with certainty, that all the other prisoners have spent night in the central living room, then he will free all of them. But, If the prisoner says that all the other have spent night in the living room, but that is not true, then all the prisoners will be killed”. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before the random picking begins, the prisoners are allowed to get together and make some strategy. But, once the strategy is made, then a prisoner cannot communicate with any other prisoner.

What plan should they agree on, so that eventually, someone will make a correct assertion?
Continue reading »

Sep 242015
 

Four glasses are placed on the four corners of a square rotating table. Each glass is either upright (up) or upside-down (down). You have to turn all the glasses in same direction (either all up or all down). There are following conditions

  1. You are blindfolded,
  2. At one time you can only change two glasses (and you cannot touch other two glasses).
  3. The table spins after each time you change the glasses.

When all the glasses comes in one direction, then a bell rings and the game stops?
Continue reading »

Sep 242015
 

You are standing before two closed doors. One of the doors leads to heaven and the other one leads to hell.

Two watchmen are standing, one in front of each door. You know one of them always tells the truth and the other always lies, but you don’t know which watchman tells the truth and who is the liar.

You can ask only one question to one of them, in order to find the way to heaven. What will you ask?
Continue reading »

Jul 012015
 

You have some work to be done by a worker in 7 days. The worker need to be paid every day after his work. The total cost of the work of 7 days is one gold bar (so every day the worker must be paid 1/7’th of the bar).

You have only one gold bar, and you can make only two cuts in that bar. How will you ensure that the worker is paid every day? Continue reading »

Jun 242015
 

One way to ask this question is:

Given a Binary tree that represent a family hierarchy. A parent can have at most two children (at most one girl child and at most one boy child). A girl child (if present) is always represented as left child in the binary tree, and a boy child (if present) is always represented as the right child. There will never be a situation that a parent has 2 girl children or 2 boy children or have more then 2 children. Find the total number of girls in the family.

Another way to ask the same question is to directly ask,

Write a function that returns total number of left node in a binary tree.

For example, Given the below binary tree, there are four girl children (B, D, H and F):

Binary_tree_ritambhara

The catch in twisting the question ( as girl-child in family) is to see if you can make sense from ambiguous problems. Also, sometimes, in our code, we skip the check for left child of the right child (which need to be counted).

Solution:

The solution is fairly simple. We traverse the entire tree, and if a node has left child then we increment the number of girl children by one, else not.

Algo:

1. If root is NULL, then return 0.
2. If root does not have Left child 
    - Return the number of left children in right-subtree.
3. Add the left children inside left and right subtree
   add 1 to it for the left-child of root 
   and return the total sum 

Code:

int countLeftChild(Node* r)
{
    if(r==NULL){ return 0; }
    
    if(r->lptr == NULL)
    {
        // NO Left child.
        return countLeftChild(r->rptr);
    }
    else
    {
        // Left child present.
        return countLeftChild(r->lptr) + countLeftChild(r->rptr) + 1;
    }
}

 

Jun 212015
 

There are 5 pirates, A, B, C, D and E. They have a strict hierarchy, A is senior to B, B is senior to C, C is senior to D and D is senior to E. So it is like (A > B > C > D > E).

These pirates have 1000 gold coins which they want to distribute among themselves. The rules of distribution is as follows:

- The most senior pirate should propose a distribution.
- All the pirates (including the most senior) will vote on whether they accept the distribution or not.
- If half or more pirates vote in the favour of distribution, then distribution is accepted and game ends.
- If more than half votes against the distribution, then the senior most pirate will be killed and the next senior most will propose a new distribution and this will continue.

When a pirate vote, they make their decision based on three factors (in this order):

  1. First of all, each pirate want to survive.
  2. Second, given survival, each pirate want to maximize the number of gold coins he gets.
  3. Third, given a situation of no-gain no-loss, each pirate would prefer to kill the other pirate.

Considering that all pirates are very strong in logic, and if a logic can be deduced, then they will deduce it. How should A distribute the coins so that he does not get killed and also gets the maximum coins possible. Continue reading »

Sep 032012
 

A certain town has 100 married couples (husband and wife only). Everyone in the town lives by the following rule:

  1. If a husband cheats on his wife, the husband is executed (killed) as soon as his wife get to know out about him (He may enjoy only as long as his wife does not get to know about it).
  2. All the women in the town only gossip about the husbands of other women but no woman ever tells another woman if her husband is cheating on her. ( So every woman in the town knows about all the cheating husbands in the town except her own).
  3. Husbands always remain silent.

One day an outsider came to the town and some how, got to know about all the cheating and non-cheating husbands.

The next day while leaving he announced to the entire town – “There is at least one cheating husband in the town”. 

What will happen ?
Continue reading »

Aug 312012
 

You have two identical eggs and access to a 100 floor building.

You don’t know how strong the eggs are. Eggs can be really strong (may not break if dropped from 100th floor) or fragile (break if dropped from first floor).

You want to find out the highest floor from where an egg can be dropped without breaking. In the process you may break both the eggs.

Question is, At least How many drops you need to find the highest floor?
Continue reading »