Friday, October 2, 2009

Find roof’s height

You entered in room and noticed that there is nothing but a bulb hanging from the ceiling. You noticed that the bulb is exactly touching your head and it is in the center of roof (where diagonals meet.)

So, what is roof’s height? BTW, you just came from office. So, go ahead and take some assumptions

Solution: -
The only assumption I will take is "I have a watch" & actually I do :) Now, given that bulb is hanging from the ceiling, I can make it swing like a "Pendulum". Then I can find out the length of the string T = 3.14 SQRT (L/32) . Finally, I will add 5'10 to L and that the roof's height :)

So, do you want more puzzles ??

Give your comments -

Friday, August 7, 2009

Dependency Injection

Dependency Injection (DI), Inversion of Control (IoC) sounds scary as compared to what they are. These two terms are used interchangeably in IT industry. Basically, IoC is a principle and DI is a design pattern which follows this principle. In this pattern (DI), container takes the responsibility to inject the appropriate resources to each component it manages. Lets take it step by step with example. If we look at the below implementation of CallService, we notice that it is tightly coupled with the class HomePhone.


public class CallService {
Callable callMaker = new HomePhone();

public void callClient(int clientId){
// we do not care how to make a call, but we will need callMaker
callMaker.makeCall();
}
// other methods to exposed goes here.
}

interface Callable{
void makeCall();
}

class HomePhone implements Callable{
public void makeCall() {
System.out.println("Calling from HomePhone ...");
}
}

class MobilePhone implements Callable{
public void makeCall() {
System.out.println("Calling from MobilePhone ...");
}
}


Problem is if we want to make a call from MobilePhone, we will have to write another service or will have to update CallService and recompile. BTW, who writes the code like above these days. Atleast we'll write our CallService like this.


public class CallService {
Callable callMaker = null;

public CallService(Callable callMaker){
this.callMaker = callMaker;
}
public void callClient(int clientId){
// we do not care how to make a call, but we will need callMaker
callMaker.makeCall();
}
// other methods to exposed goes here.
}


In this case what we are doing is "injecting" the dependency "Callable" to the component "CallService" via constructor. So, this is one form of dependency injection. But in this case I am asking my CallService client to instantiate a Callable object to be used. Other way is to provide a setter method for callMaker. What if the user of CallService forgets to instantiate the CallMaker before using it ? famus NullPointerException, remember ? There are few light weight containers which takes the responsiblity of injecting appropriate resources before you can use the component [Spring container.] Now questions is what exactly container does ? lets look at the below code which acts (sort of) as a container and manages given components based upon configuration file.


class Container {
private static Container INSTANCE = new Container();
public static Container getInstance() {
return INSTANCE;
}
Map components;

private Container() {
components = new HashMap();
try {
Properties properties = new Properties();
properties.load(new FileInputStream("testPackage/other/properties/container.properties"));
for (Map.Entry entry : properties.entrySet()){
process((String)entry.getKey(), (String)entry.getValue());
}
} catch (Exception e) {
throw new RuntimeException(e);
}
}
private void process(String key, String value) throws Exception{
String[] arr = key.split("\\.");
if (arr.length == 1){
Object component = Class.forName(value).newInstance();
components.put(key, component);
}else{
Object component = components.get(arr[0]); // CallService
Object toBeSet = components.get(value); // CallMaker
PropertyUtils.setProperty(component, arr[1], toBeSet); //CallService.setCallMaker(...)
}
}
public Object getComponent(String key){
return components.get(key);
}

}

class CallServiceClient {
public static void main(String[] args){
Container container = Container.getInstance();
CallService service = (CallService)container.getComponent("callservice");
service.callClient(5);
}
}

container.properties
#Define callMaker
callMaker=testPackage.other.HomePhone

#Define callService
callService=testPackage.other.CallService
#inject callMaker to callService
callService.callMaker=callMaker
# end

This is a typical example of how a container manager different components and their dependencies.

Sunday, July 12, 2009

Synchronization is easy ?

Sometimes its hard to find bugs when it comes to multi-threading environment as few programers forget fundamental concepts of writing a synchronized block. If we talk about synchronized block I can create it in three different ways.

1. Using Object synchronization [acquire lock on "this"]
2. Using Class synchronization [acquire lock on "MyClass.class"]
3. Using "another" Object for synchronization [acquired lock on "different" object]

Lets see if you can find the bug in the below code. HINT: Read the above 3 points carefully.


/*
* CountManager
*/
public class CountManager {
static int count = 0;

public static synchronized void incrementFew(int n) {
for (int i = 0; i < n; i++) {
count++;
log("Static : " + count);
try {
Thread.sleep(200);
} catch (Exception e) {
// doesn't matter.
}
}
}

public synchronized void addFew(int n) {
for (int i = 0; i < n; i++) {
count++;
log("Non-Static : " + count);
try {
Thread.sleep(200);
} catch (Exception e) {
// doesn't matter.
}
}
}

/*
* CountMangagerClient, needs run()
*/
static abstract class CountManagerClient implements Runnable {
CountManager s;

public CountManagerClient(CountManager s) {
this.s = s;
}
}

private static void log(String str) {
System.out.println(str);
}

/* main */
public static void main(String[] args) {
CountManager s = new CountManager();
Thread t1 = new Thread(new CountManagerClient(s) {
public void run() {
s.addFew(5); // no change in client code
System.out.println("Result = " + CountManager.count);
}
});
Thread t2 = new Thread(new CountManagerClient(s) {
public void run() {
CountManager.incrementFew(5); // no change in client code
System.out.println("Result 2 = " + CountManager.count);
}
});
t1.start();
t2.start();
}
}


OUTPUT
Non-Static : 1
Static : 2
Non-Static : 4
Static : 4
Static : 6
Non-Static : 6
Static : 7
Non-Static : 8
Non-Static : 10
Static : 10
Result = 10
Result 2 = 10

If you were able to find the bug, you really know synchronization. Anyways , the problem here is we are trying to synchronize the code block by acquiring the locks from two differet objects AKA "this" and "MyClass.class"

So, what is the solution? its simple; either use Object synchronization or Class synchronization. But what if the code is already being used by other clients which uses both? humm !! then introduce another object wihch is common to both of these code blocks and acquire lock on that object. This way you will not have to change the client code. Here is how you will do that:



/*
* CountManager
* @Threadsafe
*/
public class CountManager {
static int count = 0;
/* Object to get lock from */
private static final Object obj = new Object();

public static void incrementFew(int n) {
synchronized (obj) { /* get lock from Object 'obj' instead of 'MyClass.class'*/
for (int i = 0; i < n; i++) {
count++;
log("Static : " + count);
try {
Thread.sleep(200);
} catch (Exception e) {
// doesn't matter.
}
}
}
}

public void addFew(int n) {
synchronized (obj) { /* get lock from Object 'obj' instead of 'this'*/
for (int i = 0; i < n; i++) {
count++;
log("Non-Static : " + count);
try {
Thread.sleep(200);
} catch (Exception e) {
// doesn't matter.
}
}
}
}

/*
* CountMangagerClient, needs run()
*/
static abstract class CountManagerClient implements Runnable {
CountManager s;

public CountManagerClient(CountManager s) {
this.s = s;
}
}

private static void log(String str) {
System.out.println(str);
}

public static void main(String[] args) {
CountManager s = new CountManager();
Thread t1 = new Thread(new CountManagerClient(s) {
public void run() {
s.addFew(5); // no change in client code
System.out.println("Result = " + CountManager.count);
}
});
Thread t2 = new Thread(new CountManagerClient(s) {
public void run() {
CountManager.incrementFew(5); // no change in client code
System.out.println("Result 2 = " + CountManager.count);
}
});
t1.start();
t2.start();
}
}


OUTPUT:
Static : 1
Static : 2
Static : 3
Static : 4
Static : 5
Non-Static : 6
Result 2 = 6
Non-Static : 7
Non-Static : 8
Non-Static : 9
Non-Static : 10
Result = 10

Thursday, July 9, 2009

Odd one out !!

Problem: In an array of integers, all but one occur even number of times. Find the one which occur odd number of times.

First solution:
Use Hashmap like data structure Map to hold the Integer in the given array & the corresponding count.
performance : O(n) + O(n) = O(n)
Problem : extra space & data structure

Second solution:
Sort the array & start skipping the pair e.g. [2,2,3,3,9,9,11,11,11,12,12,34,34] : 11 cannot be skipped as it’s not a pair.
performance: O (nlog(n)) + O(n)
problem: bad performance

Trick solution:
We know X XOR X = 0, therefore start with 0 as result and XOR all the elements with result.
performace : O(n)
problem: none, let me know if you see any


public static void main(String[] args){
int[] arr = {2,3,6,9,20,2,4,6,9,20,3};
int result = 0;
for(int i: arr){
result ^= i;
}
System.out.println(result); //prints 4
}