Mass360 - X-duets

import java.util.HashSet;
import java.util.Set;

/*
 The X-duets of a string of characters are the ordered pairs of characters that  are X distance from each other. A string is X-particular if all its X-duets are different.  A string is Perfect String if it is X-particular for all possible X distances.  For e.g. take the string FLBL, its 0-duets are FL, LB and BL. Since all these are different,  FLBL is 0-particular. Similarly, its 1-duets are FB and LL, since they are different FLBL is  1-particular as well. Lastly, the only 2-duets of FLBL is FL, so FLBL is 2-particular. Hence, FLBL is a Perfect String.

Note that the fact that FL is both a 0-duet and 2-duet is insignificant as zero and two are different distances.

Now, take another string FFLL, its 0-duest are FF, FL and LL. Since all these are different,  FFLL is 0-particular. Its 1-duest are FL and FL, since they are same FFLL is not 1-particular.  Hence, FLBL is an imperfect String.

 Write a function called isImperfectString(String input) that returns a Boolean
 Where:
 The "input" is a non-empty strings of at most 100 capital letters, each string on a line by itself, followed by a
 line containing only two dollars ($$) signaling the end of the input.
 Output:
 For each input line, output whether or not it is a Perfect string a boolean value
 Sample Input Sample Output
 FLBL         0
 FFLL         1
 ORDINARY 0
 R                 0
 QYQRQYY 1

 */
/**
 * Solution Credit:- http://getinterviewinfo.blogspot.in/2014/07/maas360-ibm-company.html
 */
public class Duets {

    static int isImperfectString(String input) {
        Set set = new HashSet();
        for (int i = 1; i < input.length(); i++) {
            for (int j = 0; j + i < input.length(); j++) {
                String pair = ((char) input.charAt(j) + "" + (char) input.charAt(j + i));
                if (set.contains(pair)) {
                    return 1;
                } else {
                    set.add(pair);
                }
            }
            set.clear();
        }
        return 0;
    }

    public static void main(String[] args) {
        System.out.println(isImperfectString("FLBL"));
        System.out.println(isImperfectString("FFLL"));
        System.out.println(isImperfectString("ORDINARY"));
        System.out.println(isImperfectString("R"));
        System.out.println(isImperfectString("QYQRQYY"));
    }

}

Sort an array of 0s, 1s or 2-way Partitioning

/*
 * Sort an array of 0s, 1s
 * reference: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
 */
public class Partition2Way {
    int numArr[] = null;
   
    public Partition2Way(){
        numArr = null;
    }
   
    public Partition2Way(int n){
        numArr = new int[n];
    }
   
    public void sort2Way(int a[]){
        int low = 0;
        int mid = 0;
        int high = a.length-1;
        while(mid <= high){
            switch(a[mid]){
                case 0:
                    int t = a[low];
                    a[low] = a[mid];
                    a[mid] = t;
                    low++;
                    mid++;
                    break;
                case 1:
                    mid++;
                    break;
            }
        }
        this.numArr = a;
    }
   
    public void printArr(int a[]){
        System.out.print("Sorted List: ");
        for(int i=0; i<a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
   
    public static void main(String args[]){
        int a[] = {0,1,1,1,0,0,1,1,0,1};
        Partition2Way pw = new Partition2Way(a.length);
        pw.sort2Way(a);
        pw.printArr(pw.numArr);
    }
}

#output:

Sorted List: 0 0 0 0 1 1 1 1 1 1 

Convert a Binary Search Tree to a Doubly Link List

/*
 * Convert a Binary Search Tree to a Doubly Link List
 * Reference: http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/
 */
public class BST2DLL {
    TNode root = null;
 
    public BST2DLL(){
        root = null;
    }
 
    public BST2DLL(TNode t){
        root = t;
    }
 
    public TNode convertTree2DLL(TNode root){
        if(root == null)
            return root;
        if(root.left != null){
            TNode left = convertTree2DLL(root.left);
            for(;left.right != null; left = left.right);
            left.right = root;
            root.left = left;
        }
        if(root.right != null){
            TNode right = convertTree2DLL(root.right);
            for(;right.left != null; right=right.left);
            right.left = root;
            root.right = right;
        }
        return root;
    }
 
    public TNode BST2List(TNode root){
        if(root == null)
            return root;
        root = convertTree2DLL(root);
        while(root.left != null)
            root = root.left;
        return root;
    }
 
    public void printDLL(TNode root){
        System.out.print("\nList\t");
        for(;root!= null; root=root.right)
            System.out.print(root.data+" ");
        System.out.println();
    }
    public static void main(String args[]){
        //Create BST
        BinaryTree bt = new BinaryTree();
        bt.addNode(10);
        bt.addNode(8);
        bt.addNode(6);
        bt.addNode(9);
        bt.addNode(15);
        bt.addNode(12);
        bt.addNode(17);
        bt.inorder(bt.root);
     
        BST2DLL bd = new BST2DLL();
        TNode root = bd.BST2List(bt.root);
        bd.printDLL(root);
    }
}

#output

6 8 9 10 12 15 17 

List 6 8 9 10 12 15 17 

Dynamic Programming Question: maximize profit for wine sale

/**
 * you have a collection of N wines placed next to each other on a shelf. For
 * simplicity, let's number the wines from left to right as they are standing on
 * the shelf with integers from 1 to N, respectively. The price of the i-th wine
 * is pi (prices of different wines can be different).
 * Because the wines get better every year, supposing today is the year 1, on
 * year y the price of the i-th wine will be y*pi, i.e. y-times more than the
 * current year.
 * what is the maximum profit you can get, if you sell the wines in optimal order.
 * So for example, if the prices of the wines are (in the order as they are
 * placed on the shelf, from left to right): p1=1, p2=4, p3=2, p4=3.
 *
 */
public class DP1 {
    int p[] = null;
    int cache[][];
   
    public DP1(){
        p = new int[100];
        cache = new int[100][100];
        for(int i=0; i<100; i++)
            for(int j=0; j<100; j++)
                cache[i][j] = -1;
    }
   
    public DP1(int N){
        p = new int[N];
        cache = new int[N][N];
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                cache[i][j] = -1;
    }
   
    /**
     * Description: Backtracking function to find maximum profit.
     * @param year : starts from 1 to N-1
     * @param be : beginning of price array
     * @param en : end of price array
     * @return : maximized profit
     */
    public int maxProfit(int year, int be, int en){
        if(be>en)
            return 0;
        return Math.max((this.maxProfit(year+1, be+1, en)+year*this.p[be]),(this.maxProfit(year+1, be, en-1) + year*p[en]));
    }
   
    /*
     * Dynamic Programming Approach
     */
    public int maxDPProfit(int be, int en){
        if(be > en)
            return 0;
       
        if(cache[be][en] != -1)
            return cache[be][en];
       
        int year = this.p.length - (en-be+1) + 1;
        cache[be][en] = Math.max((this.maxDPProfit(be+1, en) + year*p[be]),(this.maxDPProfit(be, en-1)+year*p[en]));
        return cache[be][en];
    }
   
    public static void main(String args[]){
        DP1 dp = new DP1();
        int p[] = new int[]{1,4,2,3};
        dp.p = p;
        int profit = dp.maxProfit(1, 0, 3);
        System.out.println("Profit: " + profit);
        //DP
        int dpprofit = dp.maxDPProfit(0, 3);
        System.out.println("DP Profit: " + dpprofit);
    }
}

#output:

Profit: 29

DP Profit: 29

Given an array of integers(+ve,-ve,0 or duplicates). Find n print all triplets such that a+b+c=0

/**
   * Given an array of integers(+ve,-ve,0 or duplicates). Find n print all triplets such that a+b+c=0.
   * e.g. Let A = -1 0 9 5 -5 2 3
   * Answer = {0 5 -5} {-5 2 3}.
   * Expected : Time O(n2) Space O(1)
 */
public class Prob3Sum {

    public void find3Sum(int A[]){
        for(int i=0; i<A.length; i++){
            int l = i+1;
            int r = A.length - 1;
            while(l<r){
                if(A[i] + A[l] + A[r] == 0){
                    System.out.println("Sum: " + A[i] + " " + A[l] + " " + A[r]);
                }
                if(A[i] + A[l] + A[r] > 0)
                    r--;
                else
                    l++;
            }
        }
    }
   
    public static void main(String args[]){
        QuickSort sort = new QuickSort();
        sort.A = new int[]{-1, 0, 9, 5, -5, 2, 3};
        sort.quickSort(sort.A, 0, sort.A.length-1);
        sort.printArr();
       
        Prob3Sum ps = new Prob3Sum();
        ps.find3Sum(sort.A);
       
    }
}

#output

Sorted: -5, -1, 0, 2, 3, 5, 9, 

Sum: -5 0 5

Sum: -5 2 3

Level Order Traversal for Binary Tree

    public void levelTraversal(TNode root) {
        TNodeQueue queue = new TNodeQueue();
        if(root != null){
            queue.push(root);
            while(!queue.isEmpty()){
                //System.out.println("Queue: " + queue.isEmpty());
                TNode tmp = queue.pop();
                System.out.print(tmp.data + " ");
                if(tmp.left != null)
                    queue.push(tmp.left);
                if(tmp.right != null)
                    queue.push(tmp.right);
            }
        }
    }

# output

Inorder:

2 4 6 8 9 10 

Level Order Traversal: 

8 4 9 2 6 10 

Stack with TNode (Tree Node)

public class NodeStack {

    TNode stack[] = null;
    int top = 0;

    //int ssize = 0;
    NodeStack(int n) {
        stack = new TNode[n];
    }

    NodeStack() {
        stack = new TNode[100];
    }

    public boolean isEmpty() {
        if (top < 0) {
            return true;
        } else {
            return false;
        }
    }

    public void printPop() {
        System.out.println("Poppoed " + this.pop().data);
    }

    public void push(TNode p) {
        if (top < stack.length) {
            stack[top++] = p;
        }
        //System.out.println("Top: " + top);
    }

    public TNode top(){
        if(top>0)
            return stack[top-1];
        return null;
    }
    public TNode pop() {
        TNode p = null;
        if (top > 0) {
            p = stack[--top];
        }
        //System.out.println("Top: " + top);
        return p;
    }

    public void printStack() {
        System.out.print("Stack [LIFO order]: ");
        for (int i = this.top - 1; i >= 0; i--) {
            System.out.print(stack[i].data + " ");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        NodeStack s = new NodeStack();
        s.push(new TNode(10));
        s.push(new TNode(15));
        s.push(new TNode(20));
        s.push(new TNode(25));
        s.printStack();
        s.printPop();
        s.printPop();
        s.push(new TNode(19));
        s.push(new TNode(24));
        s.printStack();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printStack();
    }
}

# output:

Stack [LIFO order]: 25 20 15 10 

Poppoed 25

Poppoed 20

Stack [LIFO order]: 24 19 15 10 

Poppoed 24

Poppoed 19

Poppoed 15

Poppoed 10

Stack [LIFO order]: