Find the summation of first 'n' odd numbers

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

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)

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 :

1. Mocking libraries and comparison. What I've finally used and why
2. Mocking of instance functions, in a thread safe manner
3. Mocking of static functions, in a thread safe manner
4. 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 :

1. JMockit documentation recently hosted an exhaustive comparison matrix recently.
2. A comparison by Vasily Sizov on his blog from March 2009.
3. 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

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

Zealous Autoconfig

Unimodal Search

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

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

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