Technical Problem 4

Given a number N, write a program that returns all possible combinations of numbers that add up to N, as lists. (Exclude the N+0=N)

For example, if N=4 return {{1,1,1,1},{1,1,2},{2,2},{1,3}}

Technical Interview Problem 3

 Design a component that will implement web browser history. the user goes to different site and once he press on history button you should display the last 5 (no duplicates allowed, and 5 can be any N later) if duplicates occur display the most recent one. so if user visit : G,A,B,C,A,Y and than press "history" we will display Y,A,C,B,G. and of course he can go later to two other websites and than press "history" we will show them than the previous 3. 

Technical Interview Problem 2

You visited a list of places recently, but you do not remember the 
order in which you visited them. You have with you the airplane 
tickets that you used for travelling. Each ticket contains just the 
start location and the end location. Can you reconstruct your journey?

Technical Interview Problem 1

given a dictionary of wrods,find the pair of word with following property:
1,the two word don't have same letter.
2,the multiple of the two word's length is maximum.
i give a simple O(n*n*k)(k is the average length of word) method.but i think there will be better one .

Write a method to convert base of given number

Understanding Garbage Collector

I have copied the following slides from a presentation given by CTO of Azul Systems.

- concurrent and parallel are orthogonal terms. All four combinations are possible.

- All modern jvm will be the precise as if they are not precise then they will not be able to move stuff and that will lead to fragmentation.

- So the availability of safe points is crucial.

- Compiler injects these safe points.

- If there are not well placed safe points, threads will have to wait for others to reach safe points so that GC cab be started.

-At these safe points, GC will issue an stop-the-world.

Complex ballroom dancers problem

Imagine that threads represent ballroom dancers and that two kinds of dancers, leaders and followers, wait in two queues before entering the dance floor. When a leader arrives, it checks to see if there is follower waiting. If so, they can both proceeds. Otherwise it waits.

Similarly, when a follower arrives, it checks for a leader and either proceeds or waits, accordingly.

At a time there will be a single pair doing the dance. Once a pair leave, the other pair enters. As shown in the diagram.

We will have the following ballroom class -

Simple ballroom dancers problem

Imagine that threads represent ballroom dancers and that two kinds of dancers, leaders and followers, wait in two queues before entering the dance floor. When a leader arrives, it checks to see if there is follower waiting. If so, they can both proceeds. Otherwise it waits.

Similarly, when a follower arrives, it checks for a leader and either proceeds or waits, accordingly.

We will have the following ballroom class -

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?