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 :-)

Improve performance of JAX-WS

JAX-WS comes with JaXB. The raw SOAP packet does not come to the web service consumer, instead they get unmarshalled to the Java Objects by the JAX-WS runtime engines.
Lot of time it is however better not to convert the payload of the SOAP packet i.e. the XML to the java objects. Think of a situation where we are getting one XML and we are going to use that XML to another web service. This happens in case of SOA environment, where we talk to one web service, get some data and we pass that to another web service. If we are converting the received XML to another XML only then we should try to avoid the JAXB layer.
Lets consider the steps involved if we have the JAXB layer -

Response SOAP --> Response Object --> transferred to another object --> Send to another Web Service

Instead if we remove the XML to Object layer, it becomes -

Response SOAP --> XSLT transfer to another XML format and send to another web service. This is faster, only pain point is - we need to work with RAW XML like using StaX API instead of using the Objects of JaXB.

DAO layer in J2EE Apps

Phew.... its been a crazy time. There was a product release and things were pretty hectic. Hence did not get time to write anything on the post. Now that the Chrismas vacation is here, need to spend time with family also :-)

Anyway, I thought of writing this post on Data Access Layer of J2EE. How many times we write DAO layers yet we dont get it right at the first time. I was reviewing some of the codes and found out that people do not understand why they are writing a DAO and just write it cause its mentioned somewhere that it is a good practice.

okay, so as we all know that we introduce DAO layer to abstract the data access layer. For example, if your application runs on MySQL, SQL Server, Sybase and Oracle, the DAO developer makes sure that he introduces a nice abstraction layer which hides all of these database related differences. The client code of DAO - which is many times the Session Facade or Value List Handers, do not have to worry about loading the JDBC driver and creating DB specific SQLs.
Doing so, DAO layer needs to make sure that it opens a connection with database, prepare statement object, create resultset , retrieve data and close the connection and resultset. Closing the connection and resultset are important otherwise you will have leaked cursors at the database layer. It is also important to make sure DAO layer catches all the JDBC/SQL specific exceptions and convert them to application specific exceptions. Lot of DAO developers do not handle the exceptions from the DAO layer which defets the purpose of having another layer. The idea is that any code which is going to use the DAO, should not have to use java.sql.* or javax.sql.* packages at all.
There are many ways to create a DAO layer, if we refer to the Suns J2EE blueprint site -
http://java.sun.com/blueprints/corej2eepatterns/Patterns/DataAccessObject.html

Evolution from Inheritance to Composition to Dependecy Injection (Inversion of Control)

Inheritance and compositions are the most basic concepts of Object Oriented design. If there is a is-a relationship between objects, we tend to use inheritance and if there is a has-a relationship, we tend to use compositions. For example, Manager is a Employee, so Manager will be a sub-class of Employee. Otherwise, Machine has disks, so Machine object can contain many Disk objects following Composition.
It is a usual practice to follow more of Composition rather than inheriance. Reason is - composition allows loose coupling than Inheriance. In case of Inheritance, any change is super-class methods can break the client code which are using the super-class or any of its sub-classes. Whereas in case of composition, any change in the back-end class (the class that is encapsulated within another class) might not lead to changes to the client code which uses the front-end class (the class that encapsulates the back-end class).
Hence when we develop enterprise applications, we develop complex class maps where one class holds refernece of many other classes. The problem is the front end class needs to explicitely get a hold of the back-end class. For example, class A has-a Class B. In that case, we can find some code like

Class A{
private B b;
A()
{
B b = new B():
}

....

Now it becomes a problem for class A sometimes to get these references of its composite classes. Think about Class A as one EJB bean which is going to class another EJB bean B. In that case, A needs to look for B's home interface from JNDI. Or think of B's reference is available in JNDI (like B is a JDBC Datasource), in that case also A needs to look for the reference of B from JNDI.

Instead of class A, getting the reference of Class B explicitely, if some framework can inject or set the reference of class B in class A, that becomes very easy. As a result class A can concentrate on other activities. This is called "Dependency injection" (previously known as Inversion of Control). Spring framework make use of this concept very much. Even EJB 3 uses dependecny injection to inject EJB references or Persistence Contexts. Dependency injection of these frameworks can really help developers to develop cleaner code.