Interview Coding Java Sorting

Question

Write a java program to read input from a file, and then sort the characters within each word. Once you have done that, sort all the resulting words in ascending order and finally followed by the sum of numeric values in the file.

• Remove the special characters and stop words while processing the data
• Measure the time taken to execute the code

Lets Say the content of file is: Sachin Tendulkar scored 18111 ODI runs and 14692 Test runs.

Output:achins adeklnrtu adn cdeors dio estt nrsu nrsu 32803

Time Taken: 3 milliseconds

My Code takes 15milliseconds to execute.....

please suggest me any fast way to solve this problem...........

Code:

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.*;

public class Sorting {

    public static void main(String[] ags)throws Exception
    {
        long st=System.currentTimeMillis();
        int v=0;
        List ls=new ArrayList();
        //To read data from file
        BufferedReader in=new BufferedReader(
                 new FileReader("D:\\Bhive\\File.txt"));
        String read=in.readLine().toLowerCase();
        //Spliting the string based on spaces
        String[] sp=read.replaceAll("\\.","").split(" ");
        for(int i=0;i<sp.length;i++)
        {
            //Check for the array if it matches number
            if(sp[i].matches("(\\d+)"))
                //Adding the numbers
                v+=Integer.parseInt(sp[i]);
            else
            {
                //sorting the characters
                char[] c=sp[i].toCharArray();
                Arrays.sort(c);
                String r=new String(c);
                //Adding the resulting word into list
                ls.add(r);
            }
        }
        //Sorting the resulting words in ascending order
        Collections.sort(ls);
        //Appending the number in the end of the list
        ls.add(v);
        //Displaying the string using Iteartor
        Iterator it=ls.iterator();
        while(it.hasNext())
            System.out.print(it.next()+" ");
        long time=System.currentTimeMillis()-st;
        System.out.println("\n Time Taken:"+time);
    }
}

Answer 1

Use indexOf() to extract words from your string instead of split(" "). It improves performance.

See this thread: Performance of StringTokenizer class vs. split method in Java

Also, try to increase the size of the output, copy-paste the line Sachin Tendulkar scored 18111 ODI runs and 14692 Test runs. 50,000 times in the text file and measure the performance. That way, you will be able to see considerable time difference when you try different optimizations.

EDIT

Tested this code (used .indexOf())

        long st = System.currentTimeMillis();
        int v = 0;
        List ls = new ArrayList();
        // To read data from file
        BufferedReader in = new BufferedReader(new FileReader("D:\\File.txt"));
        String read = in.readLine().toLowerCase();
        read.replaceAll("\\.", "");
        int pos = 0, end;
        while ((end = read.indexOf(' ', pos)) >= 0) {
            String curString = read.substring(pos,end);
            pos = end + 1;
        // Check for the array if it matches number
            try {
                // Adding the numbers
                v += Integer.parseInt(curString);
            }
            catch (NumberFormatException e) {
                // sorting the characters
                char[] c = curString.toCharArray();
                Arrays.sort(c);
                String r = new String(c);
                // Adding the resulting word into TreeSet
                ls.add(r);
            }
        }
        //sorting the list
        Collections.sort(ls);
        //adding the number
        list.add(v);
        // Displaying the string using Iteartor 
        Iterator<String> it = ls.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        long time = System.currentTimeMillis() - st;
        System.out.println("\n Time Taken: " + time + " ms");

Performance using 1 line in file
Your code: 3 ms
My code: 2 ms

Performance using 50K lines in file
Your code: 45 ms
My code: 32 ms

As you see, the difference is significant when the input size increases. Please test it on your machine and share results.