It is Thursday April 11 and this area of the Twin Cities of Minneapolis and St. Paul has received since yesterday around noon to today around 04:00 PM about 10 inches of snow. Around noon today the snow stopped and we start receiving freezing rain. Schools are closed and there is very little traffic in the area.
According to the forecast, tomorrow will be raining during the day. Not sure if the precipitation will turn into freezing rain. One way or the other, staying home working is not a bad idea.
I received an email from HackerRank for the ACM ICPC Team challenge. I have been working with Node.js and REST APIs all day, so decided to take a break until tomorrow, and give the challenge a try.
I read the description a few times and work my way up. I like to use a test driven development (TDD) approach. Several people in the discussion section mentioned that the worse part of the challenge was to understand what needed to be done (not so good requirements). Perhaps the author thought that would be part of the challenge :o)
I used the following edited tests:
3 5
10101
11110
00010
(1,2)
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
count: 5
(1,3)
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
count: 4
(2,3)
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
count: 4
hm: {4=2, 5=1}
maxKey: 5
maxVal: 1
5
1
4 5
10101
11100
11010
00101
(1,2)
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 48
sca | scb: 49
count: 4
(1,3)
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
count: 5
(1,4)
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 49
sca | scb: 49
count: 3
(2,3)
sca: 49 scb: 49
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
count: 4
(2,4)
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 48 scb: 49
sca | scb: 49
count: 4
(3,4)
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
count: 5
hm: {3=1, 4=3, 5=2}
maxKey: 5
maxVal: 2
5
2
6 5
11101
10101
11001
10111
10000
01110
(1,2)
sca: 49 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 49
sca | scb: 49
count: 4
(1,3)
sca: 49 scb: 49
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 49
sca | scb: 49
count: 4
(1,4)
sca: 49 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
count: 5
(1,5)
sca: 49 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 48
sca | scb: 49
count: 4
(1,6)
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
count: 5
(2,3)
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 49
sca | scb: 49
count: 4
(2,4)
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
count: 4
(2,5)
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 48
sca | scb: 49
count: 3
(2,6)
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
count: 5
(3,4)
sca: 49 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
count: 5
(3,5)
sca: 49 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 48
sca | scb: 49
count: 3
(3,6)
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
count: 5
(4,5)
sca: 49 scb: 49
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
count: 4
(4,6)
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 49 scb: 49
sca | scb: 49
sca: 49 scb: 48
sca | scb: 49
count: 5
(5,6)
sca: 49 scb: 48
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 48 scb: 49
sca | scb: 49
sca: 48 scb: 48
sca | scb: 48
count: 4
hm: {3=2, 4=7, 5=6}
maxKey: 5
maxVal: 6
5
6
The edited refers to the fact that I added print statements to my solution while in development. They display test which will be rejected by the software evaluating the solution. At work I typically leave most of print statements. In actuality I use log statements which are written to files and have additional information (i.e., time, date, thread, source file, line number, etc). I also control what is logged by the use of a trace level variable that can be set per source file. Enable trace statements allows software development and DevOps engineers to reduce the time spent diagnosing issues. Have been using such techniques for a couple decades and I highly recommend them for any project. That said; I believe I went overboard in this example.
Let’s take a look at the method of interest:
// Complete the acmTeam function below.
static int[] acmTeam(String[] topic) {
// **** number of members ****
int n = topic.length;
// **** number of topics ****
int s = topic[0].length();
// **** [0]: maximum number of topics [1]: number of teams ****
int[] result = new int [2];
// ???? ????
// System.out.println("n: " + n);
// System.out.println("s: " + s);
// for (String str : topic)
// System.out.println("str ==>" + str + "<==");
// **** ****
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
// **** combinations of 2 of n ****
int maxTopics = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// ???? ????
System.out.println("(" + (i + 1) + "," + (j + 1) + ")");
// **** convert strings to character arrays ****
char[] sca = topic[i].toCharArray();
char[] scb = topic[j].toCharArray();
// **** determine the max topics ****
int count = 0;
for (int k = 0; k < s; k++) { // ???? ???? System.out.println("sca: " + (int)sca[k] + " scb: " + (int)scb[k]); System.out.println("sca | scb: " + (sca[k] | scb[k])); // **** 49 = '1' **** if ((sca[k] | scb[k]) == 49) count++; } // ???? ???? System.out.println("count: " + count); // **** update the maximum number of topics (if needed) **** if (count > maxTopics)
maxTopics = count;
// **** add to hash map ****
if (hm.containsKey(count)) {
int value = hm.get(count);
value++;
hm.put(count, value);
} else {
hm.put(count, 1);
}
}
}
// ???? ????
System.out.println("hm: " + hm.toString());
// **** ****
int maxVal = 0;
int maxKey = 0;
for (Entry<Integer, Integer> e: hm.entrySet()) {
int key = e.getKey();
int val = e.getValue();
if (key > maxKey) {
maxVal = val;
maxKey = key;
}
}
// ???? ????
System.out.println("maxKey: " + maxKey);
System.out.println("maxVal: " + maxVal);
// **** ****
result[0] = maxTopics;
result[1] = maxVal;
// **** ****
return result;
}
The first few lines in the method extract the information we will be using and sets the array to return the results.
The answer is based on combination of 2 out of n elements. You can read more about Combinations here. In our case we loop generating all the possible combinations.
For each set of combinations, we traverse the characters in the strings of interest. Note that 49 is the ACII representation for character ‘1’. We then count the instances when one of the characters at the specified location is a ‘1’.
We make us of a hash map to keep track of the number of teams that match the highest set of topics. This could also have been done directly with variables and arrays, but we do have access to the HashMap class. This holds true for many programming languages.
When done we pack the two required values into an array and return it to the caller.
My solution written in Java using the Eclipse IDE can be found in my GitHub repository.
Keep on reading and experimenting. It is the best way to learn!
If you have comments or questions regarding this or any other post in this blog, or if you need help with any technical or management aspect on any phase of the SDLC of a project, feel free and leave me a message. Requests for help will not be made public.
Enjoy;
John
@john_canessa