King and Wine Bottles

Puzzle Problem: 

A king has a stock of 1000 bottles of delightful and very expensive wine. A neighboring queen plots to kill the bad king and sends a servant to poison the wine. Fortunately the king’s guards catch the servant after he has only poisoned one bottle. Now the kind needs to find the poisoned bottle as he cant discard all bottles as they are very expensive and imported. Furthermore, it takes one month to have an effect of the poison. The king decides he will get some of the prisoners in his vast dungeons to drink the wine. Being a clever king he knows he needs to murder no more than 10 prisoners – believing he can fob off such a low death rate – and will still be able to drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks time. Explain what is in mind of the king, how will he be able to do so ?

Hint : Think in terms of binary numbers.

Answer:

-
Bottles will be represented in terms of binary numbers :

BOTTLE
Decimal	Binary
5	101
23	10111
100	1100100
255	11111111
511	111111111
682	1010101010

 10 prisoners will be selected to find out the poisoned bottle
 Each prisoner will be assigned to corresponding to a bit in the Binary Represention.

For e.g. Bottle ,  numbered as 682 will be sipped by

	Decimal	Binary
Number	682	1	0	1	0	1	0	1	0	1	0
Prisoners		10	9	8	7	6	5	4	3	2	1

As we can see if the bottle number 682 was poisoned then the prisons 10, 8 , 6 , 4 , 2 would die.
-

Binary Tree to Doubly Linked List

Problem Statement: 
   Convert the given binary tree to Doubly Linked List(DLL)
        Given Binary Tree is :

Resultant Doubly Linked List (DLL) of the given binary Tree:

Solution:

Node Structure in Linked List

 class LinkNode {  
      LinkNode prev;  
      int data;  
      LinkNode next ;  
 }  

Node structure in a Binary Tree

 class BNode {  
      BNode left ;  
      int data;  
      BNode right;  
 }  

The above basic structure of Node in a Binary Tree and DLL seems to be quite similar, implying a possibility of converting Tree Structure  to DLL with few pointer manipulation.

From the above fig we see that the nodes in the DLL are in BFS traversal of the Tree, we already know that BFS traversal of Tree can be done with the help of Queue.

Concept: 
Connect all the nodes in the queue as they we pushed while BFS traversal with right pointer , and backward linking is done by maintaing parent and child pointers to use up left pointer of the node.


Refer to Full Source Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

/** * Binary Tree to DLL (using QUeue) * @param root */ public void changeToDLL(Node root){ if(root==null) return; Queue<Node> queue= new LinkedList<Node>(); queue.offer(root); //push 1st element Node parent =null; Node child =null; while(!queue.isEmpty()){ Node popedItem = queue.poll(); child = popedItem; if(child.left!=null) queue.offer(child.left) ; if(child.right!=null) queue.offer(child.right) ; child.right = queue.peek(); child.left = parent; parent = child; } printList(parent) ; } public void printList(Node last){ Node temp=last; while(temp!=null){ System.out.print(" <---" +temp.data); temp=temp.left; }

Please comment if you like the post or any suggestion.

Happy Coding !! :)

Petrol Pump Problem

Problem Statement:

       Budh International Circuit organised Formula 1 Racing in Noida.

While inspecting the circuit the management found that the fuel tanks that were setup had limited capacity of fuel and it also happened that if a car starts from some fuel tank it wont be able to reach the other fuel tank.

Now the management had the challenge of fixing point of start of race such the race completes at the same point.

Given Inputs:

1. Fuel capacity at each fuel pump.
2. Distance to the next fuel pump.
3. There exist a point from where if the race is started it would complete.

To Find: 
      Find out the petrol pump starting at which you can go around and come back to that particular petrol pump.

Solution :


Refer to full Source Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

/** * Get the Starting Point of the Circular Trip * @return index of the petrol pump if solution exist , * else -1 if solution doesnt exist */ public static int getStartIndex(int[] dist , int[] petrol){ int nPumps= petrol.length; int start , currentPetrol; int i=start=0; while(start < nPumps) { currentPetrol= petrol[i] - dist[i] ; while(currentPetrol >= 0) { i= (i+1) % nPumps ; currentPetrol += petrol [i] - dist[i] ; if(i==start) return start; } start = ++i ; i= i % nPumps ; } return -1; }

Please comment if you liked this post, also any comments or suggestion are most welcome.

Happy Coding !! :)

Next Pallindrome

Problem Statement: 
   Given a number , find the next Palindrome.

Solution:

Concept:  

1. Convert number to String.
2. Take base as 1, which will be used to get left and right pointers, in subsequent steps, 
3. Multiple Base by 10 at even iteration of loop till half the length of the string. 
4. Take right and left pointer pointing to left and right digits in the string.
5. Add the difference of left and right to the number
6. if right is greater left the number would become smaller, therefore increment the next digit to the left of right.
7. If the number is even and left and right pointer points to adjacent digits, increment right pointer

 Please refer to Source Code

 /**
  * Get next pallindrome
  * @param num
  * @return
  */
 public static int nextPanlindrome(int num) {

  if(isPalindrome(num)) //skip if number entered is pallindrome
   num++;

  String temp = num + "";
  int end=temp.length() -1;
  int base=1;

  for(int start = 0; start < end; start++, end--)
  {

   // Gives the right digit
   int right = Integer.parseInt(temp.charAt(end)+"") * base;

   // Gives the left digit
   int left = Integer.parseInt(temp.charAt(start)+"") * base;

   // add differnce to the number
   num = num + left - right  ;   //------(1)

   base *=10;

   if(right > left)
   {
    num += base;  // for incresing the value of number which got decreased at (1)

    // previous step indroduces asymmetry if its a even number.
    if(start == end - 1)  // For even numbers eg. case 8468 (adjacent digits)
     num += base/10;
   }
   temp = num + "";
  }

  return num;
 }


 public static boolean  isPalindrome(int num) {
  int reverse = 0, temp=num;

  while( temp != 0 ) {
   reverse = reverse * 10;
   reverse = reverse + temp%10;
   temp = temp/10;
  }
  return (num == reverse ? true: false);
 }

This is one of the many ways of getting the next Palindrome number w.r.t a given number.
Any comment or suggestion for any kind of code optimization or any other better approach is most welcome.

Happy Coding !! :)

Four glasses on a Square table

Puzzle Problem :  (Four glasses on a Square table)

Four glasses are placed on the corners of a square table. Some of the glasses are upright (up) and some upside-down (down). You have to arrange the glasses so that they are all up or all down (while keeping your eyes closed all the time). The glasses may be re-arranged in turns subject to the following rules.

1. Any two glasses may be inspected in one turn and after feeling their orientation you may reverse the orientation of either, neither or both glasses.
2. After each turn table is rotated through a random angle.
3. At any point of time if all four glasses are of the same orientation a ring will bell

You have to come up with a solution to ensure that all glasses have the same orientation (either up or down) in a finite number of turns. The algorithm must be non-stochastic i.e. it must not depend on luck.

Answer:

1. On the first turn choose a diagonally opposite pair of glasses and turn both glasses up.
2. On the second turn choose two adjacent glasses. At least one will be up as a result of the previous step. If the other is down, turn it up as well. If the bell does not ring then there are now three glasses up and one down(3U and 1D).
3. On the third turn choose a diagonally opposite pair of glasses. If one is down, turn it up and the bell will ring. If both are up, turn one down. There are now two glasses down, and they must be adjacent.
4. On the fourth turn choose two adjacent glasses and reverse both. If both were in the same orientation then the bell will ring. Otherwise there are now two glasses down and they must be diagonally opposite.
5. On the fifth turn choose a diagonally opposite pair of glasses and reverse both. The bell will ring for sure.

Hand Shake Problem

Puzzle Problem : (Hand Shake Problem)
Ten people (five couples) go to a party and start shaking hands.
You don't shake your spouse's hand or (of course) your own.
Give number of handshakes that happened at the party.

Answer:

 There are totally 40 handshakes....

First couple handshake with other is 8+8 = 16
Second couple handshake with other except first couple..becuase we already add their handshakes.
so i.e. 6+6 = 12
Third couple handshakes is 4+4 = 8 (minus the first two couples handshake)
Fourth couple handshakes is 2+2 = 4 (minus the first three couples handshake)
Last couple handshakes is 0+0 = 0 (minus the first four couples handshake)

so total 16+12+8+4 = 40

Ants on a Triangle

Puzzle Problem :

There are three ants on a triangle, one at each corner.
At a given moment in time, they all set off for a different corner at random.
What is the probability that they don’t collide ?

Answer:

Let the three ants are A, B, C.

There are two cases when they will not collide, 

the one is when they all move clockwise and the other is when they all move anticlockwise.

 

They will collide if any two ants move towards each other, at the same time the third ant can move in clockwise or in anticlockwise. so for each pair there are 2 such cases. 

And there are 3 pairs possible (A,B), (B,C) and (C,A).

So total 3*2 = 6 cases when they will collide.

So probability that they will not collide is 2/(2+6) i.e. 1/4

Total number of cases = 8

A->B, B->C, C->A
A->B, B->A, C->A
A->B, B->A, C->B
A->B, B->C, C->B
A->C, B->C, C->A
A->C, B->A, C->A
A->C, B->A, C->B
A->C, B->C, C->B

The non-colliding cases are :

A->B, B->C, C->A
A->C, B->A, C->B

4 Mugs Puzzle

Puzzle Problem:

     There are 4 mugs placed upturned on the table.

Each mug have the same number of marbles and a statement about the number of marbles in it. 

The statements are: 

Mug 1 : Two or Three

Mug 2: One or Four

Mug 3: Three or One

Mug 4: One or Two.

Only one of the statement is correct. How many marbles are there under each mug?

Answer:

As it is given that only one of the four statement is correct , the correct number can not appear in more than one statement. It it appears in more than one statement , then more than one statement will be correct.

Number	1	2	3	4
Mug	Mug 2 , Mug 3	Mug 1 , Mug 4	Mug 1 , Mug 3	Mug 2

Hence, there are 4 marbles under each mug.