We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Hash Tables: Ransom Note
  2. Discussions

Hash Tables: Ransom Note

  • nikolaspavlakis
     + 2 comments

    Your solution "pays" O(nlogn) time in order to do the (unnecessary) sorting. Yes, it is simple and sometimes simplicity is preferred to performance. Yet, in an interview, you need to at least make clear to your interviewer that you are doing this in favor of simplicity and that you know that it is not the optimal solution.

    Here is a Java 8 approach:

    Scanner in = new Scanner(System.in);
int m = in.nextInt();
int n = in.nextInt();
HashMap<String, Integer> magazine = new HashMap<>();
for (int i = 0; i < m; i++) {
    String word = in.next();
    magazine.put(word, magazine.getOrDefault(word, 0) + 1);
}
HashMap<String, Integer> ransom = new HashMap<>();
for (int i = 0; i < n; i++) {
    String word = in.next();
    ransom.put(word, ransom.getOrDefault(word, 0) + 1);
}

Optional<Integer> res = ransom.entrySet().stream()
.map(e -> magazine.getOrDefault(e.getKey(), 0) - e.getValue())
.filter(e -> e < 0)
.findFirst();

System.out.println(res.isPresent() ? "No" : "Yes");