Find the frequency of a word in a book

Design a method to find the frequency of occurrences of any given word in a book.

My initial thoughts:
Assume this query would be asked for multiple times. Otherwise, if it’s a one-time thing, we can do no better than scanning through the book. We then need to build a Trie with nodes as character along with its count. When asked for particular word, we search through the tree.

My initial codes:

	public class Node {
		private char c;
		private int count = 1;
		private List<Node> children = new LinkedList<Node>();

		public Node() {

		}

		public Node(char c) {
			this.c = c;
		}

		public char getC() {
			return c;
		}

		public void setC(char c) {
			this.c = c;
		}

		public int getCount() {
			return count;
		}

		public void setCount(int count) {
			this.count = count;
		}

		public void increaseCount() {
			this.count++;
		}

		public List<Node> getChildren() {
			return children;
		}

		public Node addChild(char c) {
			for (Node node : children) {
				if (node.getC() == c) {
					node.increaseCount();
					return node;
				}
			}
			Node child = new Node(c);
			this.children.add(child);
			return child;
		}

		public Node getChild(char c) {
			for (Node node : children) {
				if (node.getC() == c) {
					return node;
				}
			}
			return null;
		}

		@Override
		public String toString() {
			return "(" + c + ", " + count + ")";
		}
	}

	private Node root = new Node();

	public void buildTree(String[] book) {
		for (String word : book) {
			Node current = root;
			for (int i = 0; i < word.length(); ++i) {
				char c = word.charAt(i);
				current = current.addChild(c);
			}
		}
	}

	public int getFrequency(String word) {
		Node current = root;
		for (int i = 0; i < word.length(); ++i) {
			char c = word.charAt(i);
			current = current.getChild(c);
			if (current == null)
				return 0;
		}
		return current.getCount();
	}

Solution:

	Hashtable<String, Integer> setupDictionary(String[] book) {
		Hashtable<String, Integer> table = new Hashtable<String, Integer>();
		for (String word : book) {
			word = word.toLowerCase();
			if (word.trim() != "") {
				if (!table.containsKey(word))
					table.put(word, 0);
				table.put(word, table.get(word) + 1);
			}
		}
		return table;
	}

	int getFrequency(Hashtable<String, Integer> table, String word) {
		if (table == null || word == null)
			return -1;
		word = word.toLowerCase();
		if (table.containsKey(word)) {
			return table.get(word);
		}
		return 0;
	}

Comments: Error conditions:

  1. Trim and toUpperCase the word before inserting into hashtable.
  2. Error condition for table==null and/or query==null.
  3. toUpperCase the query before searching through hashtable.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: