Feed for Gebo - a blog by Madhur Tanwani

2012-12-07T23:02:00.000+05:30

http://e-banki.info/wp-content/plugins/akismet/howdoit.php

Twin Primes

2011-03-30T13:59:00.001+05:30

A Math oriented question asked at a recent Amazon interview.

Q : Given any twin prime pair, prove that the number between the twin primes is always divisible by 6.

Twin Prime (from Wiipedia) :

A twin prime is a prime number that differs from another prime number by two. Except for the pair (2, 3), this is the smallest possible difference between two primes. Some examples of twin prime pairs are (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), ... (821, 823), etc. Sometimes the term twin prime is used for a pair of twin primes; an alternative name for this is prime twin.

Panlindrome Dates

2011-03-30T13:53:00.003+05:30

Asked at a recent Amazon interview : 2001-01-02 is a palindrome date.
Find the previous closest palindore date?

Reverse words in a sentence

2010-12-12T17:50:00.000+05:30

Given an array of characters, reverse the words in the sentence.
For example, if the sentence is "Reverse these words", then the output should be "words these reverse".

Source : this interview q

Find duplicates in an array

2010-12-11T23:38:00.000+05:30

Given an array of size 'n', containing elements from 1 to 'n', find out if there are any duplicates in the array. Solve this, if

a single duplicate number exists
multiple duplicate numbers exist

Source : CLRS & this blog question (that I did not get)

Find subarray with maximum sum

2010-12-11T23:30:00.001+05:30

Given an array of size n, containing positive and negative integers, find the longest sub-array such that the sum of the elements in the sub-array is the maximum.

For example,
Given array :
10, 8, -5, 1, -27, 5, 7, -5, 11
the sub array should be : 10, 8

Source : CLRS & this sample interview question

Callbacks in Java

2010-09-03T23:18:00.001+05:30

Recently I interviewed a couple of folks. One of the guys was a C++ guy and I thought of delving into the tricky and interesting land of function pointers with him. This is when the question in the title occurred to me : How would you implement callbacks in Java?

Its nothing new, its nothing great, but I was just curious how the candidate would apply his language feature proficiency to implement a real world problem. I asked that question to that candidate and two more, after which I thought I should write this post. None of the three candidates knew how to do it. Worse one of them was completely bewildered and was like "what are you trying to say???". Damn it!!! :(.

Well here is my take on implementing Callbacks in Java. Hope you find it useful.

What are callbacks?
A callback is a paradigm by which a general purpose library can delegate (generally domain specific) parts of its execution to an external, more appropriate owner. This fits well with the "separation of concerns"process - your code will do just the work it understands.

A classic example is the sort functionality - references are available in C++, Java and other languages. The sort method, typically, would accept the list of objects to be sorted, along with an optional callback for object comparison. The sort method (the general purpose library) knows how to sort lists very well, but does not need to know the algorithm to decide the ordering of two given data objects (comparison of data objects). Since comparison of the data object (your domain specific decision) is an important part of the sorting algorithm, the sort method will allow you to specify a function that it can call when it needs to compare two of your data objects. This function is the callback.

Why the fuss?
Callbacks are great! They are means available for developers to write layers of generic code that is reusable across domains with a minimal overhead. We most certainly use callback in our day-to-day code, probably without realizing them (hence those 3 candidates). Callbacks are the backbone for various implementations - lifecycle listeners (in containers), Spring (HibernateTemplate, JdbcTemplate and more), Collections.sort(), .... the list goes on.

Nice. How are they implemented in Java?
Lets just think about it - what is the callback specifying? Its allowing the caller to specify the method to be called from the method to-be-called. This could mean, at least, two things - either the method to-be-called is given the exact callback method (within an instance / global context) OR the method to-be-called declares that it would call a specific method name with specific parameters (on the callback being passed) and its the responsibility of the caller to ensure that such a method exists in the callback object's context.

While the first approach is possible in languages like C++, the second approach fits the Java world. Another read of the second approach tells us that what we taking about is a contract - a binding that the caller must confirm to, which the method to-be-called can rely on.

In Java, how are contracts specified?? Well - by using interfaces. If the method to-be-called accepts an instance of an interface, as its callback parameter, then it will enforce the caller to implement an object that implements the methods from that interface. The method to-be-called should, however, declare beforehand which methods from the interface it would calls from within its code at what time (the contact of the methods).

Hope this brief article was helpful. For further detailed reading (specially the Command pattern usage) please refer to these links :
http://www.javaworld.com/javaworld/javatips/jw-javatip10.html
http://www.javaworld.com/javaworld/javatips/jw-javatip68.html
http://stackoverflow.com/questions/1476170/how-to-implement-callbacks-in-java

BASIC Macro To Get Stock Quotes for OpenOffice Calc

2010-08-30T19:11:00.004+05:30

I've been trying to figure out to keep track of various tips, suggestions and recommendations that various financial experts throw all the time on all the major stock market information websites. While I definitely like moneycontrol.com (for India markets), I really hate the fact that it does not allow me to track my watch list conveniently. For example, I add stock to a watch list, I enter some notes, but then those notes are not visible to me while viewing the watch list :(

Also, since what I am maintaining is a watch list, I would like to record recommended target / buy prices ad trigger alerts on those. So I came up with this small spreadsheet template that will record all this information and give a snapshot of the watch list.

The biggest blocker in this task was how to populate the "current" stock price. So, I wrote this simple BASIC Macro that, given a stock symbol, will fetch the current price of the stock. Salient points about the script :

The script was written for OpenOffice Calc, but should work in Excel as well.
The script pulls its data from in.finance.yahoo.com, but this can be replaced with the country's specific address and everything should just work fine. For example, for US market replacing http://in.finance.yahoo.com with http://download.finance.yahoo.com will work as-is.
You can also replace the source http://in.finance.yahoo.com, with something completely different (for example http://www.nseindia.com/marketinfo/equities/ajaxGetQuote.jsp), but then the parsing of the returned data will have to change.
To start using the script for your spreadsheet, do ensure that the sheetNo, c, r and destCol variables at the start of the script point to correct locations in your file.

Here is the Macro :

Sub FillStockQuotes
 Dim c as Integer, r as Integer, destCol as Integer, sheetNo as Integer
 Dim Sheet, Cell, DestCell
 Dim symbol as String

 REM Which sheet contais the above rows and columns. This is a zero based index (First sheet is sheet no 0)
 sheetNo=0
 REM Which column has the styock symbol. This is a zero based index (1st column is column no 0)
 c=1
 REM Which row has the styock symbol. This is a zero based index (3rd row is row no 2)
 r=2
 REM Which column do you want to store the quote in. This is a zero based index
 destCol=6
 
 Sheet = thisComponent.Sheets(sheetNo)
 do while true
  Cell = Sheet.getCellByPosition(c, r)
  symbol = Cell.String
  if symbol = "END OF SYMBOLS" then
   Print "Processing Complete"
   exit do
  end if
  Dim stockQuote as Currency
  stockQuote = GetSymbolQuote(symbol, Sheet)
  REM Print " " & symbol & " : " & stockQuote
  if stockQuote <> "" then
   DestCell = Sheet.getCellByPosition(destCol, r)
   DestCell.Value = stockQuote
  end if
  r=r+1
 loop
End Sub

Function GetSymbolQuote(symbol as String, aSheet as Object) As Currency

 if symbol = "" then
  GetSymbolQuote = ""
  Exit Function
 end if

 Dim sUrl As String, sFilter As String
 Dim sOptions As String
 Dim stockSymbol As String
 Dim fValue As Double
 Dim oSheet as Object, oSheets as Object
 
 sUrl = "http://in.finance.yahoo.com/d/quotes.csv?s=" & symbol & "&f=sl1"
 sFilter = "Text - txt - csv (StarCalc)"
 sOptions = "44,34,SYSTEM,1,1/10/2/10/3/10/4/10/5/10/6/10/7/10/8/10/9/10" 
 
 oSheet = createSheet(thisComponent.Sheets)
 oSheet.LinkMode = com.sun.star.sheet.SheetLinkMode.NONE
 oSheet.link(sUrl, "", sFilter, sOptions, 1 )
 
 stockSymbol = oSheet.getCellByPosition(0,0).String
 fValue = oSheet.getCellByPosition(1,0).Value 

 GetSymbolQuote = fValue
End Function

Function createSheet(oSheets as Object)
 Dim oSheet as Object
 
 If oSheets.hasByName("Link") Then
  oSheet = oSheets.getByName("Link")
 Else
  oSheet = oDocument.createInstance("com.sun.star.sheet.Spreadsheet")
  oSheets.insertByName("Link", oSheet)
  oSheet.IsVisible = False
   End If 
   
   createSheet = oSheet
End Function

Using ProxySelector to take control of what proxies to use and when

2010-05-28T20:06:00.015+05:30

While helping some developers work with a code that I wrote, that used HttpClient, I was confronted with this problem : their existing code requires to work with a socks proxy, while the functionality that my code was providing would not work if sitting behind a proxy. The JVM was instructed to use socks via the socksProxyHost property.

After reading this excellent guide on proxies in Java, I decided to try using the ProxySelector mechanism. The results were awesome!!

Using ProxySelector gives us the flexibility to :

decide whether a proxy should be used or not for a URI being connected to. You can choose not to use a proxy altogether.
specify what proxies (yes multiple!) to use - including varying protocols in each proxy
manage failures when connecting to proxy servers

So here is what I did :

Extended a new class from Java's java.net.ProxySelector
The select method of this class (which is an override of the abstract method from the ProxySelector class), would be called each time Java tries to make a network connection - querying for the proxy to be used for that connection. The URI being connected to is passed to the method. I checked the attributes of this URI and if matched the hostname that my code used to connect to (which did not work via a proxy), I returned a java.net.Proxy.NO_PROXY to signify that no proxy should be used for this URI.
For all other URIs, I did not want to fidget with the user's settings, so I delegated the proxy decision making to the default ProxySelector that ships with Java

Let me put out the code I used to experiment this and everything should be crystal clear :

/**
 *  Created by : Madhur Tanwani
 *  Created on : May 28, 2010
 */
package edu.madhurtanwani.net;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.Proxy;
import java.net.ProxySelector;
import java.net.SocketAddress;
import java.net.URI;
import java.util.ArrayList;
import java.util.List;
import org.apache.commons.httpclient.HttpClient;
import org.apache.commons.httpclient.methods.GetMethod;

/**
 *
 * @author Madhur Tanwani (madhurt@yahoo-inc.com)
 */
class CustomProxySelector extends ProxySelector {

    private final ProxySelector def;

    CustomProxySelector(ProxySelector aDefault) {
        this.def = aDefault;
    }

    @Override
    public List<Proxy> select(URI uri) {
        System.out.println("select for URL : " + uri);

        if ("http".equalsIgnoreCase(uri.getScheme()) || "socket".equalsIgnoreCase(uri.getScheme())) {

            if (uri.getHost().startsWith("mail")) {
                List<Proxy> proxyList = new ArrayList<Proxy>();
                proxyList.add(Proxy.NO_PROXY);
                System.out.println("NO PROXY TO BE USED");
                return proxyList;
            }
        }

        //Proxy proxy = new Proxy(Proxy.Type.SOCKS, new InetSocketAddress("socks.corp.yahoo.com", 1080));
        List<Proxy> select = def.select(uri);
        System.out.println("Default proxy list : " + select);
        return select;
    }

    @Override
    public void connectFailed(URI uri, SocketAddress sa, IOException ioe) {
        throw new UnsupportedOperationException("Not supported yet.");
    }
}

/**
 *
 * @author Madhur Tanwani (madhurt@yahoo-inc.com)
 */
public class Socks_Public {

    private static final String URL_BEHIND_SOCKS = "http://yahoo.com";
    private static final String URL_NO_SOCKS = "http://mail.yahoo.com";

    public static void main(String[] args) throws Exception {
        ProxySelector.setDefault(new CustomProxySelector(ProxySelector.getDefault()));

        System.out.println("\n\n++++++++++++++++++++USING HTTP CLIENT++++++++++++++++++++");

        HttpClient client = new HttpClient();

        System.out.println("\nURL : " + URL_NO_SOCKS);
        GetMethod get = new GetMethod(URL_NO_SOCKS);
        int response = client.executeMethod(get);
        System.out.println("Response code : " + response + " , Response : " + get.getResponseBodyAsString().substring(0, 50));

        System.out.println("\nURL : " + URL_BEHIND_SOCKS);
        get = new GetMethod(URL_BEHIND_SOCKS);
        response = client.executeMethod(get);
        System.out.println("Response code : " + response + " , Response : " + get.getResponseBodyAsString().substring(0, 50));


        System.out.println("\n\n++++++++++++++++++++USING JAVA URL CONNECTION++++++++++++++++++++");

        System.out.println("\nURL : " + URL_NO_SOCKS);
        URI uri = new URI(URL_NO_SOCKS);
        InputStream is = uri.toURL().openStream();
        BufferedReader rdr = new BufferedReader(new InputStreamReader(is));
        for (int i = 0; i < 2; i++) {
            System.out.println(rdr.readLine());
        }
        is.close();


        System.out.println("\nURL : " + URL_BEHIND_SOCKS);
        uri = new URI(URL_BEHIND_SOCKS);
        is = uri.toURL().openStream();
        rdr = new BufferedReader(new InputStreamReader(is));
        for (int i = 0; i < 2; i++) {
            System.out.println(rdr.readLine());
        }
        is.close();
    }
}

And here is the output of the code run :

++++++++++++++++++++USING HTTP CLIENT++++++++++++++++++++
URL : http://mail.yahoo.com
select for URL : socket://mail.yahoo.com:80
NO PROXY TO BE USED
select for URL : socket://login.yahoo.com:443
Default proxy list : [SOCKS @ socks.corp.yahoo.com:1080]
Response code : 200 , Response : 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01

URL : http://yahoo.com
select for URL : socket://yahoo.com:80
Default proxy list : [SOCKS @ socks.corp.yahoo.com:1080]
select for URL : socket://www.yahoo.com:80
Default proxy list : [SOCKS @ socks.corp.yahoo.com:1080]
Response code : 200 , Response : <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN"


++++++++++++++++++++USING JAVA URL CONNECTION++++++++++++++++++++

URL : http://mail.yahoo.com
select for URL : http://mail.yahoo.com/
NO PROXY TO BE USED
<!-- l03.member.in2.yahoo.com uncompressed/chunked Fri May 28 20:32:24 IST 2010 -->
null

URL : http://yahoo.com
select for URL : http://yahoo.com/
Default proxy list : [SOCKS @ socks.corp.yahoo.com:1080]
select for URL : http://www.yahoo.com/
Default proxy list : [SOCKS @ socks.corp.yahoo.com:1080]
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN"
   "http://www.w3.org/TR/html4/strict.dtd">

Mock, Mock... who's that? (Part 2)

2010-05-04T18:23:00.011+05:30

Starting off where I left my first introductory post of this series - so I chose Mockito as my mocker. What next?

The Requirements For Mocking
Following are the requirements that we wanted to fill up (for starters). Though these requirements are specific to mine, I'm sure almost every project would have the same / similar mocking requirements :

Objective : The most important point of using mocking frameworks was to emulate certain behaviour from instances of external dependencies.

Lets continue with this example :

+--------------------------------------------------+
| MyLoginService --uses--> BackendAuthService |
|                                    |             |
|                             authenticates via    |
|                                    |             |
|                                    v             |
|                                DataSource        |
+--------------------------------------------------+
Here the objective is to unit test MyLoginService's login API, which in its integration environment would talk to multiple backend services.
Lets assume that the BackendAuthService has an API named login, which accepts a custom class object. This custom class object contains the details of the credentials to authenticate.
Further, lets say this API returns another custom class object which is the authenticated token after successful authentication. Also, if the authentication fails when this API throws an exception.

Independence : While unit testing (in my Dev or on the continuous integration farm), I cannot expect the backend services to be available / functional. Hence, unit testers will choose to mock-out the behaviour expected from these external dependencies.

Note that this implies that the developer first needs to know possible behaviours exhibited by these dependencies (SuccessCase1, SuccessCase2, FailCase1, FailCase2, ExceptionCase1, ....).
Then s/he should code the unit test case, such that when the external dependencies are called / invoked, they exhibit the behaviour the unit test case is supposed to test.
Generally, there would be at least one unit test case for each expected scenario. In addition there would be negative test cases as well.
A point to explain what I mean by "mock-out the behaviour". In the above example, for a positive test case, we need (to simulate) the backend service returning a valid authenticated token, signifying successful authentication. Using the mocking framework, we can induce this simulation on the backend service instance.

Integration : Moving on, the production code uses implementation classes injected via a Spring(-like) framework. So there are configuration files where mappings are defined, injection customizations and finally, instance look up code.

Modifying the production code flow, for adding any unit testing capability is forbidden.
Hence, we want to re-use the injection framework, configuration files and the same instance look up code, to seamlessly work while unit testing.

Thread Safety : We wanted to be able to run unit tests in parallel. This is very easily possible via TestNG, in addition to the load of unit test features it provides. In a typical production environment, all instances of these external dependencies are expected to be thread safe. Obviously, we want that behaviour to remain even in the mocks.
Distinct behaviour per thread : In spite of requirement (4), since every thread in the unit test case would be a test for a different scenario, a developer would want each mock for each test case to behave differently. So though we want thread safety, we also want the mocks to behave differently in each thread.

Cool! So we now know what we want to do. Moving on to how it was done.

Approaches Possible
Before I explicitly state the solution we adopted, I want to discuss the various possibilities we considered. This section talks about those.

Spring supports two bean scopes by default for standalone applications - prototype and singleton (default). What we needed was a way to define mock implementation classes in the spring configuration, such that each thread would have its own mocked instance - basically thread scope. This way the thread safety of the mocked instance and different-behaviour-per-thread requirements can be achieved.

One way out here was to define a custom scope in Spring. (see also the SimpleThreadScope class in available in 3.0.x version).
Another way out is to ask Spring to use factories for bean creation and then take control over this aspect by implementing a factory.

We wanted the capability to choose / change mocker implementations in the future. Hence, we wanted control over the way these mock objects were created / initialized / refreshed etc... - so we wanted to implement the factory that Spring would turn to for bean instance creation.

Spring provides a convenient way to do this - using FactoryBeans. By implementing FactoryBean interface, we can write a factory class that will generate beans as well as control singleton behaviour.
Other methods using instance factories and static factories are also possible

Approach Implemented

Use an implementation of Spring's FactoryBean to serve as a factory for creating beans. This implementation, lets name it MockServiceLookUp, will be called whenever the code flow requests for some bean.
The MockServiceLookUp implementation is responsible for creating mocked instances for the class that is being looked up - one instance per thread.
The MockServiceLookUp implementation will rely on the use of a MockProvider to create actual mock objects. The MockProvider is the class that will actually use the mocker library to create mocks.

Ideally, MockProvider should be an interface, with multiple implementations for each type of mocker you want to support (so that those can be plugged in as needed).
Alternately, MockProvider can be skipped completely and the mocker library can be used in the look up implementation to create mock instances.

For every look up request, the MockServiceLookUp will first check whether a mock implementation for the class being looked up exists in its ThreadLocal. If it does, the instance is returned, otherwise the MockProvider is consulted.

The general case is that unit test will fetch the mock instance for a class that the actual code the unit test is for will be using. Then the unit test would "apply" behaviour mocking on this instance (i.e. behavior stubbing) and finally call the actual API to test.
Since the API would also look up the same class from Spring (which in turn will request MockServiceLookUp for the instance), the API would get a mock instance with appropriate methods stubbed. These methods would be those that the unit test expects the API to call on the backend/dependency. Hence, the unit test would be complete.

Finally, the MockServiceLookUp also provided for a "clear all" API to erase all the stubbing performed on the mock instances in its ThreadLocal.

This was a useful API for us - to start afresh from within a unit test - where we wanted to discard all previous stubbing
This API was also called by default from out unit testing infrastructure whenever a new unit test case started - hence ensuring all unit tests started clean.

Conclusion
This is what the mock framework class diagram (taken with permission - thanks to my colleague Siju) is like :

Finally, a unit test would run like this :

Unit Test Case Start
Use Spring to fetch the implementation for BackendAuthService.

Spring would invoke the MockServiceLookUp's getObject() API to get the implementation of BackendAuthService.
MockServiceLookUp would first check if an existing implementation of the class exists already, in its ThreadLocal. If this is the first getObject call for this class, then the mock method of the MockProvider is called. Otherwise, the mock instance from ThreadLocal is returned.
The MockProvider will use Mockito to create the mock instance of the specified class.

The unit test will override the behaviour of the BackendAuthService's login API

The behaviour override can be to return valid values (auth tokens) or invalid values (excetpions, errors, invalid auth tokens) depending on what is being tested

Then the test would make a call to MyLoginService's login API

This implementation would again request Spring for the implementation of the BackendAuthService class, which this time will be the stubbed mock instance.
When the login API on BackendAuthService is called the stubbed code executes returning the auth token / exception.

After the API call completes, the unit test must verify that the auth token returned is valid or not (or if an exception was excepted, whether it was thrown or not).
Unit Test Case End

Hope this post has helped you understand how "instances" of classes are mocked and injected into production code, in a distinct-behaviour-per-thread manner. Good luck with mocking!

Three Distance Theorem

2010-05-04T14:14:00.000+05:30

While learning from this video lecture by Steve Skiena on Discrete Mathematics, he explains the Three Distance Theorem (at time 37:32).

The Three Distance Theorem goes like this :
For any irrational number 'a', if the sequence of points {i*a}, where 0 <= i <= n, are plotted on a unit distance / circle (wrapped at unit distance), then :

The points divide the circle / line into n+1 distances
The maximum number of distinct distances defined is 3
The minimum number of distinct distances defined is 2
Of the three distinct distances, one is a sum of the other two

Here is a single page PDF explaining the theorem nicely : http://myweb1.lsbu.ac.uk/~whittyr/MathSci/TheoremOfTheDay/NumberTheory/ThreeDistance/TotDThreeDistance.pdf

The findings are really awesome - as Prof Skiena explains and proves the theorem in the lecture.

Application To Hashing
I think because of the distinct distance generation property of the theorem, the theorem can be an effective way to avoid collisions by the basic multiplication method. Ofcourse the other limitations of open addressing apply, but if that approach is chosen, this theorem might be helpful.

The basic idea for collision resoluton would be hashing in this order :

h(k, 1) = H(K*1*a)

h(k, 2) = H(K*2*a) ...
where
h(k, l) - hash for the key k, being hashed for the lth time
k - key to insert / lookup
a - an irrational number
1, 2 - the first, second lookup. The l+1th lookup should be performed only if lth lookup had a collision

Tower of Hanoi with a restriction of no direct transfers

2010-05-03T20:40:00.003+05:30

We need to solve the Tower of Hanoi problem, with this additional restriction : direct moves between the origin and destination towers is disallowed. All other restrictions still apply as-is.

For example, if a single disk is to be moved from Tower A to Tower B (using Tower C), then moving the disk directly from A to B is not allowed. The disk must be first transferred to Tower C and then to Tower B.

The purpose is to find the shortest sequence / number of moves we can do this in :

T(0) = 0 (basis case, nothing to move)
T(1) = 2 (from above)
T(n-discs) = ???

Source : Concrete Mathematics (2nd Edition) Ex. 1.2

Find the summation of first 'n' odd numbers

2010-04-16T19:02:00.005+05:30

Find a simple formula for the summation of the first 'n' odd numbers (1, 3, 5.....).
More formally, find a general solution for :
n
Σ (2k-1)
k=1

Source : CLRS A.1-1

Road Trip To Brindavan Garden

2010-03-08T22:55:00.006+05:30

Hola! Sunday afternoon and nothing else to do (except a code commit and few distribution builds) we decided to take a trip the famous Brindavan Gardens built next to the KRS Dam @ Mandya.

Check the petrol, check the tyres and off we were. We started from Old Madras Road (Bangalore) @ 2:30 PM and swearing on the Bangalore roads and traffic subdued when we reached the Mysore highway at about 3:45 PM. Phew!

After that it was a wonderful road (minus those @#!$*@ speed breakers that stopped me from touch 110 kmph) all the way till Mysore. We finally reached the Brindavan Gardens at 6:30 PM - just in time for the entries to start.

We quickly bought ticket (INR 15 per person, INR 50 per camera) and rushed into a huge line for the entry. The lights were already on and the excitement to see the musical fountains was at its peak.

Its a long walk to the musical fountain and by the time we reached there, one round of the show had ended.I clicked the beautifully landscaped garden in the mean time - its awesome to see!!

When the music started again, we rushed to the place. I must say I was a little disappointed by the show, maybe because of my high expectations from all the hype, but I'm sure better music and better fountain synchronization can be achieved. That apart, it was a good show - specially when the water reaches the peaks - its great then!

After the show we returned to the other side of the garden (towards Hotel Orchid), that's on the other side of the walking bridge. I like this part the most - it was calm, had lots of places to sit, no people rush this side, lots of nicely laid fountains and water paths. I loved this place!

We walked all the way upto the Orchid Hotel - the view from the top is amazing!! Finally, I ran out of batteries, most of the garden was clicked and it was almost 8:30 PM - so we decided to head back home,

We reached home @ 12:00. Very tired I finished the code commits and disted the builds - may the Force be with the QA team ;-).

This was one hell of a trip - I loved it!! Some photos and videos from the trip :

Mock, Mock... who's that? (Part 1)

2010-03-03T02:23:00.002+05:30

Let me begin with this quote from Martin Fowler's post :

The term 'Mock Objects' has become a popular one to describe special case objects that mimic real objects for testing. Most language environments now have frameworks that make it easy to create mock objects. What's often not realized, however, is that mock objects are but one form of special case test object, one that enables a different style of testing.

Mocking - huh?
This post series is not to explain / debate on mocking and stubbing test strategies. If you are interested in reading what mocks are, why to use them and so on, please refer to the following links :

This article by Martin Fowler describing mocks, stubs their differences and test strategies.
Mock Objects article on Wikipedia - an excellent starting point.
MockObjects.com - A site dedicated to mock objects!

If you have decided to take the mock path and are interested in how to use mocks, please read on. Here is my agenda on covering what I've learned from my project's mock testing efforts :

Mocking libraries and comparison. What I've finally used and why
Mocking of instance functions, in a thread safe manner
Mocking of static functions, in a thread safe manner
Mocking of static getInstance() / factory methods, in a thread safe manner

Though my mock usage examples would be in Java, most of the concepts can be used across languages. So, here we go...

Mocking libraries and comparison
There are multiple library projects that offer mocking and stubbing functionality. The number of choices are overwhelming and its often difficult to decide what's the right one to choose. For starters, simple dynamic proxy or sub-classing "mockers" would be just fine. For advances usages, "mockers" with greater benefits - probably state maintenance, static mocking would be useful.

A comparison of currently available mock libraries can be found here :

JMockit documentation recently hosted an exhaustive comparison matrix recently.
A comparison by Vasily Sizov on his blog from March 2009.
StackOverFlow.com users had this great discussion over mock library choices

Our initial set of candidates included EasyMock and Mockito. Though JMockit sounded very tempting, due to lack of documentation (about 4 months back - though its improved quite a lot now) we did not want to adopt it - or so we thought.

EasyMock and Mockito are both very easy to code to and it was a tough call which one to use. Finally, multiple team members got their hands dirty using the two libraries and we voted. The winner was Mockito - we simply loved its documentation (everything was just there) and the extensibility for mocking behaviors. I have been happily mocking using Mockito since then - here I have use and like about Mockit :

unlike EasyMock, Mockito is not a "record-n-play" mocker. You mock out what is necessary, when it is necessary, make unit test API calls and then verify expectations - all on demand.
behavior mocking is very simple, written like English sentences in code : when(BasicService.foo()).thenReturn(retval);
throwing exceptions, tracking number of calls made was possible and easy
the return values from mock methods can be customized using the API call parameters.
verification of mocked behavior is easy. Though there is no auto-verification feature.

Hope this post will help you find your mocker. I will follow up with more posts on how we used mocks in a thread safe manner, injected them into Spring and how mocking static functions made us use a mix of Mockito and JMockit :). Stay tuned!

Hilarious Strips from xkcd

2010-03-02T01:40:00.001+05:30

After reading this hilarious suggestion, I fooled around to find some more :

Zealous Autoconfig

Unimodal Search

2010-01-11T22:58:00.001+05:30

An array A[1...n] is unimodal if it consists of an increasing sequence followed by a decreasing sequence. More precisely, if there is an index m in {1, 2, ... n} such that
A[i] < A[i+1] for 1 <= i < m and
A[i] > A[i+1] for m <= i < n

In particular, A[m] is the maximum element, and it is the unique "locally maximum" element surrounded by smaller elements.

Give an algorithm to compute the maximum element of a unimodal input array A[1...n] in O(lg n) time.

Source: Problem 1-3.from MIT OpenCourseWare Course - 6.046J / 18.410J Introduction to Algorithms (SMA 5503)

100 Switches & 100 bulbs

2010-01-11T00:11:00.000+05:30

There are 100 switches in a room operating 100 bulbs. At iteration '0' all switches are OFF. For every iteration 'i', all switches that are multiples of 'i' are toggled (turn OFF if ON, turn ON if OFF).

You need to find the state of the 'k'th switch/bulb (1<=100) after the 'i' th iteration

Expected O(1) time and space complexity.

[ALGO] Is Binary Search Tree

2009-12-02T00:02:00.002+05:30

Given a binary tree, verify if it is Binary Search Tree

[ALGO] Find the string in 2 dimensional matrix

2009-12-01T00:01:00.002+05:30

Given a 2-dim matrix of characters 'm' and a string 's' - find if the string 's' is present in the matrix. Only characters in the neighboring cells of a cell can contribute to the string.

For example, for the case below B,D,F,G are neighbors of X. From 'X' possible strings (or substrings) are XB, XD, XF, XH.
|-----|-----|-----|
| A | B | C |
|-----|-----|-----|
| H | X | D |
|-----|-----|-----|
| G | F | E |
|-----|-----|-----|

Finally, an example. Given the matrix

(0,0)
    |-----|-----|-----|-----|
    | y | a | a | o |
    |-----|-----|-----|-----|
    | a | o | a | o |
    |-----|-----|-----|-----|
    | y | a | o | o |
    |-----|-----|-----|-----|
    | h | a | a | o |
    |-----|-----|-----|-----|
    | y | a | h | o |
    |-----|-----|-----|-----|
                          (3,3)

and asked to check for the string 'yahoo' the solution is true :
y - (3,0)
a - (3,1)
h - (3,2)
o - (3,3)
o - (2,3)

[ALGO] Random number generator, with equal probability

2009-11-30T23:43:00.002+05:30

RANDOM(a.b) is a random number generator that generates integers between a and b (inclusive), all equally likely.

Assuming we have an implementation of RANDOM(0.1), how can we implement RANDOM(a.b) - i.e. given we have a function that returns 0 OR 1 both with a probability of 1/2, how can we implement a function that returns integers from a to b (b > a), all with a probability of 1/n, where n = (b-a+1)

Source : Cormen - Problem 5.1-2 (randomized algorithms)

Similar problem :
At a restaurant, how can Veronica choose one out of three desserts with equal probability with the help of a coin?

Its on Gurmeet's site here http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-tossing-with-one-third-probability/

Things To Do...

2009-11-08T23:03:00.002+05:30

I recently attended a Spring training by SpringSource. While learning the framework and admiring its features, it prick me that there is a LOT that I don't know and have to gather.

So, after a long time I'm starting this post, that I anticipate to update regularly with things I want to do, things I want to learn and things I want to talk about.

Expect one blog title for each entry in this list. So, here I go :

P1: Spring - an E2E tutorial - put to use all the learning from the training into a live example.
P2: OSGi - post an article listing resources I read to understand OSGi. Maybe with a few self comments
P?: Groovy - I really loved the way Groovy scripts helped code Java applications quickly. I'm going to try them out
P?: Grails - Another quick build of a web application. I'm going to try this out too.
P?: Castor - Data binding framework : http://www.castor.org/
P?: JBoss Seam
P?: Spring Roo : http://en.wikipedia.org/wiki/Spring_Roo
P2: Why should one refrain from using Stubs and prefer using XPath for Web service implementation (server side)
P2: Code-first VS contract-first approach for webservices
P?: The JSF standard
P2: Distributed transactions - an interesting concepts / field. How about starting here : Distributed transactions in Spring, with and without XA
P2: Java Persistence API : https://glassfish.dev.java.net/downloads/persistence/JavaPersistence.html
P?: JDO : http://java.sun.com/jdo/
P2: JSR-250 Common Annotation
P1: Introduction to Algorithms @ MIT Open Courseware - http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm
P?: A course / reading on OOAD, Systems Analysis, Design
P?: Machine Learning Modeling Algo : Linear CRF - What? How?

.... (To be continued...)

Walk the bridge, in pairs as fast a possible

2009-09-06T16:05:00.003+05:30

There are 4 women who want to cross a bridge. They all begin on the same side. There is one flashlight. A maximum of two people can cross at one time. It is night. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross
Woman 3: 5 minutes to cross
Woman 4: 10 minutes to cross

For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission.

Find jar with the contaminated pills

2009-09-06T15:55:00.002+05:30

You have 4 jars of pills. Each pill is a certain weight, except for contaminated pills contained in one jar, where each pill is weight + 1. How could you tell which jar had the contaminated pills in just one measurement?

Source : http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm

Algorithms from "100 Interview Questions for Software Developers" : Part 3

2009-09-05T23:46:00.003+05:30

Find repeating element in array

I felt this question deserves a post of its own. So here it is :

Q5. In an array from 1 to n, one number is present twice. How to do you determine which one?

There are multiple answers - all correct. We would, obviously, aim for the optimized one - benchmark parameters being time & space complexity

Source : Algorithms from 100 Interview Questions for Software Developers