Hackerrank : Hash Tables: Ransom Note

Question

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 < m; magazine_i++){
            magazine[magazine_i] = in.next();
        }
        String ransom[] = new String[n];
        for(int ransom_i=0; ransom_i < n; ransom_i++){
            ransom[ransom_i] = in.next();
        }

        if(getRansom(m,n,magazine,ransom))
            System.out.println("Yes");
        else
            System.out.println("No");
    }

    private static boolean getRansom(int m, int n, String[] magazine, String[] ransom) {

        if(m < n)
            return false;

        Map<String, Long> magazineMap = getFrequencyMapFromArray(magazine); //Arrays.stream(magazine).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        Map<String, Long> 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) < ransomMap.get(key))
                return false;
        }

        return true;

    }

    private static Map<String, Long> getFrequencyMapFromArray(String[] arr) {

        Map<String, Long> 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 < m; magazine_i++) {
            magazine[magazine_i] = in.next();
        }
        String ransom[] = new String[n];
        for (int ransom_i = 0; ransom_i < n; ransom_i++) {
            ransom[ransom_i] = in.next();
        }

        if (getRansom(m, n, magazine, ransom))
            System.out.println("Yes");
        else
            System.out.println("No");
    }

    private static boolean getRansom(int m, int n, String[] magazine, String[] ransom) {

        if (m < n)
            return false;

        Map<String, Long> magazineMap = getFrequencyMapFromArray(magazine);
        Map<String, Long> ransomMap = getFrequencyMapFromArray(ransom);
        System.out.println(magazineMap);
        System.out.println(ransomMap);

        return (ransomMap.entrySet().stream()
                .filter(i -> (!magazineMap.containsKey(i.getKey()) || magazineMap.get(i.getKey()) < i.getValue()))
                .count() == 0);

    }

    private static Map<String, Long> getFrequencyMapFromArray(String[] arr) {

        return Arrays.stream(arr)
                     .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    }

}

Answer 1

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<String, Integer> 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.

Answer 2

After reviewing your Java-7 code, it seems that you have counted frequency of each word from magazine and ransom. Then, you are comparing frequencies of both hash map.

Well, this question can also be solved by using ArrayList instead of HashMap. Time complexity of hash map and array list is O(1) and O(n). I have solved this question by making array list of magazine. Then, I started to remove each element (from magazine array list) found in ransom array.

In your case, you are getting two new maps from getFrequencyMapFromArray() function. From my point of view, this can reduce the overall performance based on length of both (magazine and note) strings. ransom[] is almost same as maganize[]. So, you are creating two maps of almost equal length.

boolean flag = false;
List<String> ll = new ArrayList(Arrays.asList(magazine));

for(int i = 0; i < ransom.length; i++)
{
     if(ll.contains(ransom[i]))
     {
          ll.remove(ransom[i]);
     }
     else
     {
          flag = true;
          break;
     }
}

Answer 3

Assuming that the ransom note in general is smaller than the magazine, the way would be to have a frequency map of the ransom words only, and forget about a frequeny map of magazine words.

Rather walk the magazine words and when a word was found in the ransom words' frequency map, decrement the frequency, on reaching 0 remove the key.

So:

• Adding. Determine how many of which words are needed for the ransom note.
• Subtracting. Scratch those words reading the magazine words.
• Remains the ransom words not occurring in the magazine.

Should the frequency map become empty, you succeed. Otherwise at the end there is failure.

Several loops are imaginable, here one variant of computeIfPresent.

 Map<String, Long> ransomWords = getFrequencyMapFromArray(ransom);
 if (ransomWords.isEmpty()) {
     return true;
 }
 for (String magazineWord : magazine) {
     if (ransomWords.computeIfPresent(magazineWord,
             (w, freq) -> freq.longValue() == 1L ? null : freq - 1L) == null) {
         // Entry was removed...
         if (ransomWords.isEmpty()) {
             return true;
         }
     }
 }
 return false;

Answer 4

I solved it this way - I modified main method that hacker rank provided to not read all inputs for ransom note or store it - but break early if mismatch is found.

Also, there is no need to store magazine words in a String[], you can directly build map while reading input.

import java.util.*;


public class RansomNote {


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();

        boolean flag = true;

        Map<String,Long> magazineMap = new HashMap<>();
        for(int magazine_i=0; magazine_i < m; magazine_i++){
            magazineMap.merge(in.next(), 1L, Long::sum);
        }

        //Prepared only one map of magazines & not ransom words to to have memory efficiency 
        // Ransom note stoarge is not needed

        for(int ransom_i=0; ransom_i < n; ransom_i++){
            String ransomWord = in.next();

            if(!magazineMap.containsKey(ransomWord) || magazineMap.get(ransomWord) == 0) {
                flag = false;
                break;
            }else {
                Long newfrequency = magazineMap.get(ransomWord).longValue()-1L;
                magazineMap.put(ransomWord, newfrequency);
            }
        }



        if(flag)
            System.out.println("Yes");
        else 
            System.out.println("No");

        in.close();

    }
}