Hello friends,
I recently participated in a hiring contest where i came across this question where in I have to sort the given set of strings using the given n characters from the beginning and the sorting should be a stable sort [Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list - says wikipedia].
For example if the string are,
abcdefgh
abcaaaaa
aabaaaaa
and the n value is 3, then the output should be like
aabaaaaa
abcdefgh
abcaaaaa
I dont know how one will start solving this problem, but this is how i started. I used a built in method called Arrays.sort() with a custom compare function.
Arrays.sort(ar, new Comparator() {
public int compare(String str1, String str2) {
String substr1 = str1.substring(0,limit);
String substr2 = str2.substring(0,limit);
return substr1.compareTo(substr2);
}
});
Here ar is my array of strings. I created a comparator object which will override the default compare function. Inside the function I am comparing the two strings by taking their substrings to the value of M (no of characters to compare for sorting).
Here if you use return substr1.compareTo(substr2) it will be sorted in ascending order of the substring and if you use return substr2.compareTo(substr1) it will be sorted in descending order.
The final program for the above problem.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
class MyClass {
public static void main(String args[] ) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=0,M=0;//N - number of strings and M number of characters to use for sorting
String inp=br.readLine();
String sp[]=inp.split(" ");
N=Integer.parseInt(sp[0]);
M=Integer.parseInt(sp[1]);
String ar[]=new String[N];
for(int j=0;j<N;j++){
ar[j]=br.readLine();
}
final int limit=M;
Arrays.sort(ar, new Comparator() {
public int compare(String str1, String str2) {
String substr1 = str1.substring(0,limit);
String substr2 = str2.substring(0,limit);
return substr2.compareTo(substr1);
}
});
System.out.println("After Stable Sorting");
for(int j=0;j<N;j++)
System.out.println(ar[j]);
The above is not the complete problem asked in the process. I just took the main part in that problem and I have given the solution.
I hope it might be useful for someone!
