Software Job - Interview Question

Today, I was searching for some technical articles and stumbled upon this interview question from Amazon, for which I could immediately think about some good solution. Here's the question:

We have numbers from 1 to 52 that are put into a 51 number array, what's the best way to find out which number is missing?

I read an answer from some guy, who said to sort the numbers first and then loop through and find the number. I thought that was inefficient way of doing that. My answer is as below:

1) - Calculate the sum of all numbers stored in the array of size 51. 
2) - Subtract the sum from (52 * 53)/2   -- Formula : n (n+1)/2.

The result of subtraction is the answer for this question.

Any other solutions that you know of?!?!?!

Code Bubbles

So far, I have developed code on different IDE's (Integrated Development Environment) like Kawa, IntelliJ, Netbeans, Eclipse and others, but pretty curious to know how this new IDE called 'Code Bubbles' would be. Here's a demo from 'em:

Create Your Own Dependency Injection Framework

Inspired by the latest developments in Java and other open source frameworks like Guice, today I worked for a couple of hours on creating a small dependency injection framework (on the lines of guice), which I named it as 'Funny Dependency Injection' framework. This framework has only one custom annotation, which annotates a constructor, to provide dependency injection (only constructor injection in this example). Here's the code for the 'Shoot' annotation:

Shoot.java
package com.chetty.shoot;

import java.lang.annotation.Documented;
import static java.lang.annotation.ElementType.CONSTRUCTOR;
import static java.lang.annotation.ElementType.FIELD;
import static java.lang.annotation.ElementType.METHOD;
import java.lang.annotation.Retention;
import static java.lang.annotation.RetentionPolicy.RUNTIME;
import java.lang.annotation.Target;

@Target({ METHOD, CONSTRUCTOR, FIELD })
@Retention(RUNTIME)
@Documented
public @interface Shoot {}

And here's the client class, for which the 'Shoot' annotation is used:

Client.java
package com.chetty.client;

import com.chetty.service.NewService;
import com.chetty.service.Service;
import com.chetty.shoot.Shoot;

public class Client {
	private Service service;
	private NewService newService;
	
	@Shoot
	public Client(Service service, NewService newService) {
		this.service = service;
		this.newService = newService;
	}
	
	public void doSomething() {
		service.serve();
		newService.doSomethingNew();
	}
}

In the above class, you can see the 2 parameters for Client's constructor. These dependencies will be injected at runtime, with the help of "Shoot" annotation. The 'Service' and the 'NewService' interfaces are listed below:

Service.java
package com.chetty.service;

public interface Service {
 public void doSomething();
}

NewService.java
package com.chetty.service;

public interface NewService {
	public void doSomethingNew();
}

And here are 2 implementations of 'Service' interface:

ServiceImpl1.java
package com.chetty.service;

public class ServiceImpl1 implements Service {
 @Override
 public void doSomething() {
  System.out.println("I'm doing something in ServiceImpl1");  
 }
}

ServiceImpl2.java
package com.chetty.service;

public class ServiceImpl2 implements Service {
 @Override
 public void doSomething() {
  System.out.println("I'm doing something in ServiceImpl2");  
 }
}

And here's an implementation for 'NewService' interface:

NewServiceImpl1.java
package com.chetty.service;

public class NewServiceImpl1 implements NewService {
	@Override
	public void doSomethingNew() {
		System.out.println("I'm doing something new!");
	}
}

Below are 2 classes, which are part of this funnyDI framework..and which are used for configuration (dependency mapping information):

IModule.java
package com.chetty.module;

public interface IModule {
	void configure();
	 Class getMapping(Class type);
}

AbstractModule.java
package com.chetty.module;

import java.util.HashMap;
import java.util.Map;

abstract class AbstractModule implements IModule {
	private Map, Class> classMap = new HashMap, Class>();
	
	public abstract void configure();
		
	 void createMapping(Class baseClass, Class subClass) {
		classMap.put(baseClass, subClass.asSubclass(baseClass));
	}
		
	public  Class getMapping(Class type) {
		Class implementation = classMap.get(type);
		
	    if(implementation == null) 
	      throw new IllegalArgumentException("Couldn't find the mapping for : " + type);
	    
	    return implementation.asSubclass(type);
	}
}

And below is the class used for configuration by the user of 'funnyDI' framework, to provide configuration (dependency mapping information):

Module.java
package com.chetty.module;

import com.chetty.service.NewService;
import com.chetty.service.NewServiceImpl1;
import com.chetty.service.Service;
import com.chetty.service.ServiceImpl2;

public class Module extends AbstractModule {
	public void configure() {		
		createMapping(Service.class, ServiceImpl2.class);
		createMapping(NewService.class, NewServiceImpl1.class);
	}
}


And here's the core class of this funny dependency injection framework, which uses java reflection to find the dependency and inject it:

Shooter.java
package com.chetty.shoot;

import java.lang.reflect.Constructor;

import com.chetty.module.IModule;

public class Shooter {
	private IModule module;
	
	public Shooter(IModule module) {
		this.module = module;		
	}
	
	@SuppressWarnings("unchecked")
	public Object fireShot(Class klass) throws Exception {		
		if(klass != null) {			
			boolean flag = true;
			int index = 0;
			
			for(Constructor constructor: klass.getConstructors()) {				
				if(constructor.isAnnotationPresent(Shoot.class)) {
					if(flag && index == 0) { //To restrict to only one constructor injection
						flag = false;
						index++;
												
						Class[] parameterTypes = constructor.getParameterTypes();
						Object[] objArr = new Object[parameterTypes.length];
						
						int i = 0;
						
						for(Class c : parameterTypes) {
							Class dependency = module.getMapping(c);
																											
							if(c.isAssignableFrom(dependency)) {								
								objArr[i++] = dependency.getConstructor().newInstance();						
							}
						}
						
						Object resObj = klass.getConstructor(parameterTypes).newInstance(objArr);						
						
						return resObj;
					}					
				}
			}
		}
		
		return null;		
	}
}

There's one more class that is part of this funny DI framework, which initializes the configuration (based on the configuration module used) and returns the 'Shooter' class, which further provides the dependency injection:

FunnyDI.java
package com.chetty.shoot;

import com.chetty.module.IModule;

public class FunnyDI {
	public static Shooter getShooter(IModule module) {
		module.configure();
		return new Shooter(module);		
	}
}

And here's the main java class, which acts as a entry point for this funny application, which uses 'Funny Dependency Injection':
FunnyApp.java
package com.chetty.funny;

import com.chetty.client.Client;
import com.chetty.module.Module;
import com.chetty.shoot.FunnyDI;
import com.chetty.shoot.Shooter;

public class FunnyApp {
	public static void main(String[] args) throws Exception {
		Shooter shooter = FunnyDI.getShooter(new Module());
		
		Client client = (Client) shooter.fireShot(Client.class);
		
		client.doSomething();
	}
}

Thats it! When I ran the above program, "I'm doing something in ServiceImpl2" is printed, followed by "I'm doing something new", in the next line.

You can find the source code for this funny DI framework on funnydi. If you have any funny comments, please don't hesitate to post! ;)

DISCLAIMER: The code posted above was created for fun and to learn something new. The above framework needs to be improvised a lot, if you want to implement it, in your own project. So, don't use it blindly.

Google Guice - Example

Dependency Injection and Google's Guice framework need no introduction from me, as the documentation on Google's project hosting site is pretty good. Also, there are loads of articles and other information related to these topics, on the internet. So, I will start off with a pretty basic java project, to show 'Guice' in action.

Okay...Now lets think of a very small framework/project (so that, it will be easy to understand) to calculate the sum of all consecutive integers from 1 to n. You are given 'n' as the input and you are supposed to output the sum of all consecutive integers from 1 to n. Lets imagine that there is only one implementation, that we know of (at that moment), to implement the solution...but lets stick to a good design procedure of object oriented languages and make it flexible for future changes.

Below is the code for the only implementation that I know of, at that moment:

IMathAdditionService:

package com.chetty.service;

public interface IMathAdditionService {
public int sumOfAllConsecutiveNumbers(int n);
}



SnailAdditionService (implements IMathAdditionService):

package com.chetty.service;

public class SnailAdditionService implements IMathAdditionService {
@Override
public int sumOfAllConsecutiveNumbers(int n) {  
int sum = 0;
long startTime = System.nanoTime();

for(int i=1;i<=n;i++) {
sum += i;
}

long endTime = System.nanoTime();

System.out.println("Snail Addition Service - Sum : " + sum);
System.out.println("Time Complexity - O(n) and Time Taken : " + (endTime - startTime));
return sum;
}
}
Okay, now lets create an interface/client for this service (NOTE: I assume, you know something about 'Factory Pattern'. If not, check it here!). If you implement the 'Factory Pattern', this is how the code looks like: MathServiceFactory:
package com.chetty.service;

public class MathServiceFactory {
private MathServiceFactory() {}
private static IMathAdditionService mathService = new SnailAdditionService();

public static IMathAdditionService getInstance() {
return mathService;
}

public static void setInstance(IMathAdditionService service) {
mathService = service;
}
}

MathClient:
package com.chetty.client;

import com.chetty.service.IMathAdditionService;
import com.chetty.service.MathServiceFactory;

public class MathClient {
public void go() {
IMathAdditionService mathService = MathServiceFactory.getInstance();
mathService.sumOfAllConsecutiveNumbers(1000);
}
}
Implementing the factory pattern makes it a bit loosely coupled, but doesn't really take off the dependencies. Also, you would have to provide different factories for new/different implementations. This is where 'Dependency Injection' comes in handy and Google's Guice is one of the frameworks created to provide DI techniques. Below is the code, which uses 'Constructor Injection' and the Guice's 'Inject' annotation, to inject the required service, at runtime. This kind of approach is more flexible, has less code and you can bind/implement new services (or service providers) just by a minimal change in code/configuration. For the same reason, it is also easier to test the code. 'Plug n Play', 'Service Oriented Arhcitecture (SOA)', 'Webservices' come to mind, when you think about this kind of loosely coupled stuff. Below is the implementation of the client using Guice:
package com.chetty.client;

import com.chetty.service.IMathAdditionService;
import com.google.inject.Inject;

public class MathClient {
private final IMathAdditionService mathService;

@Inject
public MathClient(IMathAdditionService mathService) {
this.mathService = mathService;
}

public int sumOfAllConsecutiveNumbers(int n) {
return mathService.sumOfAllConsecutiveNumbers(n);
}
}

Apart from this, you would have to create a module (which provides/replaces the factory class implementation): MathModule:
package com.chetty.module;

import com.chetty.service.IMathAdditionService;
import com.chetty.service.SnailAdditionService;
import com.google.inject.AbstractModule;

public class MathModule extends AbstractModule {
@Override
protected void configure() {
bind(IMathAdditionService.class).to(SnailAdditionService.class);
}
}

As you see in the code above, this is the class where the required service is configured for use, by the client. In the future, if you have a new implementation for the client, all you have to do is to change the configuration. This technique sticks better to the 'Open Closed Principle', than the factory implementation. And below is the main class, where you use the Guice's injector:
package com.chetty.client;

import com.chetty.module.MathModule;
import com.chetty.service.IMathAdditionService;
import com.google.inject.Guice;
import com.google.inject.Injector;

public class MathApp {
public static void main(String[] args) {
Injector injector = Guice.createInjector(new MathModule());

MathClient mathClient = injector.getInstance(MathClient .class);

mathClient.sumOfAllConsecutiveNumbers(1000);
}
}
Ok...At some point later, I got to know a new algorithm/technique to find the sum of all consecutive integers from 1 to n. So, I want to hook up this new solution to the client, which is faster and has less code. Below is the code for that: FastAdditionService:
package com.chetty.service;

public class FastAdditionService implements IMathAdditionService {
@Override
public int sumOfAllConsecutiveNumbers(int n) {
long startTime = System.nanoTime();
int sum = (n * (n+1))/2;
long endTime = System.nanoTime();

System.out.println("Fast Addition Service - Sum : " + sum);
System.out.println("Time Complexity - O(1) and Time Taken : " + (endTime - startTime));
return sum;
}
}
All that you have to do now, is to extend the framework (but no modifications) with this new service and change the configuration in the module class (MathModule.java), as below:
bind(IMathAdditionService.class).to(FastAdditionService.class);


Looking at the Module class used for configuration, you might be wondering why we are providing configuration in a Java class, instead of the usual way of using XML or bundles/properties files.....Well, it has a reason...The reason is to provide a tight binding (for configuration) and catch all errors at compile time, so that there will be no untoward exceptions/errors on production, at runtime.

Guice Grapher - Example

Guice provides a 'Grapher' module, as an extension to its framework, to visualize the bindings and the application structure. This module is not yet available in the guice-2.0 version (and is not packed in any of the jar files of this version), but you can download the source code from the Guice's SVN repository and build it for use.

Guice's Grapher module finds all the bindings used for a particular injector and generates a DOT file (plain text graph description language). If you have already installed 'GraphViz', you can use the GVEdit.exe to run these DOT files and generate the schematic of an application using Guice's bindings.

For the example from my other post, I just copied all the sources under 'com.google.inject.grapher', built my project and ran the main java class, which looks as below:

package com.chetty.client;

import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;

import com.chetty.module.MathModule;
import com.google.inject.Guice;
import com.google.inject.Injector;
import com.google.inject.grapher.GrapherModule;
import com.google.inject.grapher.InjectorGrapher;
import com.google.inject.grapher.graphviz.GraphvizModule;
import com.google.inject.grapher.graphviz.GraphvizRenderer;

public class MathApp {
public static void main(String[] args) throws IOException {
Injector injector = Guice.createInjector(new MathModule());

MathClient mathClient = injector.getInstance(MathClient.class);

mathClient.sumOfAllConsecutiveNumbers(1000);

PrintWriter out = new PrintWriter(new File("c://MathAppGraph.dot"), "UTF-8");

Injector graphInjector = Guice.createInjector(new GrapherModule(), new GraphvizModule());
GraphvizRenderer renderer = graphInjector.getInstance(GraphvizRenderer.class);
renderer.setOut(out).setRankdir("TB");

graphInjector.getInstance(InjectorGrapher.class)
.of(injector)
.graph();
}
}


Running this class, generated a DOT file, which when opened with GraphViz's Editor, looks like:



The above pic, generated from my example project doesn't show much. So, lets use the example bundled with the Guice Source code (under 'extensions'). Using this example, the grapher modules, generates the DOT file, for the following pic: