3
\$\begingroup\$

This is a hackerank easy question.

You are given a list of N people who are attending ACM-ICPC World Finals. Each of them are either well versed in a topic or they are not. Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics.

Note Suppose a, b, and c are three different people, then (a,b) and (b,c) are counted as two different teams.

Input Format

The first line contains two integers, N and M, separated by a single space, where N represents the number of people, and M represents the number of topics. N lines follow. Each line contains a binary string of length M If the i'th line's j'th character is 1, then the i'th person knows the j'th topic; otherwise, he doesn't know the topic.

Constraints

2≤N≤500
1≤M≤500

Output Format

On the first line, print the maximum number of topics a 2-person team can know. On the second line, print the number of 2-person teams that can know the maximum number of topics.

Here is what I wrote:

Scanner console = new Scanner(System.in);
int n = console.nextInt();
int m = console.nextInt();
console.nextLine();
String[] arr = new String[n];
for(int p=0; p<n; p++){
    String s = console.nextLine();
    arr[p] = s;
}


Map<Integer, List<List<Integer>>> counts = new HashMap<>();

for(int i = 0; i< n-1; i++){

    String str=arr[i];

    for(int j=i+1; j<n; j++){


        String secondStr = arr[j];

        int count = 0;
        for(int k=0; k<m; k++){

            if(str.charAt(k) == '1' || secondStr.charAt(k) == '1'){
                count ++;
            }

        }

        List<Integer> mapping = new ArrayList<>();
        mapping.add(i+1);
        mapping.add(j+1);

        if(counts.containsKey(count)){
            List<List<Integer>> existingMappings = counts.get(count);
            existingMappings.add(mapping);
            counts.put(count, existingMappings);
        }else{
            List<List<Integer>> newMappings = new ArrayList<>();
            newMappings.add(mapping);
            counts.put(count, newMappings);
        }


    }
}

int max = counts.keySet().stream().mapToInt(Integer::valueOf).max().orElse(0);

int occurences = counts.get(max).size();

System.out.println(max);
System.out.println(occurences);

This worked and passed the challenge. But it has a code smell: Too many loops and even inner loops. Any improvements?

\$\endgroup\$
2
\$\begingroup\$

This part can be optimized a bit, in terms of length.

List<Integer> mapping = new ArrayList<>();
mapping.add(i+1);
mapping.add(j+1);

if(counts.containsKey(count)){
    List<List<Integer>> existingMappings = counts.get(count);
    existingMappings.add(mapping);
    counts.put(count, existingMappings);
}else{
    List<List<Integer>> newMappings = new ArrayList<>();
    newMappings.add(mapping);
    counts.put(count, newMappings);
}

Java 8 maps have computeIfAbsent. You can use this to "getOrCreate" the existing mapping like so:

List<Integer> mapping = new ArrayList<>();
mapping.add(i+1);
mapping.add(j+1);

counts.computeIfAbsent(count, k -> new ArrayList<>()).add(mapping);

Additionally, you do this:

    List<List<Integer>> existingMappings = counts.get(count);
    existingMappings.add(mapping);
    counts.put(count, existingMappings);

There is no need to put something back into the map when you have retrieved it, because you are retrieving a pointer to a list, and you're using it to add to a list. See this Ideone that lists you put and later retrieve from the map are the same lists.

Okay, so back to this snippet.

List<Integer> mapping = new ArrayList<>();
mapping.add(i+1);
mapping.add(j+1);

counts.computeIfAbsent(count, k -> new ArrayList<>()).add(mapping);

The new ArrayList constructor can take an initialSize argument. Since you're only going to be adding two integers to the list, you could provide this information and save memory space.

List<Integer> mapping = new ArrayList<>(2);

Your algorithm could be more optimized - there's no need to count topic knowledge for a team if they know 7 topics together and there's only 6 topics left to check and the top team currently knows 14 topics. Similarily, there's no reason to store how much topics each team knows, only the teams that know the largest amount of topics, and the largest amount of topics you have currently found.

However, I think that when we look at the loops, you can't really get rid of them.

You see, there's two loops needed to make the teams (iterating people over people), and one loop needed to check the topics (iterating over topics). There are clever tricks you could use where you take the binary string and convert it to an integer, but when you do that, you're looping over the characters in the binary string - it has to read the string, after all. You just don't use a for loop.

So we're doomed to have at least 3 loops. What you CAN do is take the counting loop and put it in a separate function. That would "get rid" of one of the loops. Your static analyzer is not built with the idea of such challenges in mind - to see a method with 3 nested loops usually means the method is doing too much work.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.