Squares on a Chess Board

Puzzle :
      How many squares are there on a Chess board. ?

64 as answer is wrong !!

Answer:

The Answer is ofcourse not 64. Since Chess boards of size 1x1 , 2x2 , 3x3 ..... 7x7 , 8x8 can be made.
For 1x1
8*8 = 64
For 2x2
7 horizontal and 7 vertical positions are available to place 2x2 chess board.
So we have 7*7= 49 , 2x2 Chess boards
For 3x3
6 horizontal and 6 vertical positions are available to place 2x2 chess board.
So we have 6*6= 36 , 3x3 Chess boards
and so on
1×1 8 x 8 = 64 squares
2×2 7 x 7 = 49 squares
3×3 6 x 6 = 36 squares
4×4 5 x 5 = 25 squares
5×5 4 x 4 = 16 squares
6×6 3 x 3 = 9 squares
7×7 2 x 2 = 4 squares
8×8 1×1 = 1 square
Therefore , total squares are 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 + 8^2 = 204 squares

Probablity of Picking socks

Puzzle: 
     Probability of Picking socks of same color.

There are 5 pairs of Black Socks and 5 pairs of White Socks. What is the probability to pick a pair of black or white socks when 2 socks are selected in random.

Answer:

Number of Ways to pick 2 socks from 20 socks = 20C2 = (20*19)/2 = 190
Number of Ways to pick 2 Black socks from 10 socks = 10C2 = (10*9)/2 = 45
Probablity of picking 2 Black socks = 45/190
Similarly ,
Probablity of picking 2 White socks = 45/190
Probablity of picking 2 socks of same color = 45/190 + 45/190
= 9/19

Remove Leaf Nodes

Problem Statement:
        Remove the leaf nodes of the given binary tree.

                                                                   

Fig1: Given Binary Tree

Tree with leaves removed:

Solution:

Full Source Code: LINK

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

/** *Remove Leave Nodes */ public Node pruneLeaves(Node root){ if(root.left== null && root.right==null) return null; else { if(root.left!=null) root.left = pruneLeaves(root.left); if(root.right!=null) root.right = pruneLeaves(root.right); } return root; }

Please Comment and post suggestions.
Happy Coding!! :)

Gold Bar

Puzzle: 
    You have hired a worker to dig Diamond mine for 7 days, and you promise the worker to give Gold Bar of 7 inches as reward , 1 inch per day. What is minimum number of cuts required to give the worker 1 inch of gold bar every day ?

Given 7inch Gold bar:

Fig: 7 inches Gold bar

  7 Inch Gold bar broken in 1 inch , 2 inches and 4 inches

Fig2 : 1inch , 2 inches and 4 inches

Answer:

Day 1: Give 1 inch (+1)
Day 2: Get back 1 inch, give 2 inches(-1, +2)
Day 3: Give 1 inch (2,+1 )
Day 4: Get back 1 inch and 2 inches, give 4 inches (-2,-1,+4)
Day 5: Give inch (4,+1)
Day 6: Get back 1 inch, give 2 inches (-1,4,+2)
Day 7:Give A (4,2,+1)

Longest Zig-Zag Path

Problem Statement:
        Calculate the longest Zig-Zag Path in a Binary Tree.

Fig: Find longest Zig-Zag Path

Longest Zig-Zag path here is : 2 , 4, 8, 9 ,
hence the length is 4
Solution:

Full Source  Code: LINK

The longest zig-zag path may not include the root of the tree, the path can either start from Right child or Left child.
Possible combinations are :
1. LRLRLR ......
2. RLRLRL.......


Main Logic implementation is given below:

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

/** * Calculates Longest Zig-Zag Path in Binary Tree * @return max value of longest path */ public int longestZigZag(Node root,int max){ if(root==null) return 0; int lh=countUtil(root,true,0); int rh=countUtil(root,false,0); max= Math.max(lh, rh); max= Math.max(max,longestZigZag(root.left, max)); max= Math.max(max,longestZigZag(root.right,max)); return max; } /** * Count Utility to count the steps covered, for a given node * @param node * @param moveLeft : if true , move left , else move right * @param count: current count * @return the count of ZIG-ZAG path traversed */ public int countUtil(Node node, boolean moveLeft , int count){ if(node==null) return count; if(moveLeft) count=countUtil(node.left,!moveLeft,count+1); else count=countUtil(node.right,!moveLeft,count+1); return count; }

Please post your comments and suggestions.
Happy Coding!! :)

Intersection and Union of Arrays

Problem Statement: 
         Find the Intersection and Union of Arrays

Solution:
 Below we will find solution of problem in O(n) and assuming the arrays are already sorted.

Full Source Code : LINK

Intersection Logic: 
1. If 1st array element is smaller , increment its index
2. If 2nd array element is smaller , increment its index.
3. If equal, print either , and increment both.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

/** * Intersection of Arrays */ public void intersection() { int i=0; int j=0; while(i < arr1.length && j < arr2.length) { if(arr1[i] < arr2[j]) i++; else if(arr1[i] > arr2[j]) j++; else { System.out.print(arr1[i++] + "\t"); j++; } } }

Union Logic:
1. If element of 1st array is smaller print it, and increment index. 
2. If element of 2st array is smaller print it, and increment index.
3. If both are equal , print arr1 element and increment both indexes of both arrays
4. Print remaining array of the larger array.

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

/** * Union Of arrays */ public void union() { int i=0,j=0; while(i < arr1.length && j < arr2.length) { if(arr1[i] < arr2[j]) System.out.print(arr1[i++]); else if(arr1[i] > arr2[j]) System.out.print(arr2[j++]); else { System.out.print(arr1[i++]); j++; } System.out.print("\t"); } if(arr2.length > arr1.length) for(;j<arr2.length;System.out.println(arr2[j]),j++); else if(arr2.length < arr1.length) for( ; i<arr1.length;System.out.println(arr1[i]),i++); }

Please comment and post your suggestions.
Happy Coding!! :) 

All Root to Leaf paths

Problem Statement:
          Print out all Root to Leaf paths in the given Binary Tree

Fig: Given Binary Tree

Output:

1-->    2-->    4-->    8-->    9-->    
1-->    2-->    5-->    
1-->    3-->    6-->    
1-->    3-->    7-->    

Solution:
Full Source Code: LINK

Implementation Logic below :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

/** * Subroutine to print all paths from root to leaves * @param list: holds the nodes encountered, values are overriden based on the value of index * @param index */ private void printRoot2LeafPaths(Node root,Node[] list, int index) { if(root==null) return ; list[index++]=root; if(root.left==null && root.right==null) { for(int i=0;i<index;i++) System.out.print(list[i]+"-->\t"); System.out.println(); } printRoot2LeafPaths(root.left,list,index); printRoot2LeafPaths(root.right,list,index); return; }

Please comment and post your suggestions if any.
Happy Coding !! :)

Trees: Median At Given Level in a Binary Tree

Problem Statement: 
        Find the Median at a given level (say level 3) in a binary Tree.

Fig: Given Binary Tree

Output: For level 3

 Available Nodes @ given Level : [4, 5, 6, 7]  
 Median : 6  

Solution:

Full Source Code: LINK

Code snippet for the logic involved.

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

/** * Subroutine to calculate median * @param level : Given level * @return : median */ public Node medianAtLevelK(Node root, int level){ List<Node> list = itemsAtLevelK(root,level,new ArrayList<Node>()); Node median = list.get(list.size()/2); System.out.println("Available Nodes @ given Level : " + list); System.out.println("Median : " +median); return median; } /** * Fills the list with items at given level * @return list filled with nodes at the prescibed level */ public List<Node> itemsAtLevelK(Node root,int level, List<Node> list){ if(root == null) return list; if(level == 1) list.add(root); list=itemsAtLevelK(root.left, level-1,list); list=itemsAtLevelK(root.right, level-1,list); return list; }

Please post your suggestions and comments.
Happy Coding!!:)

LinkedList : Y Intersection

Problem Statement: 
         Detect the Y- Intersection of the two given Linked List

Fig: Intersecting Linked Lists

Solution:

Full Source Code : LINK

The steps Involved in the above problem are:
1. Calculate lengths of the linked list
2. Advancement in the linked list which is larger in length(i.e. advance by the offset difference of the two lengths).
3. Traverse

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 42 43 44 45 46 47 48 49 50 51 52 53 54 55

/** * Detect Intersection of linked Lists * @return null if no intersection , else return the intersecting node */ public static Node detectIntersection(Node head1, Node head2){ int len1=0, len2=0,offset =0; Node temp1,temp; //Step1 //==== length calculation starts temp = head1; while(temp!=null){ temp=temp.next; len1++; } temp=head2; while(temp!=null){ temp=temp.next; len2++; } //==== length calculation ends //Step 2 //==== Pointer advancement on the basis of offset starts offset = len1 > len2 ? (len1 - len2) : (len2 - len1) ; if(len1>len2){ temp = head1; temp1= head2; } else { temp = head2; temp1 = head1; } while(offset > 0){ temp=temp.next; offset--; } //==== Pointer advancement on the basis of offset ends //Step 3 // Final Step of Running the pointers while(temp!=null && temp1!=null){ if(temp1 == temp) return temp; temp=temp.next; temp1=temp1.next; } return null; }

Please point out if any mistakes or suggestions in the code.
Happy Coding :!!1

Shuffle Deck of Cards

Problem Statement: 
   Shuffle Deck of Cards

Solution:
   
Knuth Shuffle :
   In Iteration i, pick Integer 'rand' between 0 and i uniformly at random, swap arr[i] and arr[rand]

Knuth Shuffling algorithm produces a uniformly random permutation of the input array in linear time.
Key Note: Shuffling element should be between 0 to i  or between i to N-1 for uniformly random result.

Source Code : LINK

1 2 3 4 5 6 7 8 9 10 11 12 13

/** * Shuffle subroutine */ public void shuffle(){ Random randomGenerator = new Random(); for(int i=0;i<arr.length;i++){ int rand =randomGenerator.nextInt(i+1); swap(i,rand); } System.out.print("After Shuffling: "); print(); }

Please comment and post your suggestions.
Happy Coding !! :)