Monthly Archives: May 2013

Quick Sort: Algorithm and Complexity

After talking about Insertion sort and Heap sort, another important sorting algorithm is quick sort. It is pretty simple algorithm, and will be easy to understand using an example. Lets say we have this random array which we are trying to sort

9, 5, 7, 1, 2, 4, 3, 8, 6

Most critical step of quick sort is to select a pivot element from the array. There are multiple approaches to select the pivot like- first element, last element, mid element, random element, mean, median etc. For sake of simplicity, lets say we randomly select the pivot as 5 for first iteration. Once pivot is selected, the array is divided into 2 arrays, one with elements smaller than pivot and other greater

Iteration 1:

A1: 1, 2, 4, 3

P: 5

A2: 9, 7, 8, 6

In next iteration, one of the arrays (A1) is chosen and again a pivot (say 3) is selected. The same exercise is repeated of breaking down the array into 2 sub arrays unless we get an array of size 1. After that the arrays are merged recursively in same order as they were created, ending up into final sorted array.

Average & Best Case: If we take above case where we kept on dividing the problem array into half (N/2 then N/4, N/8 and so on), and hence halfing number of comparison in every next step. we are looking at a complexity of N Log N.

Worst Case: In worst case, lets say we select highest element every time. So instead of having half the elements in an array, we have N-1 elements in next step. So in this case we end up N*N (N Square) complexity

Web Service vs Web Application

There are times when I get confused if a web application is sufficient to solve a problem or I should be creating a web service. So I tried to get into depth of the two approaches.

What is a web application? web + application. A software application is something that is helping a user to achieve some specific goal, like MS Word, Calculator, Email Client etc. A web application, similarly, is an application which is available over a network or internet, it might be online banking application, some e-commerce application etc.

What is a web service? A service is similar to application in a sense that it is achieving a goal, but instead of being independent application, a service is providing inputs to some other application. For example, a service to add up two numbers, will take 2 numbers from a calculator app, add up two numbers, and return back to the calling applications.

Now how to take up the question if I should be creating a web application for a particular problem or web service. Let’s go back to calculator app, which needs a functionality to add 2 numbers. Web application approach will be to implement the add function inside the app, which is good enough if I know that this function is to be used only with this app. Web service approach will need the sum service to be independent of any application. This gives advantage that the same service can be used by multiple applications, this includes web apps, mobile apps or desktop apps as they will just need to connect to network and call the service to fulfill a requirement.

Above, we have defined web app and web service from a functional aspect. Technically, web service is a specialized web application only. A rule of thumb states that if your requirements want a user interface, you will need a web application implementation, but if your requirement does not need a interface but will return only some data, a web service is a good fit.

Heapsort: Algorithm and Complexity

Heap sort is one of the most important and interesting algorithms. The implementation is base of many other sophisticated algorithms. We will focus on basics of heap sorting here. Infact, if you understand what a heap data structure is, heap sort is just application of some known simple operations on the heap.

Let’s relook at our heap

heapsort

This is a max heap so let’s try to create an array in reverse sorted order (a min heap is good for sorted in lowest to highest format and vice versa).  Before moving forward, revisit the heap data structure and understand Insert and Delete operations, after that heap sort algorithm is a cake walk.

We know that max heap has a property that element at the top is highest. Using this property, we can create an algorithm like

  1. Create max heap from the random array
  2. Remove top element from heap and add to reverse sorted array
  3. Heapify (restore heap property) the remaining heap elements
  4. Repeat Step 2 till the heap is empty

Step 1 is nothing but inserting all elements of an array to heap. One Insert Key operation takes Log N operations so N elements will take N Log N

Step 2 is order of 1 as we are just removing the top element and adding to our array

Step 3 is nothing but Delete Node operation in heap, i.e.  take last leaf node and add as root, then compare with its child nodes and swap with largest. Repeat the process till heap property is maintained, i.e. child is greater than parent.  This is Log N operations for one heapify.

Step 4 is combination of 2 & 3, N times. Step 2 is constant order and hence can be ignored. This means we have N Step 3 order or N Log N.

Combining Step 1 and 4, we figure out order of heap sort complexity is of  N Log N order.

Related: http://kamalmeet.com/2013/05/heap-data-structure/

http://kamalmeet.com/2011/07/insertion-sorting/

Java multiple Inheritance: Interfaces and Composition

Inheritance means a class extending other class. Multiple Inheritance means single class extending more than one class. Java does not support this kind of inheritance as one class can inherit only a single class.

Q. Why Java does not support multiple inheritance?

Consider a scenario, there are 2 classes

class A{

public void mymethod(){//some code

}

}

class B{

public void mymethod(){//some code

}

}

class C extends A,B{//illegal in Java

//which implementation of mymethod is imported ?

}

If java allow multiple inheritance, it will be tricky to handle above situation with multiple inheritance, hence Java does not allow it.

Q. How does Java implement Multiple inheritance?

Java does not provide direct implementation of multiple inheritance by extending more than one classes, but it provides you 2 alternatives.

1. Use of Interfaces: A Java class cannot extend more than one class, but it can implement any number of interfaces.

Class C implements A,B{ // this time A and B are interface

public void mymethod(){//interfaces did not provide implementation and hence no conflict

}

}

2. Composition: Other way to use properties of other classes is to use composition, that is have the object of other classes as part of current class.

Class C{//A and B are different classes

A objA=new A();

B objB=new B();

}

Best Approach: A mix of implementing interfaces, extending class and using composition, based on different requirements

Heap Data Structure

Understanding of Heap data structure is very important as it is part of many other data structures like priority queue and algorithms like priority queues, Dijkstra’s.

Let’s understand Heap data structure first. Heap is a simple tree based data structure with a unique property that root node is always larger or smaller than its children.

heapsort

In the current heap we can see parent element is always higher than child nodes, hence it is called max heap. Similarly in case the parent is smaller than children, it will be min heap. Also the heap shown above is binary heap as each parent node has only two child nodes.

Let’s talk about efficiency of the heap data structure in terms of Inserting and deleting the nodes.

Insert a Key: To insert a new node, new element is added to next possible leaf node. It is then compared to its parent node and moved up if larger.

1. Insert node at next leaf

2. While element is less than parent

Swap child and parent

 

Insert operation in a heap data structure is order of log N, where N is number of nodes available.

Delete Node: Deletion always occur at the root node. Last leaf node is moved to root and then moved down till it is greater than children.

1. Node =root

2. While node <any child

Swap node and largest child

Delete operation in a heap data structure is order of log N, where N is number of nodes available.

Stored procedure Vs SQL in code

Originally Posted December 24, 2007

The debate is old. But every now and then, we have to make a decision between using stored procedures and writing sql queries in code. When you are implementing sql queries for your database, you can either write them down in your code (again you can have different layers in your code and you can decide where to implement your sql queries, but that is different topic) or you can store them in database itself as stored procedures.

There are two schools of thoughts, one that will recommend going for stored procedure and the second will propose no stored procedures approach. I tried to understand the difference between the two approaches.

What is a stored procedure for a database? It is same as any procedure you create in your coding language, that takes some arguments, apply some logic, execute and returns back a result (if required).

As I already mentioned the debate is really old, so instead of reinventing the wheel, I will borrow the pointers from different sources and then try to add my thoughts to that

Stored procedures are secure: Stored procedure are secured against SQL injections. Are they totally safe? Isn’t it again the responsibility of person creating the procedure to make sure it is safe. Again, if I am writing queries in application layer (code), I can make sure the code is protected against the attacks.

Separation of data logic from business logic: All your queries which are interacting with database are residing over the database engine itself. This clearly separates all database interactions and hence make design more cleaner. One alternative will be to divide yourapplication layer into different parts, and keep data handling part completely separate from the rest.

A Disadvantage: Moving stored procedure from one platform to another can be tough, eg you decided to move from MSSQL to MYSQL, you may have recode all your stored porcedures. But this has a related advantage that if the front end language is changing, say you are moving from php to java, and your database is not changing then you don???t need to change the stored procedures.

Testing the app: Testing application with stored procedures can be a pain. Yes, as the changes are to be made in multiple places, your code as well as stored procedure. Now if database is handled by a different team, every time for a small change you have to communicate the changes and then test. This will take longer time than making changes just in your code as multiple teams are involved.

Stored procedure is faster: now that is debatable statement. I found this thing mentioned at many places that stored procedures as faster as the procedure is part of database engine itself and hence have faster access to database. Also you don’t need to send the complete query but just the procedure name. But as per my exp, I never faced any differences in terms of execution time with stored procedure.

Having considered all the points above, my personal opinion would be not to use the stored procedures especially in big application and if the same database is being used by multiple applications, because you don’t have complete control over the database and every time a change is made to a procedure it has to be communicated to multiple parties. In small applications and small teams one can use stored procedures as mostly same team has control of both database engine and code layer, so it is easier to coordinate and implement the changes.

http://codebetter.com/blogs/eric.wise/archive/2006/05/24/145393.aspx
http://www.tonymarston.net/php-mysql/stored-procedures-are-evil.html
http://codebetter.com/blogs/jeremy.miller/archive/2006/05/25/145450.aspx

AJAX with Java

As a major requirement for AJAX application from server side language is to retrieve the request from client side and then parse it based on the format of the request. The request can be in form of a simple string, or XML, or JSON. And similarly the AJAX application expects a response back from server in one of these formats. Java can fulfill these requirements easily.

As for the first part, the server side language needs to accept the request from AJAX application in client side. Now Java has multiple ways to accept the request like JSPs, Servlets, Struts, JSFs etc. lets take a Servlet example

Public void doGet(HttpServletRequest req, HttpServletResponse res)
{
String ajaxData=req.getParameter(“Data”);
String returnString = executeAJAXRequest(ajaxData);
res.setContentType(“text/xml”);
res.getWriter.write(returnString);
}

Above one is a simple example. I left some of the details on purpose. Like what is executeAJAXRequest method doing. This will actually depend on the kind of request we receive.

The request might be a text based one where we don’t need to do any special parsing.

String executeAJAXRequest(String name)
{
String helloString= “Hello “+name;
return helloString;
}

That’s just a simple example; we could be doing some database operations in the method based on the name we got. But the idea is that the data is being used as it is. If it was a number say employee number we would convert to long and use.

Now if the data is in XML format. We already know that Java has strong XML support. It can parse and create XML documents easily using either DOM or SAX parsers. The following example shows how to parse data (uses apache’s xerces library)

ajaxRequest=”<employees><employee><name>John</name></employee></employees>”;

ArrayList executeAJAXRequest(String ajaxRequest)
{
ArrayList<String> nameValueArray=new ArrayList<String>(10);
try
{
DOMParser parser = new DOMParser();

parser.parse(new org.xml.sax.InputSource(new java.io.StringReader(ajaxRequest)));
DocumentImpl document = (DocumentImpl)parser.getDocument();

//get the root of the XML document
Node root = document.getFirstChild();
NodeList childNodes=root.getChildNodes();

for(int i=0;i<childNodes.getLength();i++)
{
nameValueArray.add(i, childNodes.item(i).getFirstChild().getFirstChild().getNodeValue());
}
}
catch (SAXException e)
{
e.printStackTrace();
//handle exception
}
catch(IOException e)
{
e.printStackTrace();
//handle exception
}

return nameValueArray;
}

The third way to pass data from client to server and vice versa is by using JSON. There are many libraries available in Java to parse and create JSON strings. Here is an example of code parsing a JSON String from client side using json-simple library (http://code.google.com/p/json-simple )

JSON string received from client is something like “{\”Employee\”: [{\”name\”: \”Eric\”, \”EmployeeNum\”: \”1232\”, \”Designation\”: \”SE\”}]}”

void executeAJAXRequest(String ajaxRequest)
{
JSONParser jsonParser = new JSONParser();
ContainerFactory containerFactory = new ContainerFactory(){

public List creatArrayContainer() {
//Add Details if required
return null;
}

public Map createObjectContainer() {
//Add Details if required
return null;
}
};

try{
Map jsonMap1 = (Map)jsonParser.parse(ajaxRequest, containerFactory);

Iterator iter1 = jsonMap1.entrySet().iterator();
while(iter1.hasNext()){
Map.Entry entry1 = (Map.Entry)iter1.next();
String valueString=entry1.getValue().toString();
String dataString=valueString.substring(1,valueString.length()-1);

Map jsonMap2 = (Map)jsonParser.parse(dataString, containerFactory);

Iterator iter2 = jsonMap2.entrySet().iterator();
System.out.println(“Here are the Employee Details”);
while(iter2.hasNext()){
Map.Entry entry2 = (Map.Entry)iter2.next();
System.out.println(entry2.getKey() + “=>” + entry2.getValue());
}
}

}
catch(ParseException pe){
System.out.println(pe);
}
}