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 !! :)

DP: Longest Common Sub-Sequence

Problem Statement:
    Find the LCS or Longest Common Sub-sequence (not necessarily contiguous) of the two given Sequences.

Seq 1: P R A T E E K
Seq 2: R A T H O R E

LCS is : R A T E

  Solution :

LCS applications:
1. Molecular Biology : 
          To compare DNA sequences

2. File Comparison: 
3. Screen Redisplay:
           As in Mobile display only the changed pixel are updated, instead of updating the whole screen.
 This is problem is combinatorial in nature and therefore can be solved by Brute force,
Possible Subset of the given sequences of length m and n will be 2^m and 2^n respectively, which will be matched by one with each other. Thus , the Complexity of the algorithm will be exponential.

Now,
    Question is "Can we do Better" as Professor Tim Roughgarden says.


 We can see this problem fulfilling the properties of Dynamic Programming.

 Principle behind Dynamic Programming says , start with recursive algorithm , which may be inefficient because of repeated computation of sub-problems. Simply remember the solution of sub-problems, which reduce the recomputing and will be simply looked up when required.
Thus computation time reduces to proportional to the number of sub-problems.

Dynamic Programming Properties:
1. Optimal sub-structure :
           We can decompose our problem in to smaller sub-sequence and calculate solution for them.

Fig: Optimal Sub-Structure

2. Overlapping Sub-Problem:
          Our Problem involves kind of recursion.



Given

Seq 1: P R A T E E K
Seq 2: R A T H O R E

Fig: LCS for given strings

Here ,all those characters are picked which come from diagonal cell, i.e. which are marked in orange, cell in green indicates the Longest Common Sub-sequence


Full Source Code: LINK
  

 /**
  * Longest Common Sequnece Subroutine
  */
 public static int lcs(String s1, String s2){

  char[] X = s1.toCharArray();
  char[] Y = s2.toCharArray();
  int[][] LCS = new int[Y.length +1 ][X.length +1 ];

  for(int i=1;i<=Y.length;i++)
  {
   for(int j=1;j<=X.length;j++)
   {
    if(Y[i -1 ]== X[j-1])
     LCS[i][j] = 1 + LCS[i-1][j-1];
    else
     LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
   }
  }

  // Start Trace Back
  StringBuilder sb= new StringBuilder();
  int i=Y.length ;
  int j=X.length ;

  while(i > 0 && j>0)
  {
   //System.out.println(i + " " + j);
   if(Y[i-1] == X[j-1])
   {
    sb = sb.append(X[j-1]);
    i--;
    j--;
   }
   else
   {
    if(LCS[i][j-1]> LCS[i-1][j])  
     j--;
    else
     i--;
   }
  }

  System.out.println(sb.reverse());
  return LCS[Y.length][X.length];
 }

References:1. http://www.ics.uci.edu/~eppstein/161/960229.html
                    2. Refer NPTEL videos of design and algoritms (IIT Mumbai)
                    3. http://www.youtube.com/watch?v=wJ-rP9hJXO0


Please comment  and post suggestions

Happy Coding!! :)

Continuous Subsequence divisible by a number

Problem Statement: 
      What is the number of sub-sequences divisible by the given divisor  ?  

Given sequence:

                        {1 , 1 , 3 , 2 , 4, 1 ,4 , 5}
Divisor is 5

Answer is 11

Reference : Problem number 3 of
http://www.mii.lt/olympiads_in_informatics/pdf/INFOL062.pdf

Solution: 

Our goal is find the number of continuous sub-sequences divisible by the divisor
We will group the pre-fixes of the given sequence by the remainders (here modulo 5) of the sums of their elements.
If there are 'k'  prefixes for some remainder, then number of continuous sub sequences, with the sums of elements divisible by divisor (here 5) will be given by

ⁿC₂    = k(k-1)/2

 

 

Full Source Code: LINK

Implementation:

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

/** * Sub-Routine to count numnber of sub-sequnces * @param d: the given divisor */ public static int solve(int[] arr, int d) { Object o; int Answer = 0; int[] hash = new int[d]; int sum = 0; int val; int num; for (int i = 0; i < arr.length; i++) { num = arr[i]; if(num % d == 0) // count numbers which are divisible by divisor Answer ++ ; sum += num; val = sum % d; if(val<0) //handle negative numbers val = val * (-1); hash[val] = hash[val] + 1; } int size=hash.length ; for (int i = 0; i < size; i++) { int count = hash[i]; if(count > 1) Answer = Answer + count * (count -1)/2 ; } System.out.println(Answer+hash[0]); return Answer+hash[0]; }

Users are requested to refer the reference.
If u liked my article please comment and like the page on facebook.
Happy Coding!! :)