Hackerrank : Hash Tables: Ransom Note

I just solved the Hash Tables: Ransom Note problem on Hackerrank using both Java-8 and Java-7. Given m words in a magazine and the n words in the ransom note, print Yes if a kidnapper can replicate his ransom note exactly (case-sensitive) using whole words from the magazine; otherwise, print No. 1 ≤ m, n ≤ 30000.

I am looking for suggestions regarding the efficiency, coding style and if this is the best way to solve this kind of problem.

Java-7

public class RansomeNotesJava7 {

    public static void main(String[] args) throws Exception{
        Scanner in = new Scanner(new File("input.txt"));
        int m = in.nextInt();
        int n = in.nextInt();
        String magazine[] = new String[m];
        for(int magazine_i=0; magazine_i  magazineMap = getFrequencyMapFromArray(magazine); //Arrays.stream(magazine).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        Map ransomMap =  getFrequencyMapFromArray(ransom); //Arrays.stream(ransom).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        System.out.println(magazineMap);
        System.out.println(ransomMap);

        for(String key : ransomMap.keySet()){
            if(!magazineMap.containsKey(key))
                return false;

            if(magazineMap.get(key)  getFrequencyMapFromArray(String[] arr) {

        Map map = new HashMap<>();

        for(String key : arr){
            if(map.containsKey(key))
                map.put(key, map.get(key)+1);
            else
                map.put(key, new Long("1"));
        }
        return map;
    }
}

Java-8

```
public class RansomNotes {

public static void main(String[] args) throws Exception {
Scanner in = new Scanner(new File("input.txt"));
int m = in.nextInt();
int n = in.nextInt();
String magazine[] = new String[m];
for (int magazine_i = 0; magazine_i magazineMap = getFrequencyMapFromArray(magazine);
Map ransomMap = getFrequen

Coding style

Overall looks good. I only got some small remarks:

Put {} after each if and else as well. This is mostly to prevent stupid bugs if you (or someone after you) adds an innocent looking line like this:

for(String key : ransomMap.keySet()){
    if(!magazineMap.containsKey(key))
        System.out.println("Not enough of: " + key);
        return false;  //<- this false is actually outside the if block now.

    if(magazineMap.get(key) < ransomMap.get(key))
        return false;
}

Suddenly it always returns false, even tho we just wanted to print which key wasn't found. Most IDE's can be set up to always place the braces for you.

A minor thing is also the name for magazineMap. I would rename this to magazineFrequencyMap to make it clear that it's a frequency map (like your great method name says to populate the map). But since that might feel a little long later on you'll have to decide for yourself what feels better.

The last thing is that you never close your Scanner. Since this is in your main method and your program ends after execusion it doesn't really matter much, but since we're talking best practices here I couldn't ignore this.

Efficiency

Why store the number of words in a Long if there's at most 30k of them? An Integer should do:

Map magazineMap = getFrequencyMapFromArray(magazine);

A major change to gain efficiency is to never build the frequency map for the ransom notes. Instead use the following strategy to solve the problem:

Put all the magazine words into a map like you did now.

Try to take each ransom word out of that bag while reading them from the file.

If it's not in the bag (or count is 0) you can stop here and return false

If you are "lucky" and the first ransom word is not present in your magazines you can stop early. This can save "a lot" of time counting the other ransom words. (Note that "a lot" means a couple of miliseconds probably, so it doesn't really matter that much for this problem).

the best way

I would argue that there is no best way to solve a computer problem. Only a better way given certain criterea.

For the given problem I would argue that my "take ransom words out of the existing bag as we go" is better since it's more memory efficient and fails faster.

If, however, we want to expand this problem later to:


Given a stack of magazines, which of these magazines can be used to write the ransom note?

Then it makes a lot more sense to read the ransom note once and put them into their own frequency map. Because we can use this map to compare with each of the magazine frequency maps like you did in your solution.

StackExchange Code Review Q#159872, answer score: 5