8
\$\begingroup\$

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()));
    }

}
\$\endgroup\$
  • \$\begingroup\$ Java8 getRansom could use anyMatch(): return !ransomMap.entrySet().stream() .anyMatch( i -> (!magazineMap.containsKey(i.getKey()) || magazineMap.get(i.getKey()) < i.getValue())); \$\endgroup\$ – RobAu Apr 5 '17 at 7:11
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. The suggestions provided by you are amazing. However, I have a couple of questions. 1) In Java-8 when you create a frequency map using Collectors.counting(), it automatically creates it has a Long. So is there a way to have it as an integer there itself? \$\endgroup\$ – Amriteya Apr 5 '17 at 12:27
  • 1
    \$\begingroup\$ 2) In the efficiency approach that you suggested, if I do not create a ransomFrequencyMap, I'll have to keep altering magazineFrequencyMap to reduce the frequency every time a String from ransom array is available in magazineFrequencyMap. I don't know how to concurrently alter the map while using streams. Is that even possible? Could you show it in an example? \$\endgroup\$ – Amriteya Apr 5 '17 at 12:28
  • \$\begingroup\$ Ah sorry, I'm still used to java 6 actually so I silently ignored the java 8 streams since I'm not used to those at all. If the return type of the method is of type Long then you should just keep it as a Long, the remark was more about your java 7 solution where you have the choice. About the concurrent stream: again sorry, I assumed it wouldn't be concurrent so this wasn't a problem for me. If you need concurrency perhaps someone else can post an answer to optimise for that criteria? (this fits nicely in my remark about when a solution is the best one) \$\endgroup\$ – Imus Apr 5 '17 at 14:42
  • \$\begingroup\$ @Amriteya Check out ConcurrentHashMap This may do what you need with streams \$\endgroup\$ – Gary99 Apr 7 '17 at 1:24
  • \$\begingroup\$ @Gary99 could you elaborate with a code example how ConcurrentHashMap will help in this case? \$\endgroup\$ – Amriteya Apr 7 '17 at 6:26
2
\$\begingroup\$

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;
     }
}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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;
| improve this answer | |
\$\endgroup\$
-1
\$\begingroup\$

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();

    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. Please read How do I write a good answer?: "Every answer must make at least one insightful observation about the code in the question. Answers that merely provide an alternate solution with no explanation or justification do not constitute valid Code Review" \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Feb 14 '18 at 14:21
  • \$\begingroup\$ Thanks for the comment, I am new to review site even though I have been on SO for long. Looks like, I misunderstood purpose here. \$\endgroup\$ – Sabir Khan Feb 14 '18 at 14:29

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.