Monday 1 October 2012

Probability puzzle

Puzzle: Given 50 white marbles, 50 black marbles, and 2 boxes, put the marbles into the boxes to maximize the chances of selecting a black marble.

Sol: probability to select a box would be 1/2, so if we put 50 marbles in a box and other 50 in other box then probability to select black marble will be:
0.5*1 + 0.5*0 = 50%
Instead we can improve it by putting 1 black marble in a box and other 49 B+50 W marbles in other box.
Now probability for selecting a black marble will improve:
0.5*1 + 0.5*(49/99)= 74.5 %
and that is a significant improvement from previous 50%.

Please comment if it could be more improved.

Diameter and maximum distance between two nodes in a Binary tree.

/*
  Function to find out maximum distance between two nodes in a binary tree.
  Ds for tree could be found here: Ds for Tree
*/

public int height(Node root){
        if(root==null)
            return 0;
        else
            return (1+max(height(root.getLeft()),height(root.getRight())));
    }
   
    public int max(int a, int b){
        return a>b?a:b;
    }
   
    public int diameter(Node root){
        if(root==null)
            return 0;
        else{
            int lh=height(root.getLeft());
            int rh=height(root.getRight());
           
            int ld=diameter(root.getLeft());
            int rd=diameter(root.getRight());
           
            return( max(1+lh+rh,max(ld,rd)));  //add 1 to the result if counting current node as well.
        }          
    }   

Iterative inorder tree traversal-Morris traversal

/*
   Morris traversal in Java:
   Inorder tree traversal without recursion.
   Helper class for Tree data-structure could be found here: DS for Tree
  
*/


/**
 * MorrisTraversal.java
 *
 */

/**
 * @author vikky.agrawal
 *
 */
public class MorrisTraversal {

    private TreeNode root;

    MorrisTraversal() {
        root = new TreeNode(49);
    }

    public static void main(String args[]) {
        new MorrisTraversal().traverse();
    }

    public void traverse() {
        System.out.println("Building tree with root value " + root.getData());
        for (int i = 0; i < 7; i++)
            this.insert(root, (int) (Math.random() * 100));
        this.morrisTraverse(root);

    }

    /**
     * Iterative inorder traversal using Morris traverse
     *
     * @param root
     */
    public void morrisTraverse(TreeNode root) {

        while (root != null) {
            if (root.getLeft() == null) {
                System.out.println(root.getData());
                root = root.getRight();
            } else {
                TreeNode ptr = root.getLeft();

                while (ptr.getRight() != null && ptr.getRight() != root)
                    ptr = ptr.getRight();

                if (ptr.getRight() == null) {
                    ptr.setRight(root);
                    root = root.getLeft();
                }

                else {
                    ptr.setRight(null);
                    System.out.println(root.getData());
                    root = root.getRight();
                }
            }
        }
    }

    // Insertion as BST
    public void insert(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
            return;
        } else {
            if (val < root.getData()) {
                if (root.getLeft() == null) {
                    System.out.println("inserting left to :" + root.getData()
                            + " val : " + val);
                    root.setLeft(new TreeNode(val));
                } else {
                    insert(root.getLeft(), val);
                }
            } else {
                if (root.getRight() == null) {
                    System.out.println("inserting right to :" + root.getData()
                            + " val : " + val);
                    root.setRight(new TreeNode(val));
                } else {
                    insert(root.getRight(), val);
                }
            }
        }
    }

    // DS for tree
    private static class TreeNode {

        private int data;
        private TreeNode right;
        private TreeNode left;

        TreeNode() {
        }

        TreeNode(int data) {
            this.setData(data);
            this.setLeft(null);
            this.setRight(null);
        }

        public int getData() {
            return this.data;
        }

        public TreeNode getRight() {
            return this.right;
        }

        public TreeNode getLeft() {
            return this.left;
        }

        public void setData(int data) {
            this.data = data;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }
    }

}