Find duplicate lines in 1 and more files

Step 1: In Windows machine collect all files in one folder (temp)and execute the command in the command prompt
type *.*> main.txt
Step 2: Copy this file to a unix machine and execute the following command
sort main.txt | uniq --count > result.txt
In result.txt, all those lines which has count more than 1 are duplicates.

Java Generic Merge Sort - Top Down Approach

Reference : http://en.wikipedia.org/wiki/Merge_sort

package sorting;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

public class MergeSort {
    private Object[] data = null;
    private Comparator<Object> comparator = null;
    
    public MergeSort(Object[] data, Comparator<Object> comparator){
        this.data = data;
        this.comparator = comparator;
    }
    
    public Object[] sort(){
        return sort(data);
    }
    
    private Object[] sort(Object[] data) {
        if(data==null || data.length<2)
            return data;
        //divide into two sublist till it has only one element
        int middle = data.length/2;
        Object[] first = Arrays.copyOfRange(data, 0, middle);
        Object[] second = Arrays.copyOfRange(data, middle, data.length);
        
        //merge two list into one and do this recursively till you get one list.
        return merge(sort(first), sort(second));
    }

    private Object[] merge(Object[] first, Object[] second) {
        ArrayList<Object> result = new ArrayList<Object>();
        Queue<Object> firstQueue = new LinkedList<Object>();
        for(Object o:first)
            firstQueue.add(o);
        Queue<Object> secondQueue = new LinkedList<Object>();
        for(Object o:second)
            secondQueue.add(o);
        while(firstQueue.size()>0 || secondQueue.size()>0){
            if(firstQueue.size()>0 && secondQueue.size()>0){
                if(comparator.compare(firstQueue.peek(),secondQueue.peek())<=0){
                    result.add(firstQueue.remove());
                }else{
                    result.add(secondQueue.remove());
                }
            }else if(firstQueue.size()>0){
                result.add(firstQueue.remove());
            }else{
                result.add(secondQueue.remove());
            }
        }
        return result.toArray();
    }
}

Java Generic QuickSort

Reference : http://en.wikipedia.org/wiki/Quick_sort

package sorting;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

import types.Employee;

public class QuickSort {

    
    private Object[] _dataToBeSorted = null;
    //comparator to compare any type of element
    private Comparator<Object> _comparatorForData = null;
    public QuickSort(Object[] data, Comparator<Object> comparator){
        _dataToBeSorted = data;
        _comparatorForData = comparator;
    }
    
    public Object[] sort(){
        return sort(_dataToBeSorted);
    }
    
    private Object[] sort(Object[] dataToBeSorted){
        //if the dataToBeSorted is empty return as it is.
        if(dataToBeSorted == null || dataToBeSorted.length < 1){
            return dataToBeSorted;
        }
        
        //find pivot
        int pivotIndex = dataToBeSorted.length/2;
        List<Object> lessThan = new ArrayList<Object>();
        List<Object> greaterThan = new ArrayList<Object>();
        
        //separate elements less than pivot and greater than pivot 
        for(int i=0; i < dataToBeSorted.length; i++){
            if(i == pivotIndex){
                continue;
            }else if(_comparatorForData.compare(dataToBeSorted[i], dataToBeSorted[pivotIndex]) >= 0){
                greaterThan.add(dataToBeSorted[i]);
            }else if(_comparatorForData.compare(dataToBeSorted[i], dataToBeSorted[pivotIndex]) < 0){
                lessThan.add(dataToBeSorted[i]);
            }
        }
        
        List<Object> sortedData = new ArrayList<Object>();
        //join collected less than elements on the left of the pivot after sorting them (recursive).
        for(Object objToAdd:this.sort(lessThan.toArray()))
            sortedData.add(objToAdd);
        sortedData.add(dataToBeSorted[pivotIndex]);
        //join collected greater than elements on the right of the pivot after sort them (recursive).
        for(Object objToAdd:this.sort(greaterThan.toArray()))
            sortedData.add(objToAdd);
        return sortedData.toArray();
    }
    
    public static void main(String[] args) {
        /*//Integer
        Object[] data = {2,3,1,5,4};
        Comparator<Object> comparator = new Comparator<Object>() {
            
            @Override
            public int compare(Object m1, Object m2) {
                Integer o1 = (Integer) m1;
                Integer o2 = (Integer) m2;
                if(o1 == o2)
                    return 0;
                else if(o1 > o2)
                    return 1;
                return -1;
            }
        };*/
        
        /*//String
        Object[] data = {"xyz","abc","mno"};
        Comparator<Object> comparator = new Comparator<Object>() {
            
            @Override
            public int compare(Object m1, Object m2) {
                String o1 = (String) m1;
                String o2 = (String) m2;
                if(o1.equals(o2))
                    return 0;
                else if(o1.compareTo(o2) > 0)
                    return 1;
                return -1;
            }
        };*/
        
        //Employee
        Employee e1 = new Employee("c1", "xyz", 26);
        Employee e2 = new Employee("c2", "abc", 25);
        Employee e3 = new Employee("c3", "mno", 27);
        Object[] data ={e1, e2, e3};
        /*Comparator<Object> comparator = new Comparator<Object>() {
            
            @Override
            public int compare(Object m1, Object m2) {
                Employee o1 = (Employee) m1;
                Employee o2 = (Employee) m2;
                if(o1.name.equals(o2.name))
                    return 0;
                else if(o1.name.compareTo(o2.name) > 0)
                    return 1;
                return -1;
            }
        };*/
        Comparator<Object> comparator = new Comparator<Object>() {
            
            @Override
            public int compare(Object m1, Object m2) {
                Employee o1 = (Employee) m1;
                Employee o2 = (Employee) m2;
                if(o1.age == o2.age)
                    return 0;
                else if(o1.age > o2.age)
                    return 1;
                return -1;
            }
        };
        
        QuickSort quickSort = new QuickSort(data, comparator);
        for(Object a : quickSort.sort()){
            System.out.println(a.toString());
        }

    }
}

The Unscrambler (Anagrams)

When i was working for a gaming company, there used to be quarterly competitions conducted online. one of them was unscramble. A jumbled letters will be given and you have to find anagrams. I implemented this programatically. My implemention will give results in short time for 7 words, will take a lot of time for words more than that.

I used brute force method. I construct a master word from which small words will be taken and looked up in a dictionary file (dict.txt). There are 3 files. The output for "estma" is
Enter Letters : estma
1 : steam
2 : mates
Finish

The reason why i can't find teams, meats etc.. is, the dict.txt have only singulars for those words.

UnScrambler.java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class UnScrambler {
    private static String word;
    private static int p = 0;

    static void getWord() throws IOException {
        BufferedReader d = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Enter Letters : ");
        word = d.readLine();
    }

    static StringBuffer genMasterWord() {
        StringBuffer sb1 = new StringBuffer();
        StringBuffer sb2 = new StringBuffer();
        StringBuffer sb3 = new StringBuffer();
        char a[] = word.toLowerCase().toCharArray();
        for (int i = 0; i < a.length; i++) {
            for (int j = i; j >= 0; j--) {
                for (int o = j, l = fact(i); l - 1 >= 0; l--, o = o + i + 1) {
                    sb1 = sb1.insert(o, a[i]);
                }
                for (; p == 0; p--) {
                    sb1 = sb1.insert(p, a[i]);
                }
                sb2 = sb2.append(sb1);
                sb1 = new StringBuffer();
                sb1 = sb1.append(sb3);
            }
            sb3 = sb2;
            sb2 = new StringBuffer();
            sb1 = new StringBuffer();
            sb1 = sb1.append(sb3);
        }
        return sb3;
    }

    public static List<String> formWord() {
        StringBuffer b = genMasterWord();
        List<String> li = new ArrayList<String>();
        String a = b.toString();
        for (int j = 0; j < a.length(); j = j + word.length())
            // System.out.println((i++)+" : "+a.substring(j,j+word.length()));
            li.add(a.substring(j, j + word.length()));
        return li;
    }

    public static int fact(int i) {
        int r;
        if (i == 1)
            return 1;
        else if (i == 0)
            return 0;
        r = fact(i - 1) * i;
        return r;
    }

    public static List<String> loadDict() throws IOException {
        String e;
        int i = 0;
        List<String> dic = new ArrayList<String>();
        FileInputStream fi = new FileInputStream("dict.txt");
        BufferedReader d = new BufferedReader(new InputStreamReader(fi));

        while ((e = d.readLine()) != null) {
            i++;
            dic.add(e.toLowerCase());

        }
        return dic;

    }

}

TestUS.java

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class TestUS {

    public static void main(String[] args) throws IOException {
        List<String> word = new ArrayList<String>();
        List<String> dic = new ArrayList<String>();
        List<String> result = new ArrayList<String>();
        UnScrambler.getWord();
        word = UnScrambler.formWord();
        ListIterator<String> wli = word.listIterator();
        dic = UnScrambler.loadDict();

        int k = 1;
        while (wli.hasNext()) {
            String a = wli.next();
            if (dic.contains(a)) {
                if (!result.contains(a)) {
                    result.add(a);
                    System.out.println((k++) + " : " + a);
                }

            }
        }
        System.out.println("Finish");
    }
}

dict.txt
I found the dictionary file in C:\Program Files (x86)\Mozilla Firefox\dictionaries. I removed some of the unwanted chars and words from this file programmatically. download here

Print all running process in windows using vc++

DWORD pProcessIds[256];
DWORD cb = 256;
DWORD pBytesReturned;
if(!EnumProcesses(pProcessIds,cb,&pBytesReturned))
    return 0;
long lnoofprocess = pBytesReturned/sizeof(DWORD);
DWORD dwDesiredAccess = PROCESS_QUERY_INFORMATION;
BOOL bInheritHandle = TRUE;
for(long i=0; i<lnoofprocess; i++){
    DWORD dwProcessId = pProcessIds[i];
    HANDLE hProcess=NULL;
    hProcess = OpenProcess(dwDesiredAccess,bInheritHandle,dwProcessId);
    if(hProcess==NULL) continue;
    LPSTR lpImageFileName = new char[256];
    DWORD nSize = 256;
    if(!GetProcessImageFileNameA(hProcess,lpImageFileName,nSize)) continue;
    char *pfrdslh = strrchr(lpImageFileName, 92);
    cout<<pfrdslh+1<<endl;
    delete [] lpImageFileName;
}

IVY TOP CODER CHALLENGE 2011

I participated in IVY Topcoder 2011 and submitted my code
Question:Musical Water Fountains
Andhra Pradesh tourism is planning to construct a park and install water fountains. It is planning to organize "Musical Fountain" shows.
The fountains shoot water in air in varying directions and with varying heights.
Fountains are to be installed in a row such that water from all the fountains is visible.
You are given int[] height, int[] turnOnTime, and int[] turnOffTime.
height represents how high each fountain shoots water in air, turnOnTime represents the time when fountain shoots the water in air and
turnOffTime represents the time when fountain stops shooting the water. Musical fountain show would be for 30 minutes.
Elements in turnOnTime and turnOffTime will be a number between 1 and 30 inclusive and turnOffTime [i] will always be greater than turnOnTime [i].
Fountain that shoots water high in air is to be installed as far as possible. The fountain that shoots water with less height must be installed in
front of the fountain that shoots water high in air to prevent blocking. A fountain can start shooting water and other stops at the same minute but
still one can block the other. You should also try to have the fountain with maximum possible height being first in the park.
You should return a int[] which contains the elements of height in the order you should install fountains to achieve the above goal.
The front of the park is represented by the first element in your return value, and is where you view the fountains from. The elements in height []
will all be unique
Definition
Class: MusicalFountain
Method: getFountainOrdering
Parameters: int[], int[], int[]
Returns: int[]
Method signature: int[]getFountainOrdering (int[] height, int[] turnOnTime, int[] turnOffTime) (be sure your method is public)
Constraints
height will have between 2 and 10 unique elements, inclusive.
turnOnTime and turnOffTime will have the same number of elements as height.
Each element of height will be between 1 and 30 meters, inclusive.
Each element of turnOnTime and turnOffTime will be between 1 and 30 minutes, inclusive.
 For each element i of turnOnTime and turnOffTime, turnOffTime [i] will be greater than turnOnTime [i].
Example 1

height[] = {6, 5, 4, 3, 2, 1}
turnOnTime [] = {1, 1, 1, 1, 1, 1}
turnOffTime [] = {30, 30, 30, 30, 30, 30}
Returns: {1, 2, 3, 4, 5, 6}
All fountains start at 1st minute and stop at 30th minute. All will block each other; you must order them from shortest to tallest.
Example 1

height[] = {6, 5, 4, 3, 2, 1}
turnOnTime [] = {1, 5, 10, 15, 20, 25}
turnOffTime [] = {4, 9, 14, 19, 24, 29}
Returns: {6, 5, 4, 3, 2, 1}
The fountains start and stop at different times so they will never block each other. You can order them from tallest to shortest.

package topcoder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class MusicalFountain {
    public static int[]getFountainOrdering (int[] input1, int[] input2, int[] input3){
        ArrayList<Integer> result = new ArrayList<Integer>();
        arrange(input1, input2, input3);
        result.add(input1[0]);
        for(int i = 1; i < input1.length; i++){
            int newPos = i;
            for(int j = i-1; j >= 0; j--){
                if(((input2[i] >= input2[j] && input2[i] <= input3[j])
                    || (input3[i] >= input2[j] && input3[i] <= input3[j])
                    || (input2[j] >= input2[i] && input2[j] <= input3[i])
                    || (input3[j] >= input2[i] && input3[j] <= input2[i]))
                    && (input1[i] < input1[j])){
                        int temp = result.indexOf(input1[j]);
                        newPos = temp < newPos ? temp : newPos;
                }/*else if(input1[i] > input1[j]){
                    int temp = result.indexOf(input1[j]);
                    newPos = temp < newPos ? temp : newPos;
                }*/
            }
            result.add(newPos, input1[i]);
        }
        int[] finalResult = new int[input1.length];
        for(int i = 0; i < result.size(); i++){
            finalResult[i] = result.get(i);
        }
        return finalResult;
    }
    public static void arrange(int input1[], int input2[], int input3[]){
        ArrayList<Integer> heightList = new ArrayList<Integer>();
        for(int i:input1)
            heightList.add(i);
        Comparator<Integer> reverse    = Collections.reverseOrder();
        Collections.sort(heightList, reverse);
        arrangeDependent(input1, heightList, input2);
        arrangeDependent(input1, heightList, input3);
        for(int i=0; i<heightList.size(); i++)
            input1[i] = heightList.get(i);
    }
    private static void arrangeDependent(int[] input1, ArrayList<Integer> heightList, int[] data) {
        int[] tempData = new int[input1.length];
        for(int oldIndex=0; oldIndex<input1.length; oldIndex++){
            int newIndex = heightList.indexOf(input1[oldIndex]);
            tempData[newIndex] = data[oldIndex];
        }
        for(int i=0; i<data.length; i++){
            data[i] = tempData[i];
        }
    }
    public static void main(String[] args) {
        /*int[]height={6, 5, 4, 3, 2, 1}; 
        int turnOnTime [] = {1, 1, 1, 1, 1, 1};
        int turnOffTime [] = {30, 30, 30, 30, 30, 30};*/
        
        /*int height[] = {6, 5, 4, 3, 2, 1};
        int turnOnTime [] = {1, 5, 10, 15, 20, 25};
        int turnOffTime [] = {4, 9, 14, 19, 24, 29};*/ 
        
        /*int height[] = {6, 5, 4, 3, 2, 1};
        int turnOnTime [] = {1, 5, 10, 15, 20, 25};
        int turnOffTime [] = {5, 10, 15, 20, 25, 30};*/
        
        /*int height[] = {5, 4, 3, 2, 1, 6};
        int turnOnTime [] = {6, 10, 15, 20, 2, 1};
        int turnOffTime [] = {9, 15, 20, 25, 5, 6};*/
        
        /*int height[] = {1,    2,    3,    4,    5,    6};
        int turnOnTime[] = {1,    16,    1,    16,    1,    16};
        int turnOffTime[] = {15,    30,    15,    30,    15,    30};*/
        
        int height[] = {1,3,5,2,4,6};
        int turnOnTime[] = {11,25,15,3,21,6};
        int turnOffTime[] = {15,30,25,5,25,10};
        
        /*arrange(height, turnOnTime, turnOffTime);
        printIntArray(height);
        printIntArray(turnOnTime);
        printIntArray(turnOffTime);*/
        
        int[] result=getFountainOrdering(height,turnOnTime,turnOffTime);
        printIntArray(result);
    }
    public static void printIntArray(int[] datas){
        for(int data:datas)
            System.out.println(data);
        System.out.println("END");
    }
}