Hash Tables : Ransom Note

I randomly selected the Hash Tables: Ransom Note challenge.

Before starting to work on the challenge I noticed a video clip and a Hashing link. I watched the video which was directed to technical interviews and read the document “Hashing” by AllisonP. Hash tables typically are treated as full chapters in algorithms books. Their use is part of several implementations of other types of objects.

The following paragraph provides context to the challenge:

“A kidnapper wrote a ransom note but is worried it will be traced back to him. He found a magazine and wants to know if he can cut out whole words from it and use them to create an untraceable replica of his ransom note”.

This implies that words in the magazine cannot be used more times in the ransom note than they appear in the magazine.

Following is a screen capture of the Eclipse IDE console using the sample data provided by the challenge:

6 4
give me one grand today night
give one grand today
Yes

The second sample data is illustrated in the following screen capture:

6 5
two times three is not four
two times two is four
No

Following is an actual test case which is part of the discussions:

15 17
o l x imjaw bee khmla v o v o imjaw l khmla imjaw x
imjaw l khmla x imjaw o l l o khmla v bee o o imjaw imjaw o
No

This last one does not work for the ransom note because it uses words (e.g., o) more times that it is available in the magazine :o(

The Java code for my solution and test code follows:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;

public class Solution {

	/**
	 * Check if we have sufficient words in the magazine for the ransom note.
	 */
	static String sufficientWords(String[] magazine, String[] ransom) {

		// **** build magazine map ****
		
		HashMap<String, Integer> magMap = new HashMap<String, Integer>();
		
		for (String word : magazine) {
			if (magMap.containsKey(word)) {
				int count = magMap.get(word);
				count++;
				magMap.put(word,  count);
			} else {
				magMap.put(word, 1);
			}
		}

		// **** build ransom map ****
		
		HashMap<String, Integer> ransomMap = new HashMap<String, Integer>();
		
		for (String word : ransom) {
			if (ransomMap.containsKey(word)) {
				int count = ransomMap.get(word);
				count++;
				ransomMap.put(word, count);
			} else {
				ransomMap.put(word, 1);
			}
		}
		
		// **** compare words and counts ****
		
		Iterator iter = ransomMap.entrySet().iterator();
		
		while (iter.hasNext()) {
			
			// **** ****
			
			Map.Entry<String, Integer> pair = (Map.Entry<String, Integer>)iter.next();
			String word = pair.getKey();
			int count 	= pair.getValue();
			
			// **** ****
			
			if (!magMap.containsKey(word)) {
				return "No";
			} else {
				if (count > magMap.get(word)) {
					return "No";
				}
			}
		}

		// **** we have enough words ****
		
		return "Yes";
	}

	/**
	 * Test code.
	 */
	public static void main(String[] args) {

		// **** open scanner ****
		
        Scanner in 	= new Scanner(System.in);
        
        // **** read parameters ****
        
        int m 		= in.nextInt();
        int n 		= in.nextInt();
        
        // **** read words from the magazine ****
        
        String magazine[] = new String[m];
        for (int i = 0; i < m; i++){
            magazine[i] = in.next();
        }
        
        // **** read words for ransom note ****
        
        String ransom[] = new String[n];
        for(int i = 0; i < n; i++){
            ransom[i] = in.next();
        }
		
        // **** close scanner ****
        
        in.close();
        
        // **** determine if there are sufficient words for the ransom note ****
        
        System.out.println(sufficientWords(magazine, ransom));
	}
}

The approach is to first build a map of words available in the magazine with their frequencies. The second step is to build a map of the words needed in the ransom note with their associated frequencies. The last step is to iterate through the words in the ransom note checking that they are available in with the associated counts.

Sorry if this code is too much for you. I personally like simple, documented and easy to understand code. Keep in mind that you or other engineers will have to maintain and enhance while the product is available for users.

The code passed all 20 test cases.

If you have comments or questions regarding this or any other post in this blog please do not hesitate and send me a message.

Enjoy;

John

Follow me on Twitter:  @john_canessa