What I did:
1. Just sort an integer array
2. Sort an integer array in non-increasing order
3. Sort a string array in non-decreasing order of the length
4. Sort substrings (implemented a simple suffix-array-like algorithm)
Interesting stuff:
1. Comparator is like functor in C++.
2. Anonymous class is cool! I liked this style. You can write, on the spot, an implementation of its super class (or interface).
3. Java's string data structure is clever. The way it retains strings enable to share a memory with some strings. In the code test4(), all the substrings share a memory.
4. Looks like Java Api codes are way more legible than that of C++.
Source code:
I'll post the source code below.import java.util.Arrays;
import java.util.Comparator;
public class Test {
public static void main(String args[]) {
test1();
test2();
test3();
test4();
}
private static void test1() {
int xs[] = {4, 1, 4, 6, 3, 8, 10, 0};
Arrays.sort(xs);
System.out.println(Arrays.toString(xs));
}
private static void test2() {
Integer xs[] = {4, 1, 4, 6, 3, 8, 10, 0};
Arrays.sort(xs, new Comparator<Integer>() {
public int compare(Integer x, Integer y) {
return y-x;
}
});
System.out.println(Arrays.toString(xs));
}
private static void test3() {
String names[] = {
"hanako",
"taro",
"yu",
"sho",
"amataro",
"takafumi"
};
Arrays.sort(names, new Comparator<String>() {
public int compare(String x, String y) {
return x.length() - y.length();
}
});
System.out.println(Arrays.toString(names));
}
private static void test4() {
String text = "Oh, say can you see," +
"by the dawn's early light" +
"What so proudly we hailed" +
"at the twilight's last gleaming?" +
"Whose broad stripes and bright stars," +
"through the perilous fight." +
"O'er the ramparts we watched" +
"were so gallantly streaming?";
String word = "gallant";
// build a suffix array
String suffix[] = new String[text.length()];
for (int i = 0; i < text.length(); i++)
suffix[i] = text.substring(i);
Arrays.sort(suffix);
// search the word
int lo = 0;
int hi = text.length() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (suffix[mid].compareTo(word) < 0)
lo = mid + 1;
else
hi = mid;
}
if (suffix[lo].startsWith(word))
System.out.println(word + " is found!");
else
System.out.println(word + " is not found!");
}
}