Good day. Hope all is going well with you. As you will read in this post, something different and perhaps unique occurred. I clearly recall solving this problem and making a note that I had to modify the test code offered by HackerRank. Earlier this morning I received the following email message:
[JohnCanessa/FullCountingSort] Test Case 5 doesn't works (#1) Inbox Prateek <notifications@github.com> Unsubscribe 1:19 AM (14 hours ago) to JohnCanessa/FullCountingSort, Subscribed — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or unsubscribe.
Apparently a HackerRank problem I solved 17 months ago stopped working. Not really. It seems that it was too slow. Test case #5 which contains 1,000,000 input lines is now taking too long. Go figure!
If interested in this issue and problem I would suggest for you to first take a look at The Full Counting Sort post in this blog.
I will not describe the problem here. You can get to it via a link in the post The Full Counting Sort.
4 0 a 1 b 0 c 1 d - c - d 20 0 ab 6 cd 0 ef 6 gh 4 ij 0 ab 6 cd 0 ef 6 gh 0 ij 4 that 3 be 0 to 1 be 5 question 1 or 2 not 4 is 2 to 4 the - - - - - to be or not to be - that is the question - - - - 10 1 e 2 a 1 b 3 a 4 f 1 f 2 a 1 e 1 b 1 c - - f e b c - a - - 20 88 pe 36 uw 57 ng 58 lt 29 gv 44 be 22 bz 67 yd 20 xm 86 gy 99 dd 35 eg 19 qc 65 jm 6 po 76 xv 72 qm 24 vn 98 mr 11 ab po ab qc - - vn - eg - - - - jm - qm xv - - mr dd
These are the same test cases I used 17 months ago. They still seem to work.
/**
* Original test scaffold.
*/
// public static void main(String[] args) throws IOException {
// // **** ****
// BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
// // **** ****
// int n = Integer.parseInt(bufferedReader.readLine().trim());
// // **** ****
// List<List<String>> arr = new ArrayList<>();
// // **** ****
// IntStream.range(0, n).forEach(i -> {
// try {
// arr.add(Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" ")).collect(toList()));
// } catch (IOException ex) {
// throw new RuntimeException(ex);
// }
// });
// // **** close the buffered reader ****
// bufferedReader.close();
// // **** function of interest (fails on test case #5) ****
// countSort0(arr);
// // **** function of interest (fails on test case #5) ****
// countSort(arr);
// }
I used the original test case provided by HackerRank. After reading and parsing the input lines into a List<List<String>> data structure, it makes one (I added a second one) call to the function in question.
All test cases passed except #5. After experimenting I decided to process the input directly from the test case bypassing the function of interest. In other words, I wrote the solution directly in the test code. As you can verify, I did something similar when I originally wrote the solution for this problem 17 months ago.
In conclusion this code does not work.
/**
* Complete the countSort function below.
* Using StringBuilder.
*
* !!! Too slow !!!
*/
static void countSort0(List<List<String>> arr) {
// **** initialization ****
int ndx = 0;
StringBuilder[] sb = new StringBuilder[100];
for (int i = 0; i < 100; i++)
sb[i] = new StringBuilder();
// **** set first half of the strings to "- " ****
for (int i = 0; i < (arr.size() / 2); i++) {
// **** set index to string to integer ****
ndx = Integer.parseInt(arr.get(i).get(0));
// **** ****
sb[ndx].append("- ");
}
// **** append strings with same index to respective string builder ****
for (int i = arr.size() / 2; i < arr.size(); i++) {
// **** set index to string to integer ****
ndx = Integer.parseInt(arr.get(i).get(0));
// **** ****
sb[ndx].append(arr.get(i).get(1) + " ");
}
// **** display result string ****
for (int i = 0; i < 100; i++) {
// **** skip blank string builder ****
if (sb[i].toString().equals("")) continue;
// **** display string builder ****
System.out.print(sb[i].toString());
}
// **** terminate line ****
System.out.println();
}
This was my first attempt to implement the function of interest. Test case #5 failed.
/**
* Complete the countSort function below.
* Using StringBuffer.
*
* !!! Too slow !!!
*/
static void countSort(List<List<String>> arr) {
// **** sanity check(s) ****
if (arr == null || arr.size() == 0) return;
// **** initialization ****
String str;
StringBuffer[] sb = new StringBuffer[100];
for (int i = 0; i < 100; i++)
sb[i] = new StringBuffer();
int size = arr.size();
// **** traverse all entries in the string array ****
for (int i = 0; i < size; i++) {
// **** generate index ****
int ndx = Integer.parseInt(arr.get(i).get(0));
// **** set string ****
if (i < size / 2) // top half
str = "- ";
else // bottom half
str = arr.get(i).get(1) + " ";
// **** append string to string buffer ****
sb[ndx] = sb[ndx].append(str);
}
// **** display result string ****
for (int i = 0; i < 100; i++) {
// **** skip blank string buffer ****
if (sb[i].toString().equals("")) continue;
// **** display contents of string buffer ****
System.out.print(sb[i]);
}
}
This was my second attempt to implement the function of interest. Test case #5 failed.
As you can see I made a few changes but no success.
/**
* Test scaffolding.
*
* UNACCEPTABLE having to replace the provided test scaffold.
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
// **** get the number of elements ****
int n = Integer.parseInt(bufferedReader.readLine().trim());
// **** initialize the array of StringBuffers ****
StringBuffer[] sb = new StringBuffer[100];
for (int i = 0; i < 100; i++)
sb[i] = new StringBuffer();
// **** process all `n` entries ****
String str;
for (int i = 0; i < n; i++) {
// **** read input line and split it ****
String[] strs = bufferedReader.readLine().trim().split(" ");
// **** extract index ****
int ndx = Integer.parseInt(strs[0]);
// **** set string ****
if (i < n / 2) // top half
str = "- ";
else // bottom half
str = strs[1] + " ";
// **** append string to string buffer ****
sb[ndx] = sb[ndx].append(str);
}
// **** display result string ****
for (int i = 0; i < 100; i++) {
// **** skip blank string buffer ****
if (sb[i].toString().equals("")) continue;
// **** display contents of string buffer ****
System.out.print(sb[i]);
}
// **** close buffered reader ****
bufferedReader.close();
}
This version of the code was accepted by HackerRank. It passed all test cases including #5.
We start by opening a buffered reader.
We read the number of input lines and assign the value to `n`.
We then declare and initialize the array of string buffers.
We then enter a loop that reads and processes all the `n` entries.
In the loop we read the current line and split it into two parts. The first contains the index from the string and the second the actual string.
We extract the index value into the `ndx` variable.
Next we set the string in the string builder array. Note that for the first half of the values we append the string “- “, and for the second half we append the string from the current line (the one we just read).
After the first loop is completed, we have to display the result. We do so by displaying the non-empty string buffer array entries. This saves the time of concatenating them into a string buffer and then displaying it.
When all is set and done we close the buffered reader. We always do this in the main procedure.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John