Archive for July, 2011


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package XXXX;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.StringTokenizer;

/**
 *
 * @author poochedi
 */
public class LongestIncreasingSubsequence {
    
    public static void main(String[] args) throws IOException {
        
        InputStreamReader iReader = new InputStreamReader(System.in);
        BufferedReader bReader = new BufferedReader(iReader);
        ArrayList seqList = new ArrayList();
        ArrayList lngIncSeq = new ArrayList();
        System.out.println("Enter a sequence of numbers seperated by space Hit enter to terminate");
        String seqString = bReader.readLine();
        if(seqString != null) {
            
            StringTokenizer tokenizer = new StringTokenizer(seqString);
            while(tokenizer.hasMoreTokens()) {
                
                seqList.add(tokenizer.nextToken());
            }
            System.out.println("seqList " + seqList.toString());
        }
        else 
            System.out.println("No sequence");
        
        //Now that I have the list I can find the increasing subseq
        Iterator seqItr = seqList.iterator();
        //add the 1st to the result list
        int first = Integer.parseInt((String)seqItr.next());
        lngIncSeq.add(first);
        System.out.println("lngIncSeq - 1st elem " + lngIncSeq.toString());
        while(seqItr.hasNext()) { //every element is looked O(n)
            
            int next = Integer.parseInt((String) seqItr.next()); //access is O(1)
            if(lngIncSeq.size() < 2) {
                System.out.println("next " + next + " first " + first );
                if (next < first) {
                    
                    //the new number is lesser than the already existing in the list
                    lngIncSeq.remove(0);
                    lngIncSeq.add(next);
                    first = next;
                    //lngIncSeq.set(0, next);
                    System.out.println("lngIncSeq if next < first " + lngIncSeq.toString() );
                }
                else if(next > first) {
                    
                    //append the new number to the already existing list
                    lngIncSeq.add(next);
                }
            }
            else {
                //now that the result list is more than 2 in length see how the next num is w.r.to prev two numbers in the list
                int prev = (int) (lngIncSeq.get(lngIncSeq.size()-2)); //O(1)
                int pres = (int) (lngIncSeq.get(lngIncSeq.size()-1)); //O(1)
                
                if(next > pres && next > prev) {
                    //add next to end of the list
                    lngIncSeq.add(next); //O(n) added to end of the list
                }
                else if( next > prev && next < pres) {
                    int index = lngIncSeq.indexOf(pres);
                    lngIncSeq.remove(index);    //O(n) removal from end of list
                    lngIncSeq.add(next);        //O(n) addition to end of list
                }
                //if next is less than both pres and prev, ignore it => no change to the existing result list
            }
        }
        
        System.out.println("lngIncSeq " + lngIncSeq.toString());
    }
}
Advertisements
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package XXXX;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

/**
 *
 * @author poochedi
 */
public class CommonSubSequence {

    static HashMap table = new HashMap();

    public static void main(String[] args) throws IOException {

        InputStreamReader iReader = new InputStreamReader(System.in);
        BufferedReader bReader = new BufferedReader(iReader);
        ArrayList seqA = new ArrayList();
        ArrayList seqB = new ArrayList();
        ArrayList lngIncSeq = new ArrayList();
        System.out.println("Enter a sequence of numbers seperated by space Hit enter to terminate");
        String seqString = bReader.readLine();
        if(seqString != null) {

            StringTokenizer tokenizer = new StringTokenizer(seqString);
            while(tokenizer.hasMoreTokens()) {

                seqA.add(tokenizer.nextToken());
            }
            System.out.println("seqList " + seqA.toString());
        }
        else
            System.out.println("No sequence");

        System.out.println("Enter a sequence of numbers seperated by space Hit enter to terminate");
        seqString = bReader.readLine();
        if(seqString != null) {

            StringTokenizer tokenizer = new StringTokenizer(seqString);
            while(tokenizer.hasMoreTokens()) {

                seqB.add(tokenizer.nextToken());
            }
            System.out.println("seqList " + seqB.toString());
        }
        else
            System.out.println("No sequence");

        //compare seqA and seqB
        if(seqA.size() < seqB.size()){

            //enter elements of B to hashtable and compare them with the smaller list,seqA
            fillTable(seqB);
            compare(seqA);
        }
        else {
            //seqA will get into hashtable and is compared with the smaller list seqB
            fillTable(seqA);
            compare(seqB);
        }    

    }

    public static void fillTable(ArrayList list) {

        Iterator listItr = list.iterator();
        while(listItr.hasNext()) {

            table.put(Integer.parseInt(listItr.next().toString()), 0);
        }
     }

    public static void compare(ArrayList list) {

        int tableLookup = 0;
        //for each element in the list lookup whether its in the list
        //if so set the elements val = 1.
        //finally print the elements in the table with val = 1. they are the elements common to both
        Iterator listItr = list.iterator();
        while(listItr.hasNext()) {

            int elt =  Integer.parseInt((String)(listItr.next()));
            System.out.println("elt " + elt);
             if(table.get(elt) != null) {

                 tableLookup = (int) table.get(elt);
                 table.put(elt, 1); //this elt matches
             }
        }

        System.out.println("Printing the common elements");
        //get the set of entries
        Set set = table.entrySet();
        //get an iterator
        Iterator itr = set.iterator();
        while(itr.hasNext()) {

            Map.Entry elt = (Map.Entry)itr.next();
            if(elt.getValue() == 1){
                System.out.println(elt.getKey());
            }
        }
    }
}

Given a string.Replace the words whose length>=4 and is even,with a space between the two equal halves of the word.consider only alphabets for finding the eveness of the word

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package XXXXX;

import java.util.StringTokenizer;

/**
*
* @author poochedi
*/
public class SplitStringHalves {

public static void main(String[] args) {

String input = “Hello How are youu eleven’s heartt”;
String output = “”;
StringTokenizer st = new StringTokenizer(input);
while(st.hasMoreTokens()) {

String string = st.nextToken();
if(string.length() >=4 && string.length()%2 == 0) {

System.out.println(“String qualified ” + string);
int spaceAfter = string.length() / 2; //determine space after how many chars
System.out.println(“Space needed ” + spaceAfter);
String stringPartA = string.substring(0,string.length()/2);
if(stringPartA.length() == spaceAfter)
stringPartA+=” “;
String stringPartB = string.substring(string.length()/2, string.length());
string = stringPartA + stringPartB;
System.out.println(“String ” + string);
}

output+=” ” + string;
}
System.out.println(“Input ” + input);
System.out.println(“Output ” + output);
}

}

You have a stream of numbers of unknown length. When you hit a zero, the stream is terminated. Return the largest even number and the largest odd number.

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package XXXX;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.ArrayList;
/**This prog accepts input until user enters 0
* then find the largest odd and largest even number
*
* @author poochedi
*/
public class StreamOfNumbers {

public static void main(String[] args) throws IOException {

ArrayList oddList = new ArrayList();
ArrayList evenList = new ArrayList();
int maxOdd = 0;
int maxEven = 0;
System.out.println(“Enter the input. enter 0 to terminate”);
BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
String input = bReader.readLine();
int inputNumber = Integer.parseInt(input);

while(inputNumber !=0) {
//classify this input number
if(inputNumber%2 == 0) {

//this number is even
evenList.add(inputNumber);
}

else {

oddList.add(inputNumber);
}

//accept more input
System.out.println(“Enter the input. enter 0 to terminate”);
input = bReader.readLine();
inputNumber = Integer.parseInt(input);

}

//user entered a 0 So terminate getting the input
//Now find the maximum of the odd number and max of even number

if(!oddList.isEmpty()){

maxOdd = (int) Collections.max(oddList);
System.out.println(” Max Odd ” + maxOdd);
}
else if(oddList.isEmpty())
System.out.println(“OddList empty”);

if(!evenList.isEmpty()) {

maxEven = (int) Collections.max(evenList);
System.out.println(” Max Even ” + maxEven);
}
else if(evenList.isEmpty())
System.out.println(“Even list empty”);

}
}