Category Archives: Uncategorized

Train Routing Problem

Problem Statement: Say 4 trains start at the same time. They may travel via same stations. Only one train can be there at one station at once. How should we achieve this using multi threading.

Solution:  I consider  this as an example of multi threading. Say, there are four trains (Train 1, Train 2, Train 3 and Train 4) which run between stations A,B,C,D and E.

We assume the following points :

  1. The train routes are single line. So, only one train can be there at one station at once.
  2. All the trains are stopping for a fixed interval in all the stations (5 seconds).
  3. All the trains start at the same time.
  4. All the trains travel at the same speed.

Following are the train routes :

Train 1 Route = A –> B –> E
Train 2 Route =  B –> C –> D
Train 3 Route =  A –> C –> E
Train 4 Route = A –> B –> C –> D –> E


 

import java.util.HashMap;

public class TrainRoutingProblem implements Runnable{

private char myroute[];
 static HashMap<Character,Character> stations = new HashMap<Character,Character>();
 
 
 public void setRoute(char[] myroute)
 {
 this.myroute = myroute;
 }

public TrainRoutingProblem()
 {

}

public synchronized void atStation(char c) 
 {
 stations.put(c, 'O');

try 
 {
 Thread.sleep(100);

} 
 catch (InterruptedException e) {
 System.out.println("Station "+c+" is occupied by "+Thread.currentThread().getName()+". Please wait..");
 }

stations.put(c, 'V');
 System.out.println(Thread.currentThread().getName()+" has left station "+c);
 }


 public void trainRun()
 {

for(char c:myroute)
 {
 System.out.println(Thread.currentThread().getName()+" is approaching station "+c);
 
 atStation(c); 
 
 }
 }

public void notifyJourneyStarted()
 {
 System.out.println(Thread.currentThread().getName()+" has started its journey.");
 }

public void notifyJourneyFinished()
 {
 System.out.println(Thread.currentThread().getName()+" has completed its journey.");
 }

public static void reset()
 {
 stations.put('A', 'V');
 stations.put('B', 'V');
 stations.put('C', 'V');
 stations.put('D', 'V');
 stations.put('E', 'V');

}

public static void main(String[] args) 
 { 
 char route1[]={'A','B','E'};
 char route2[]={'B','C','D'};
 char route3[]={'A','C','E'};
 char route4[]={'A','B','C','D','E'};
 
 TrainRoutingProblem routeObj = new TrainRoutingProblem();
 routeObj.setRoute(route1);
 
 Thread t1 = new Thread(routeObj);
 t1.setName("Train 1 Route 1");
 
 routeObj.setRoute(route2);
 Thread t2 = new Thread(routeObj);
 t2.setName("Train 2 Route 2");

routeObj.setRoute(route3);
 Thread t3 = new Thread(routeObj);
 t3.setName("Train 3 Route 3");
 
 routeObj.setRoute(route4);
 Thread t4 = new Thread(routeObj);
 t4.setName("Train 4 Route 4");
 
 TrainRoutingProblem.reset();
 
 t1.start();
 t2.start();
 t3.start();
 t4.start();
 
 }

@Override
 public void run() {
 notifyJourneyStarted();
 trainRun(); 
 notifyJourneyFinished();
 }
}
Output:

Train 3 Route 3 has started its journey.
Train 4 Route 4 has started its journey.
Train 1 Route 1 has started its journey.
Train 1 Route 1 is approaching station A
Train 2 Route 2 has started its journey.
Train 4 Route 4 is approaching station A
Train 3 Route 3 is approaching station A
Train 2 Route 2 is approaching station A
Train 1 Route 1 has left station A
Train 1 Route 1 is approaching station B
Train 2 Route 2 has left station A
Train 2 Route 2 is approaching station B
Train 3 Route 3 has left station A
Train 3 Route 3 is approaching station B
Train 4 Route 4 has left station A
Train 4 Route 4 is approaching station B
Train 3 Route 3 has left station B
Train 3 Route 3 is approaching station C
Train 3 Route 3 has left station C
Train 3 Route 3 is approaching station D
Train 3 Route 3 has left station D
Train 3 Route 3 is approaching station E
Train 3 Route 3 has left station E
Train 3 Route 3 has completed its journey.
Train 2 Route 2 has left station B
Train 2 Route 2 is approaching station C
Train 1 Route 1 has left station B
Train 1 Route 1 is approaching station C
Train 1 Route 1 has left station C
Train 1 Route 1 is approaching station D
Train 2 Route 2 has left station C
Train 2 Route 2 is approaching station D
Train 4 Route 4 has left station B
Train 4 Route 4 is approaching station C
Train 4 Route 4 has left station C
Train 4 Route 4 is approaching station D
Train 2 Route 2 has left station D
Train 2 Route 2 is approaching station E
Train 2 Route 2 has left station E
Train 2 Route 2 has completed its journey.
Train 1 Route 1 has left station D
Train 1 Route 1 is approaching station E
Train 4 Route 4 has left station D
Train 4 Route 4 is approaching station E
Train 1 Route 1 has left station E
Train 1 Route 1 has completed its journey.
Train 4 Route 4 has left station E
Train 4 Route 4 has completed its journey.

Note: This is very basic solution and needs to be enhanced to meet more scenarios. Till I find out a better approach “Keep Safe and Happy Coding 🙂 “…

Advertisements

Quickly sorting using Quick Sort Algorithm

Quick sort algorithm and the tutorial is explained nicely  .

I have used the following steps for using quick sort:

  1. Select the first element as pivot.
  2. Position it properly in the array by comparing it from end of array.
  3. Reassign the pivot with the newly swapped element.
  4. Compare it with the starting of the array.
  5. Reassign the pivot with the next element from left side.
  6. Repeat steps 2-5 until the array is sorted.

public void sort(int arr[])
{
int pi = 0,
temp=0;

int leftpi = -1 ,
rightpi=arr.length-1,
count = 0;

boolean leftsorted = false,rightsorted = false;

System.out.println(“=================================”);
for(int a:arr)
{

System.out.print(a+” | “);
}

do{

pi = leftpi + 1;
System.out.println(“\n==========PASS “+(++count)+”==================”);
for(int i = arr.length -1 ; (i >=0 && i > leftpi) ; i– )
{

if(arr[pi] > arr[i])
{
temp = arr[i];
arr[i] = arr[pi];
arr[pi] = temp;

System.out.println(“Pivot=”+arr[pi]);

for(int a:arr)
{

System.out.print(a+” | “);
}

leftpi = pi;
pi = i ;
leftsorted = true;
break;
}
}

for(int j = 0; (j<arr.length || j<rightpi-1) ; j++)
{
if(arr[pi] < arr[j])
{
temp = arr[j];
arr[j] = arr[pi];
arr[pi] = temp;

System.out.println(“Pivot=”+arr[pi]);

for(int a:arr)
{

System.out.print(a+” | “);
}

rightpi = pi ;
pi = j ;
rightsorted = true;
break;
}
}

if(!leftsorted && !rightsorted)
{
System.exit(0);
}

leftsorted = false;
rightsorted = false;

}while(leftpi<=rightpi);
}

 

While this gives me the sorted array but I think there are some passes in the above iteration which can be skipped. Still trying for a better solution. Keep safe and happy coding 🙂

 

String Literal versus String Object

Strings are a special type of object in Java. Unlike C++, Strings in Java are character arrays and not necessarily end with a newline character.

So, what is a String literal ?

String a=”abcd”;

When this happens, a pool in the heap is created and “abcd” is stored in it. a now refers to that location in string pool.

String b=”abcd”;

When we write this line, b will refer to the same location in the string pool as a is referring.

Hence the following code would return true, as == checks for content equality and equals checks for object equality.

if (a==b && a.equals(b))

return true;

else

return false;

Now what happens when we use the new keyword.

String c=new String(“abcd”);

This creates a new object and a separate place not referring to the string pool.

Hence the following code returns false as a and c and not the equal objects.

if (a==c && a.equals(c))

return true;

else

return false;

Happy coding..  🙂

Difference between HashMap and WeakHashMap?

Nice post on WeakHashMap and HashMap..

Vivek's Tech Blog

WeakHashMap is an implementation of Map interface where the memory of the value object can be reclaimed by Grabage Collector if the corresponding key is no longer referred by any section of program. This is different from HashMap where the value object remain in HashMap even if key is no longer referred. We need to explicitly call remove() method on HashMap object to remove the value so that it can be ready to be reclaimed(Provided no other section of program refers to that value object). Calling remove() is an extra overhead.

Here is a simple program which demonstrate the difference:-

import java.util.HashMap;

import java.util.Map;

import java.util.WeakHashMap;

public class WeakMap {

public static void main(String[] args) {

Map weak = new WeakHashMap();

Map map = new HashMap();

{

String weakkey = new String("weakkey");

weak.put(weakkey,new Object());

String key = new String("key");

map.put(key, new Object());

weakkey = null;

key = null;

}

System.gc();

}

View original post 141 more words

JVM, JRE and JDK

We can differentiate between the three using a very nice diagrammatic approach collected from the internet. Here is a brief description on the three.

JVM:

JVM (Java Virtual Machine) is an abstract machine. It is a specification that provides runtime environment in which java bytecode can be executed.

The JVM performs following main tasks:

  • Loads code
  • Verifies code
  • Executes code
  • Provides runtime environment

JRE :  JRE consistes of JVM and other libraries like rt.jar etc.

JDK: Along with JVM and JRE , JDK consists of the actual development tools such as javac and java.

The diagrammatic approach shown in http://www.javatpoint.com/difference-between-jdk-jre-and-jvm   link is very helpful.

WebSphere Concepts: Cell, Node, Cluster, Server…

Understanding Websphere Basic Terminologies

IT Developer World

Quick post… If you are not familiar with WebSphere at first you might get confused with its concepts: cell, deployment manager, node, node agent, cluster, server, …

First of all, lets start with the concept of a Cell:

A Cell is a virtual unit that is built of a Deployment Manager and one or more nodes. I guess a picture will help making things clearer:

WebSphere Cell

But still there are a few concepts that need to be explained. The next obvious one is the Deployment Manager.

The Deployment Manager is a process (in fact it is an special WebSphere instance) responsible for managing the installation and maintenance of Applications, Connection Pools and other resources related to a J2EE environment. It is also responsible for centralizing user repositories for application and also for WebSphere authentication and authorization.

The Deployment Manager communicates with the Nodes through another special WebSphere process, the Node Agent

View original post 163 more words