Open-Closed principle Revisited

Reference: http://kamalmeet.com/system-design-and-documentation/understanding-openclosed-principle/

Open closed principle states that your classes should be open for extension but closed for modification. One way to look at it is that when you provide a library or a jar file to a system, you can ofcourse use the classes or extend the classes, but you cannot get into the code and update it.

At a principle level, this means you should code in a manner that you never need to update your class once code. One major reason behind this principle is that you have a class which is reviewed and Unit tested, you would not like someone to modify and possibly corrupt the code.

How do I make sure that my class follow open closed principle?

Let’s look at a design of this MyPizza class

public class MyPizza {
public void createPizza(Pizza pizza)
{
if(pizza.type.equals("Cheese"))
{
//create a cheese pizza
}
else if(pizza.type.equals("Veg"))
{
//create a veg pizza
}
}
}

Following pizza type classes use this

class Pizza
{
String type;
}

class CheesePizza extends Pizza{
CheesePizza()
{
this.type=”Cheese”;
}
}

class VegPizza extends Pizza{
VegPizza()
{
this.type=”Veg”;
}
}

The above design clearly violates the open closed principle. What if I need to add a double cheese pizza here. I will have to go to MyPizza class and update it, which is not following “closed for modification” rule.

How can fix this design?

public class MyPizza {
public void createPizza(Pizza pizza)
{
pizza.create();
}
}


class CheesePizza extends Pizza{
CheesePizza()
{
this.type="Cheese";
}

public void create()
{
//do the creation here
}
}

With this simple modification we are making sure that we will need not change the code in MyPizza class even when we will add new types of pizza, as actual responsibility of creation would be with the new class being created (DoubleCheese).

Reverse Engineering: MySQL WorkBench

In last post I talked about creating sequence diagrams using MaintainJ. Another important aspect you would want to understand for a Project is the database schema design. How many tables are there? How do they interact with each other? etc.

For understanding this design the best way is to look into ER or Entity Relationship diagram. Ideally one would create the ER diagram first and then implement database.

In case we do not have a ER diagram available we can create using Reverse Engineering the database to ER diagram.

For MySQL, we can use MySQL WorkBench tool to create one.

Download the installer from https://www.mysql.com/products/workbench/

Once installed, you can connect to you mysql database in workbench. Then in Database Tab at the top, select Reverse Engineer option, and select the schema you want to reverse engineer.

Reverse Engineering: MaintainJ

The best way to analyze the code with hundred of Java classes is to look into the documentation, class diagrams, sequence diagrams etc to understand the flow and usage. Unfortunately there are times when you would not be provided with any such documentation.

Reverse Engineering tools can be of help upto some level. MaintainJ is one such tool to help you with Java.

So if you have a working codebase for a web application, which you need to analyze, here are the steps to go ahead.

1. Download the MaintainJ war file from http://maintainj.com/userGuide.jsp?param=install
2. Add the war file to the server where main application (to be analyzed is available), for example if you project war file is added to tomcat – tomcat/webapps, add the MaintainJ.war
3. Now if you will visit the link to server like http://localhost:8080/MaintainJ/, it will let you provide the package to be traced and directory where output file to be added.
4. It will provide simple settings to be added to catalina.sh (or other server config),
5. Once all settings done, restart the server.
6. Go to MaintainJ link and start tracing.
7. Now browse through the actual app, MaintainJ will create sequence diagrams to the directory where you have provided the path.

You can view the ser file created by MaintainJ in eclipse by adding MaintainJ plugin to eclipse. Create a new project of MaintainJ trace type and copy generated ser files into this project in a folder.

A good overall demo is provided – http://maintainj.com/userGuide.jsp?param=overviewDemo

Shared Nothing vs Shared Everything

In database cluster implementation we can have multiple ways to make sure how different nodes will communicate with each other.

Shared nothing approach: None of the nodes will use others memory or storage. This is best suited for the solutions where inter node communication is not required, i.e. a node can come up with a solution on its own.

Shared Memory: In this approach memory is shared, i.e. each node/ processor is working with same memory. This is used when we need nodes to share solutions/ calculations done by other nodes and are available in memory.

Shared Everything: In this approach nodes share memory plus storage. This makes sense when nodes are working on problem where calculations and data created/ used by node is dependent on others.

Further Reads:

https://www.quora.com/What-are-the-differences-between-shared-nothing-shared-memory-and-shared-storage-architectures-in-the-context-of-scalable-computing-analytics

https://en.wikipedia.org/wiki/Shared_nothing_architecture

How to check if a port is open on a server?

I wanted to check if the service I am trying to access on a server is actually listening on the port I am hitting. I tried to look for a ping variant which could tell me if the port is listening and required service is up and running.

Found nmap command as answer.

nmap -p 80 google.com

Starting Nmap 6.40 ( http://nmap.org ) at 2016-03-02 16:05 IST
Nmap scan report for google.com (216.58.197.78)
Host is up (0.050s latency).
rDNS record for 216.58.197.78: maa03s21-in-f14.1e100.net
PORT STATE SERVICE
80/tcp open http

It checks the port state and also what service is listening at the port.

Inject Or Autowired

Sometimes in a Spring framework code, we see the keywords @Inject and @Autowired being used interchangeably. Simply putting it @Autowired is Spring specific annotation for implementing Dependency Injection, whereas @Inject is part of Java EE 6 specification, hence more generic.

JSR 299, Java EE 6 specification, provided a feature called Contexts and Dependency Injection (CDI). http://docs.oracle.com/javaee/6/tutorial/doc/giwhb.html.

JSR 330, more specifically talks about Dependency Injection. https://dzone.com/articles/what-relation-betwe-there

A more elaborated explanation on usage of various DI annotations – http://blogs.sourceallies.com/2011/08/spring-injection-with-resource-and-autowired/#more-2350

Kill blocking session in Oracle

To check which all session are live on an oracle server

select * from v$session

To check blocking sessions

SELECT
O.OBJECT_NAME,
S.SID,
S.SERIAL#,
P.SPID,
S.PROGRAM,
SQ.SQL_FULLTEXT,
S.LOGON_TIME
FROM
V$LOCKED_OBJECT L,
DBA_OBJECTS O,
V$SESSION S,
V$PROCESS P,
V$SQL SQ
WHERE
L.OBJECT_ID = O.OBJECT_ID
AND L.SESSION_ID = S.SID
AND S.PADDR = P.ADDR
AND S.SQL_ADDRESS = SQ.ADDRESS;

To kill a session

alter system kill session ‘SID,SERIAL#';

HashMap- Collision handling using chaining and open addressing

A HashMap is a datastructure which links a key to the value. For example key can be employee id and value might be employee details. The definition actually is true for any map, a hash map adds the functionality of hashing to a simple key-value map. A hash function maps a key to a particular bucket (we can think of it as array position) to add value. For example, if employee id is unique, a good hash function would simply return employee id itself as key. But in case, we are trying to use employee name as key, we might need a better hashing function to generate a bucket id based on employee name.

As we can see from above example, if we do not choose a good hash function, we might not be able to get unique bucket ids for every key. So multiple keys might actually return same bucket id. This causes a collision.

There are 2 important ways to handle collisions

Separate Chaining: In this technique, we create a list inside each bucket to store the objects in case one bucket needs to handle multiple objects. For example, say keys Dave and David returns same hash say bucket number 4 (or array index 4), we would create a linked list in bucket four and store both elements in the list. The advantage is that we can infinitely grow this list (provided no space concerns) and handle any level of collisions.

Open Addressing:
In this technique, if in case say two keys generate same hash, the first one would be stored at the hash position, and the other one(s) would be stored at next best position. There are again multiple ways to find the next best position. Here are 2 simple ones

Linear Probing: Simply look for next empty space in array. For previous example, say David has a hash value 4, and we found that position 4 is already filled, we will simply look for next empty position, say 5 is empty, we will save David’s object in 5 or if 5 is also booked we will move on to 6 and so on.

Double Hashing: Going to previous example, if we found bucket 4 is full, instead of simply looking for next empty position, we will invoke a new hash function and add the returned number to initial bucket number. Say input David returned 16 from second hash function, we will try to insert the object at 4+16 i.e. 20th position. If 20th position is also filled, we will move to 20+16 i.e. 36 and so on.

Worst case Analysis

The performance of a hashmap usually depends on the hashing function. For example, say we have <=1000 objects and we create a map with 1000 entries. The perfect hashing function would map each entry to a unique entry in the map. In such a case we will have addition, deletion and search at worst case as O(1).

Similarly, if we choose a worse hash function, which lets say maps each key to a single bucket (say a dumb hash function return 10, no matter what the input is), we will end up with a worst case search of O(n).

Because of the above reason, we cannot guarantee a worst case performance for a hashmap, and hence a Binary Search Tree or a Red Black tree would sometimes be preferred in performance critical operations, as we can guarantee a max search time.

Separate Chaining vs Open Addressing

An obvious question is that which collision handling technique should be used. Both has its advantages. As a thumb rule, if space is a constraint and we do have an upper bound on number of elements, we can use open addressing. The advantage with Separate chaining is that it can grow indefinitely (if space is available).

Minimum Priority Queue- Java Implementation

http://kamalmeet.com/data-structure/priority-queue/
http://kamalmeet.com/algorithms/heap-data-structure/

package com.kamalmeet.www;

/**
 * This is a sample implementation of Min Priority queue. 
 * This will work for any object type which has a valid comparable interface implemented.
 * 
 * @Copyright kamalmeet.com
 * @author kamalmeet
 *
 * @param 
 */
public class MinPriorityQueue {
  
  Type minQueue[]=null;
  int elements=0;
  
  /**
   * Constructor to create a Minimum priority queue of a specific size.
   * 
   * @param size
   */
  public MinPriorityQueue(int size){
    minQueue=(Type[]) new Object[size];
  }
  
  /**
   * A new element is always added at the last leaf and then moved up till we find correct position.
   * 
   * @param t
   */
  public void add(Type t)
  {
    if(elements==0)
    {
      System.out.println("adding"+t);
      minQueue[0]=t;
      System.out.println(minQueue[0]);
      elements++;
    }
    else
    {
      System.out.println("adding 2"+t);
      minQueue[elements]=t;
      moveUp(elements);
      elements++;
      
    }
  }
  
  /**
   * Zeroth element is deleted and returned. 
   * Last element would move to root element and queue would be heapified.
   *  
   * @return
   */
  public Type delete()
  {
    Type min=minQueue[0];
    minQueue[0]=minQueue[--elements];
    moveDown(0);
    return min;
  }
  
  /**
   * In Move up or swim method, an element is compared to its parent and moved 
   * up unless correct position is found.
   * 
   * @param num
   */
  public void moveUp(int num)
  {
    System.out.println("move:"+num);
    while(((Comparable)minQueue[num]).compareTo(minQueue[parent(num)])<0)
    {
      swap(num, parent(num));
      num=parent(num);
    }
  }
  
  /**
   * In move down or sink method, an element is compared to its children and moved 
   * down unless correct position is found.
   * 
   * @param num
   */
  public void moveDown(int num)
  {
    if(leftChild(num)>elements)
      return;
    Type leftChild=minQueue[leftChild(num)];
    if(rightChild(num)>elements)
    {
      if(((Comparable)leftChild).compareTo(minQueue[num])<0)
      {
        swap(num, leftChild(num));
        return;
      }
    }
    else{  
      Type rightChild=minQueue[rightChild(num)];
      if(((Comparable)leftChild).compareTo(rightChild)<0)
      {
       if(((Comparable)leftChild).compareTo(minQueue[num])<0)
       {
         swap(num, leftChild(num));
         moveDown(leftChild(num));
       }
      }
      else
      {
        if(((Comparable)rightChild).compareTo(minQueue[num])<0)
        {
          swap(num, rightChild(num));
          moveDown(rightChild(num));
        }
      }
    }
    
  }
  
  /**
   * Method to swap 2 elements.
   * 
   * @param i
   * @param j
   */
  public void swap(int i, int j)
  {
    Type t=minQueue[i];
    minQueue[i]=minQueue[j];
    minQueue[j]=t;
  }
  
  /**
   * Find parent of an element. usually it is element/2 but we need to take 
   * care of the fact that array starts from 0.
   * 
   * @param i
   * @return
   */
  public int parent(int i)
  {
    if(i==0 || i==1 || i==2)
      return 0;
    int p=(i+1)/2;
    return p-1;
  }
  
  /**
   * Finds left child for the element.
   * 
   * @param i
   * @return
   */
  public int leftChild(int i)
  {
    //as array starts from 0, we will need to add 1 initially and subtract 1 finally
    int c=0;
    c=(i+1)*2;
    return c-1;
  }
  
  /**
   * Find right child for the element.
   * 
   * @param i
   * @return
   */
  public int rightChild(int i)
  {
    //as array starts from 0, we will need to add 1 initially and subtract 1 finally
    int c=0;
    c=((i+1)*2)+1;
    return c-1;
  }
  
  /**
   * Method to print the minimum queue (for debug).
   */
  public void print()
  {
   
    for(int i=0;i min= new MinPriorityQueue(10);
    
    min.add(11);
    min.add(88);
    min.add(99);
    min.add(43);
    min.add(2);
    min.add(36);
    min.add(222);
    min.add(123);
    min.add(7);
    
    min.print();
    System.out.println("********************");
    System.out.println("deleted:"+min.delete());
    min.print();
    
  }

}

Strongly connected components- Kosaraju’s algorithm

Before starting with Kosaraju’s algorithm, you might want to revisit Depth first and beadth first algorithms.

http://kamalmeet.com/algorithms/depth-first-search/
http://kamalmeet.com/algorithms/breadth-first-search/

Refer the following graph

scc

vertex a,b in a graph are stringly connected if a is reachable from b and b is reachable from a.

In above graph, ABCD subgraph is strongly connected.

Kosaraju’s algorithm helps in finding all such strongly connected components in a graph.

1. Run Depth first search (DFS) on the graph and add verticies on a stack S.
2. Reverse (transpose) the graph by reversing directions of all the edges.
3. Pull a vertext v fron Stack S (step 1), run DFS on on vertex on reversed graph created in step 2. All the nodes found in DFS from vertex v are stringly connected. Remove all nodes found in DFS from reversed graph and stack S.

Further reads-

https://en.wikipedia.org/wiki/Strongly_connected_component

https://en.wikipedia.org/wiki/Kosaraju’s_algorithm
http://www.geeksforgeeks.org/strongly-connected-components/