Code implemented with HashMap fails when tested with array of size 30K

Question

I am working on solving the code challenge from the link below but it fails from cases 13 to 19. I am reading that HashMap can take a large amount of data but my solution seems is not working for the cases when the array (magazine) is of 30K.

Below is the solution I implemented.

Help is appreciated.

https://www.hackerrank.com/challenges/ctci-ransom-note/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

I tested the code with arrays of 4K and it works fine

static void checkMagazine(String[] magazine, String[] note) {

    int initSize_m = (int) Math.ceil(magazine.length / 0.75);
    int initSize_n = (int) Math.ceil(note.length / 0.75);
    HashMap<Integer, String> m_hash= new HashMap<Integer, String>(initSize_m);
    HashMap<Integer, String> n_hash= new HashMap<Integer, String>(initSize_n);


    for(int i= 0; i < note.length; i++){
      n_hash.put(i, note[i]);
    }

    for(int i= 0; i < magazine.length; i++){
      m_hash.put(i, magazine[i]);
    }

    boolean flag=true;

    if(note.length<magazine.length){

    for (Map.Entry<Integer, String> entry : n_hash.entrySet()) {
        flag = m_hash.containsValue(entry.getValue());
        if(flag){
            m_hash.values().removeIf(v -> v.equals(entry.getValue()));
        }else{
            break;
        }
    }
    }else{

    for (Map.Entry<Integer, String> entry : m_hash.entrySet()) {
        flag = n_hash.containsValue(entry.getValue());
        if(flag){
            n_hash.values().removeIf(v -> v.equals(entry.getValue()));
        }else{
            break;
        }
    }
    }

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


}

Cases from 13 to 19 fail

Svetlin Zarev · Accepted Answer · 2019-09-10 05:32:06Z

2

Your maps should have the words as keys and their count as values. Mapping the words by their position in the input does not help you find them.

The whole point of a Map (also known as Dictionary) is to be able to quickly find a value by a given key. In the case of HashMap this operation is O(1), while finding a value by iterating all entry-values (as in your case) is much slower -> O(n). I strongly suggest that you read about maps and sets.

Here is a proper solution:

public class HackerRank {
    public static void main(String[] args) {
        final Scanner in = new Scanner(System.in);

        final int numberOfWordsInMagazine = in.nextInt();
        final int numberOfWordsInNote = in.nextInt();

        final Map<String, Integer> wordsInMagazine = new HashMap<>();
        for (int i = 0; i < numberOfWordsInMagazine; i++) {
            final String word = in.next();
            wordsInMagazine.merge(word, 1, Integer::sum);
        }


        boolean canPrintMessage = true;
        for (int i = 0; i < numberOfWordsInNote; i++) {
            final String word = in.next();

            Integer remainingCount = wordsInMagazine.computeIfPresent(word, (key, value) -> value - 1);
            if (null == remainingCount || remainingCount < 0) {
                canPrintMessage = false;
                break;
            }
        }

        System.out.println(canPrintMessage ? "Yes" : "No");
    }
}

edited Sep 10, 2019 at 5:32

answered Sep 10, 2019 at 4:35

Svetlin Zarev

15.8k4 gold badges60 silver badges89 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Erik Over a year ago

Worked flawlessly. Thanks for the push. My intention was to learn and I did.

Collectives™ on Stack Overflow

Code implemented with HashMap fails when tested with array of size 30K

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related