Cyclic barrier

Methods should be called within a sequence

A class foo could have the following three methods.
If a single object of Foo is passed in three threads t1, t2 and t3. The threads calls the methods in the following order.

• t1 calls f2()
• t2 calls f3()
• t3 calls f1()

Then f1() should get executed first and then f2() and then f3(). t1 will wait for the completion of t3, t2 will wait for the completion of t1. Do not use thread joining as there could be any such number of threads at runtime. The output should look like the following, no matter in what order the methods are being called within the threads.

Code
Output

Two threads printing even and odd numbers one after the other

There should be two threads 'ODD' thread and 'EVEN' thread- 'ODD' thread will first print 1 and then will allow the 'EVEN' thread to print 2. 'ODD' thread will then print 3 and the 'EVEN' thread will print 4 and so on -

Code

Output

Bathroom problem

There is a single bathroom in a hostel, which is shared by boys and girls. Following rules are applicable -

• Any number of males can enter the bathroom, if there is a male inside it.
• Any number of females can enter the bathroom, if there is a female inside it.
• Male or female will wait in a queue if any opposite sex is inside the bathroom.
• Everybody gets to use the bathroom in fair way and there is no starvation.

Code that provides no fairness
Bathroom.java
Test.java

Solution

There are different way to approach a problem and in that one approach is to solve a simpler version of problem and then build over a bigger solution.  lets try to break this problem. If problem is that only one man or female can enter in a bathroom then we have created one bathroom lock and every body was waiting on that if it was acquire by any other thread. but this problem states that multiple threads of same type can enter in bathroom. That's mean ,  different types of threads cannot wait on same lock. we need more locks on which thread can wait. so we need three locks.

 Semaphore bathroom = new Semaphore(1);
 Semaphore mutexForMan = new Semaphore(1);
 Semaphore mutexforWomen = new Semaphore(1);

We also need a variable by which we can identify that who is using bathroom so that other type of thread can wait and same type of thread can processed.


       public void manEnter() throws Exception
{
mutexForMan.acquire();
numberOfMan++;
if (numberOfMan == 1)
{
bathroom.acquire(); // used to control entry in  bathroom
System.out.println("Man acquire room" );
}
System.out.println("Number of Mans=" + numberOfMan);
mutexForMan.release();
}

public void manExit() throws Exception
{
mutexForMan.acquire();
numberOfMan--;
if (numberOfMan == 0)
{
System.out.println("Man release room" );
bathroom.release();

}
mutexForMan.release();
}

public void womanEnter() throws Exception
{
mutexforWomen.acquire();
numberOfWoman++;
if (numberOfWoman == 1)
{
bathroom.acquire();
System.out.println("Woman acquire room" );
}
System.out.println("Number of Woman=" + numberOfWoman);
mutexforWomen.release();
}

public void womenExit() throws Exception
{
mutexforWomen.acquire();
numberOfWoman--;
if (numberOfWoman == 0)
{
System.out.println("Woman release room" );
bathroom.release();

}
mutexforWomen.release();
}

Difference between thread's context class loader and normal classloader

Class loader basics
JVM provides an hierarchy of class loaders. Let's start with the following class loaders.
Bottstrap class loader
Loads the classes from JAVA_HOME/jre/lib
Extension class loader
Loads the classes from JAVA_HOME/jre/lib/ext
System class loader
Loads the classes from application class path, which is value of the property java.class.path.

Whenever A class A needs to load a class say B, B will be loaded by using the A's classloader. Class loaders in java follows the delegation model. A class loader will pass the request to system class loader, which then will forward the request to extension and extension will forward the request to bootstrap and finally one of the class loaders will load the class.

Thread's context class loader
Let's understand this in jdbc context. JDBC specifications are provided by sun and are part of JAVA_HOME/jre/lib/ext. So all these classes are loaded using extension class loader.

Class loading is hard to understand..need to explain the followings...

• DriverManager class and drivers registration process in J2SE environment
• DriverManager class and a driver that is not part of system class loader and whose location will be known at runtime
• DriverManager and drivers registration in tomcat servlet container
• Service loader's -> public static <S> ServiceLoader<S> load(Class<S> service) {

Count possible ways to run up the stairs

Problem -  A person is running up a stair and can hop either 1 step, 2 step or 3 steps at a time. Implement a method to count how many ways the person can run up the stairs.

Solutions


Output-

Number of step 3831006429
 Elapsed Time using Recursion= 43119
 Number of step 3831006429

 Elapsed Time using DP= 2

Bottomup fibonacci number

In bottom up programming we first try to solve the problem for bottom up value and then use them to build up the complete solution.

Code

Dynamic programming - memoization - coin change problem

Dynamic programming - memoization - fibonacci number

Code

Dynamic programming - memoization - knapsack problem

A thief enters a house and have a cloth to collect the items. The cloth has a fix capacity M. Thief can either select an item fully or leave that. Given the items with weight w1,w2,...wn and there values v1,v2,...vn. What is the maximum values he can collect.

For example -

item number	weight	value
1	2	3
2	3	4
3	4	5
4	5	6

If the capacity of the cloth is 5, the thief can select item#1 and item#2 to make the (3+4=7) profit.

Code

Dynamic programming - memoization - cutting a rod problem

Problem - Find best way to cut a rod of length n

• Given: rod of length $n$
• Assume that each length rod has a price p(i) fot length i
• Find best set of cuts to get maximum price
• Each cut is integer length
• Can use any number of cuts, from 0 to n-1
• No cost for a cut

Solution - Using dynamic bottom up to figure out optimum order to fill the solution array Or Using the recursion 

import java.util.ArrayList;

public class CutRod {

int[] cutSize = {1,2,3,4,5,6,7,8};
int[] cutCost = {1,5,8,9,10,17,17,20};
int rodSize = 8;
public static void main(String[] args) {
CutRod rod = new CutRod();
ArrayList<Integer> maxCosts = new ArrayList<Integer>();
maxCosts.add(0, 0);
rod.calculateMaxCostWithDP(maxCosts, 1);

System.out.println( "maxCost By Bottom Up DP= " + maxCosts.get(rod.rodSize )  );
System.out.println( "maxCost By Recursion=" + rod.calculateMaxCostWithRecursion(rod.rodSize));
}

private void calculateMaxCostWithDP(ArrayList<Integer> maxCosts, int size) {
if (size > rodSize )
return;
int b ;
int cost =0;
int maxCost = 0;

for(int index= 0 ; index < cutSize.length ; index++){
b = size - cutSize[index];
if ( b < 0)
continue;
cost =  maxCosts.get(b).intValue() + cutCost[index];
if ( cost > maxCost){
maxCost = cost;
}
}
maxCosts.add(size,maxCost);
calculateMaxCostWithDP(maxCosts, ++size);

}

private int calculateMaxCostWithRecursion(int size) {
if ( size < 1)
return 0;
int b ;
int cost =0;
int maxCost = 0;

for(int index= 0 ; index < cutSize.length ; index++)
{
b = size - cutSize[index];
if ( b < 0)
continue;
cost = calculateMaxCostWithRecursion(b) + cutCost[index];
if ( cost > maxCost) {
maxCost = cost;
}
}
return maxCost;
}

}

Output-

maxCost By Bottom Up DP= 22

maxCost By Recursion=22

2D Binary Search

Next Higher permutation of a given Number

QuickSelect Algorithm and its related problems

By default, Hashtable is unordered. How can you retrieve Hashtable elements in a inserted order?