Find subarray with maximum sum

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

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

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 :

1. The script was written for OpenOffice Calc, but should work in Excel as well.
2. 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.
3. 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.
4. 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

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 :

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

So here is what I did :

1. Extended a new class from Java's java.net.ProxySelector
2. 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.
3. 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)

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 :

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.

1. 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.
2. 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

1. 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.
2. The MockServiceLookUp implementation is responsible for creating mocked instances for the class that is being looked up - one instance per thread.
3. 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.
4. 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.
5. 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

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 : 

1. The points divide the circle / line into n+1 distances
2. The maximum number of distinct distances defined is 3
3. The minimum number of distinct distances defined is 2
4. 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

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