May 122016
 

You are blindfolded and 10 coins are place in front of you on table. 5 are having their heads-side up and 5 are having their tails-side facing upward.

You cannot tell which way they are by touching the coin.

You are allowed to touch the coins and flip them as many times as you want.

How do you make two piles of coins each with the same number of heads-up and tails-up?
Continue reading »

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 »

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 »

Dec 122012
 

An honest man holds a card which can be either ‘1‘, ‘2‘ or ‘3‘.

You can ask one (and only one) question to the man. The man is allowed to answer only ‘Yes‘, ‘No‘ and ‘I don’t know‘. The honest man obviously never lies.

What question will you ask so that you get to know about the card with 100% certainty?

Continue reading »