Demystify

This page has the solutions to all interview questions posted in the blog.The questions are demystified here. The fact is that all these questions have very simple and elegant solutions. All that is required is the spark.

Links for questions:

Part 1
Part 2
Part 3

Part 1 Solutions:

Question 1:

For each number, calculate the number of times it will be changed, which is nothing but the number of factors for a number. The concept is that, every square number has odd number of factors, every other number has even number of factors. So, 10 cups will be open, which are the ten square numbers, 1, 4, 9, …. 100.

Question 2:

There are 64 squares. Suppose we start from a black square, as mentioned. Consider it as “Position 1″. The next move will be to a white square ( that is how a horse moves ), which we shall consider as “Position 2″. The third move will be to a black one ( Position 3 ). The pattern emerges will be such that all black squares will be in odd positions and the white squares in even positions. The diagonally opposite corner is a black square, and that has to be position 64 if it must be the destination. But black squares are always in odd positions, So, it is impossible to reach the diagonal corner after moving through all the squares once.

Part 2 Solutions:

Question 1:

The prisoners decide that the shortest prisoner will find out the no. of black hats by looking at the prisoners in front of him (n-1). Now if the no. of black caps is even, he says “black” otherwise he says “white”. Consequently, the prisoner in the front will hear him. Now assume there were an odd no. of black hats with respect to the shortest prisoner. Then the prisoner in front of the shortest prisoner hears “white”. Now if he is wearing a black hat, he’ll see an even no. of black hats but according to the shortest one there should be odd no. of blacks. So this prisoner answers “black”. Everyone else now knows that there are even no. of black caps among the n-2 prisoners and so the process continues, at the end of which n-1 prisoners are surely saved. The only prisoner who doesn’t get saved is the shortest prisoner whose life is dependent on what we call luck and mathematicians call “PROBABILITY”

Now lets bring some complexity into this.

What if there were a crazy warden who happens to use hats of m different colours for this activity? How does the prisoners’ algo change and how many will be saved? (Assume m < n)

Hint: More the uncertainity, more the no. of unsure survivors

Question 2:

Assume you are one of the prisoners. You might guess the colour of your hat to be black. Now, the second prisoner will be seeing one black and one white hat. Lets assume that the second prisoner guesses the colour of his own hat to be black. Now since he sees one black hat and guesses his own to be black, he would expect the third person to answer “white”. But the third person does not answer. So the second person would easily conclude that his hat is white. But even he does not answer for some time. Thus you conclude that your hat is white.

Part 3 Solutions:

Question 1:

Consider the 300 digit number to be N. The sum of all digits of the number N is 100×1 + 100×2 = 300.
300 is divisible by 3, but it is not divisible by 9. This means that N  is divisible by 3 but it is not divisible by 9.
So, N can be written as 3xm. For a number to be a perfect square, all its prime factors must be in even number, which is defied in the case of 3. So, N cannot be a square number.

Question 2:

Answer is very simple. Take any 16 coins from the table, flip them and place them on the other. It works!!!

Question 3:

(For a clock, [a/b] means a parts of the sand is on top, b parts on bottom)

The most optimal solution is this:

Start both clocks simultaneously.

Time 0:   [7/0]    [11/0]

Time 7:   [0/7]    [4/7]    now flip clock 1

Time 7:   [7/0]    [4/7]

Time 11:  [3/4]    [0/11]   now flip clock 1

Time 11:  [4/3]

Time 15:  [0/7]