Trie in Java

Trie is a good datastucture, details can be found here - http://en.wikipedia.org/wiki/Trie . I came across Trie while performing "Prefix" based searching. Have you ever Wondered what Data Structure is used behind the Mobile SMSes ? When we type SMS, it finishes the words or proposes what could be the end of the word. They are usually done by Trie or data structures like Trie.
Trie consumes less space so they are hot favourite data structures on PDAs or devices with less memory. Searching of a string in Trie takes around O(m) where m = length of the key. Compare it with Binary Tree which is O(logn) where n = number of elements in the tree. For a dictionary, this n could be real large.

Here is a simple implimentation of the Trie..
One class is called Node class which holds the Key and the value.

1. public class Node {




3. private char key;


4. private String value;


5. private List children;


6. private boolean isTerminal;


7. public boolean isTerminal() {


8. return isTerminal;


9. }


10. public void setTerminal(boolean isTerminal) {


11. this.isTerminal = isTerminal;


12. }


13. public Node(char key,String value)


14. {


15. this(key,value,new ArrayList());


16. }


17. public Node(char key, String value, List children) {


18. super();


19. this.key = key;


20. this.value = value;


21. this.children = children;


22. }




24. public char getKey() {


25. return key;


26. }


27. public void setKey(char key) {


28. this.key = key;


29. }


30. public String getValue() {


31. return value;


32. }


33. public void setValue(String value) {


34. this.value = value;


35. }


36. public List getChildren() {


37. return children;


38. }


39. public void setChildren(List children) {


40. this.children = children;


41. }




43. public void addChildren(Node child)


44. {


45. this.children.add(child);


46. }

}

And the Main Trie class which builds the tree and finds any key...

package com.ds.trie;

1. import java.io.BufferedReader;


2. import java.io.File;


3. import java.io.FileNotFoundException;


4. import java.io.FileReader;


5. import java.io.IOException;


6. import java.util.ArrayList;


7. import java.util.LinkedList;


8. import java.util.List;


9. import java.util.Queue;




11. public class Trie {




13. private Node root;


14. private File fname;




16. public Trie (String filename)


17. {


18. this.root = new Node('r',"root");


19. this.fname = new File(filename);


20. }




22. public void buildTrie()


23. {


24. try {




26. if (!fname.isFile())


27. throw new FileNotFoundException("");


28. BufferedReader f = new BufferedReader(new FileReader(fname));


29. String key;


30. try {


31. while ((key = f.readLine()) != null)


32. {


33. // making value = full name only = key


34. build(key,root,key);


35. }


36. } catch (IOException e) {


37. // TODO Auto-generated catch block


38. e.printStackTrace();


39. }


40. } catch (FileNotFoundException e) {


41. // TODO Auto-generated catch block


42. e.printStackTrace();


43. }


44. }




46. // key = shamik


47. private void build(String key,Node root,String value) {


48. // TODO Auto-generated method stub


49. char c = key.charAt(0); // c = s


50. String tail = null;


51. if (key.length() > 1)


52. tail = key.substring(1); // hamik


53. Node resultNode = findKeyinChildren(root,c); // find 's' in the children


54. if (resultNode == null)


55. {


56. // this is a new key


57. Node newNode = new Node(c,value);


58. if (tail == null)


59. newNode.setTerminal(true);


60. else


61. newNode.setTerminal(false);




63. root.addChildren(newNode);


64. if (tail == null)


65. {


66. return;


67. }


68. else


69. build(tail,newNode,value);


70. }


71. else // got the key - s


72. {


73. if (tail == null)


74. return;


75. build (tail,resultNode,value);


76. }


77. }




79. private Node findKeyinChildren(Node root, char c) {


80. // TODO Auto-generated method stub


81. List list = root.getChildren();


82. if (list == null || list.size() == 0)


83. return null;


84. for (int i=0; i < list.size(); i++)


85. {


86. Node oneNode = list.get(i);


87. if (oneNode.getKey() == c)


88. return oneNode;


89. }


90. return null;


91. }




93. public List findKey(String key)


94. {




96. String value = null;


97. List values = new ArrayList();




99. Node resultNode = findinTrie(key,root);




101. if (resultNode == null)


102. {


103. value = "Not found";


104. values.add(value);




106. }


107. else


108. {




110. printTree(resultNode,values);




112. }


113. return values;




115. }




117. private void printTree(Node resultNode,List values) {


118. // TODO Auto-generated method stub


119. List list = resultNode.getChildren();




121. if (resultNode.isTerminal())


122. values.add(resultNode.getValue());




124. if (list.size() == 0)


125. {




127. return;




129. }


130. else


131. {


132. for (int i=0; i<list.size();i++)


133. {


134. Node oneNode = list.get(i);


135. printTree(oneNode,values);


136. }


137. }


138. }




140. private Node findinTrie(String key, Node root) {


141. // TODO Auto-generated method stub


142. // Implementing the Breath First Traversal


143. char first = key.charAt(0);


144. String tail = null;


145. if (key.length() > 1)


146. tail = key.substring(1);




148. Node resultNode = this.findKeyinChildren(root, first);


149. if (resultNode == null)


150. {


151. return null;


152. }


153. else


154. {


155. if (tail == null)


156. return resultNode;


157. else


158. resultNode = findinTrie(tail,resultNode );


159. }




161. return resultNode;


162. }




164. public static void main(String[] args)


165. {


166. if (args.length <= 0)


167. {


168. System.out.println("Usage : Trie ");


169. System.exit(1);


170. }


171. Trie trie = new Trie("C:\\test\\dictionary");


172. trie.buildTrie();


173. System.out.println("Going to look for " + args[0]);


174. List vals = trie.findKey(args[0]);


175. for (int i=0; i<vals.size(); i++)


176. {


177. System.out.println("possible value = " + vals.get(i));


178. }




180. }




182. }

Job Interview Question Part 2

For a tree, find out the largest possible value from the root to the leaf.

private int maxResult = 0;

public int findMaxRoot(Node root)
{
int result = root.getValue();

List nodes = root.getChilds();
if (nodes.size() == 0)
{

return result;
}
else
{

int maxChildTreeValue = 0;
for (int i=0; i {
//result = root.getValue();
Node oneNode = nodes.get(i);

result = findMaxRoot(oneNode);
if (result > maxChildTreeValue)
maxChildTreeValue = result;


}

result = maxChildTreeValue + root.getValue();

if (result > maxResult)
{
maxResult = result;

}
//maxResult = maxResult + root.getValue();


}
return maxResult;
}

Job interview question Part 1

public static int getCountOfOnes(int n) {
/*
Please implement this method to
return the number of '1's in the binary representation of n
for any integer n, where n > 0

Example: for n=6 the binary representation is '110' and the
number of '1's in that
representation is 2

*/
int count = 0;
int a = 1;

for (int i=1 ; i < 31; i++)
{
int val = n & a ;
if (val > 0 )
count++;
a = a << 1;
}

return count;
}


This is an ideal question to find out whether the developer is aware of bitwise operators ... logic is to perform bitwise and and see the value. If the value if more than 0, then that position contains 1.
Example 6 = 110
Perfor bitwise & with 1, result is 110 & 001 = 0 so there is no 1 at this position
bitwise & with 2 (10), result is 110 & 010 = 010 so there is one 1 at the second positions etc..

Java Vs C++ an analogy

I think any C++ developer tend to think when they move to Java - what they gained and what they lost. I was thinking about Java Vs C++ in terms of memory management and this thought came to my mind. I would like to describe that - working in C++ as if you are preparing food at home vs working in Java is as if you are having your food at a restaurant.
The difference between java and c++ comes clear if we think of having food at a restaurant vs preparing and having food at home. When we have food at restaurant we do not worry about where from the plates are coming (think of who allocates the memory) and who will wash them after having food (think of who frees the memory). So the good think of working in Java or having food at restaurants is that we are free from some house hold activities which are otherwise boring and error prone.
But the actual strength of preparing food at home is that - we can do anything with the food. It all depends upon us to determine how much salt or pepper we need to use in the food. Compared it with having food at restaurant where we have little control over the ingredients of the food (of course I am not referring to open kitchen style of restaurants).
So C++ might still be stronger than Java as there are more freedom given to the developer as what he wants to do - but the developer should be pretty good in it otherwise go out for dinner :-)