Thursday, 27 July 2017

CTCI Challange, DAY 3

Day 3:-
Problem Statement:- Hash Tables: Ransom Note

Todays problem is on hashtables(maps).
The problem was very easy,wrote it on paper with in 11 min,n coded in system.This time I maintained modularity and naming conventions.
Was able to derive at the correct solution in 4th iteration.
I tested with edge case scenarios as told by gayle in 7 step approach,yes it helped in identifying the issues quickly.

On Paper:-




import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Ransom_Note {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        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();
        }
        System.out.println(isRansomNotePossible(magazine, ransom));
    }

    private static String isRansomNotePossible(String[] magazine, String[] ransom) {
        Map<String, Integer> mgz_map = new HashMap<>();
        Map<String, Integer> rnsm_map = new HashMap<>();

        for (int i = 0; i < magazine.length; i++) {
            if (mgz_map.containsKey(magazine[i])) {
                int val = mgz_map.get(magazine[i]);
                mgz_map.put(magazine[i], ++val);
            } else {
                mgz_map.put(magazine[i], 1);
            }
        }
        for (int i = 0; i < ransom.length; i++) {
            if (rnsm_map.containsKey(ransom[i])) {
                int val = rnsm_map.get(ransom[i]);
                rnsm_map.put(ransom[i], ++val);
            } else {
                rnsm_map.put(ransom[i], 1);
            }
        }

        String result = "Yes";
        for (String key : rnsm_map.keySet()
                ) {
            if (!mgz_map.containsKey(key)) {
                result = "No";
                break;
            } else if (mgz_map.containsKey(key) && rnsm_map.get(key) > mgz_map.get(key)) {
                result = "No";
                break;
            }
        }
        return result;
    }
}

Mistakes:-
I tried to iterate over mgz.map contents but there's a possibility that rnsm_map can contain values other than mgz_map values.So I interchanged it.

No comments:

Post a Comment

Installing Docker and Minikube

  install docker-   sudo apt install docker.io   set user to docker group:- sudo gpasswd -a   {user} docker   imp commands:- ...