Alogorithm: Finding Longest Increasing Subsequence using Patience Sort in C#

Finding the Longest Increasing Sequence is an interesting problem and there are multiple solutions available with varying time complexity. The solution that i plan to share today is the uses of Patience Sort  to find such a sequence. The solution finds a particular longest increasing sub-sequence as the original sequence may contain more than one such sequence.

In 1999 The Bulletin of the American Mathematical Society published a paper by David Aldous and Persi Diaconis entitled: “Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem”.

I have implemented this solution in C# and derived it from this excellent article which provides a Python implementation for the same.

This is how patience sort works

• Take a deck of cards labeled 1, 2, 3, … , n. The deck is shuffled, cards are turned up one at a time and dealt into piles on the table, according to the rule
• A low card may be placed on a higher card (e.g. 2 may be placed on 7), or may be put into a new pile to the right of the existing piles.
• At each stage we see the top card on each pile. If the turned up card is higher than the cards showing, then it must be put into a new pile to the right of the others. 

I have left out the part that returns the sorted list of numbers as it is not relevant for the longest sub-sequence problem.

The first thing to note here is

Once the cards\numbers are organized into piles. The total number of piles denote the size of longest sub-sequence.

 To get the longest sequence some extra book keeping is required. According to the paper

    Lemma 1. With deck π, patience sorting played with the greedy strategy ends with exactly L(π) piles. Furthermore, the game played with any legal strategy ends with at least L(π) piles. So the greedy strategy is optimal and cannot be improved by any look-ahead strategy.

    Proof. If cards a1 < a2 < … < al appear in increasing order, then under any legal strategy each ai must be placed in some pile to the right of the pile containing ai-1, because the card number on top of that pile can only decrease. Thus the final number of piles is at least l, and hence at least L(π). Conversely, using the greedy strategy, when a card c is placed in a pile other than the first pile, put a pointer from that card to the currently top card c′ < c in the pile to the left. At the end of the game, let al be the card on top of the rightmost pile l. The sequence a1 ← a2 ← … ← al-1 ← al obtained by following the pointers is an increasing subsequence whose length is the number of piles.

What this means is whenever a card is added to a stack (except first stack), the card should keep a back pointer to the topmost card on the pile on the left.

To get a better understanding of the above logic, i have created a diagram detailing the links that get created during the patience sort process for the list of numbers

31,16,7,39,5,12,32,18,9,1

The longest increasing sub-sequence using the above algorithm is

5,12,18

The gist for the implementation is available here

Caching Images downloaded from web on Windows Phone Isolated storage

I was helping on a Windows Phone application where the requirement was to cache the images the phone downloads on the isolated storage for offline viewing.
I wanted a solution which was simple and as transparent as possible. While researching I found  someone wrote a Silverlight converter for loading images from isolated storage. Taking that as a base I created a converted which can

1. Load image from web (http + https), and persist it to isolated storage.
2. In case of network connectivity issues can load the same image from isolated storage. It does that by mapping the http url to a isolated storage location.
3. In case the network is down and the image is neither there in cache, loads a default image, passed as parameter to converter.

Here is the gist for the implementation.


To use the converter

1. Import the name space.
2. Declare the converter as resource.
3. Set the Image Source Property to use this converter like this 

Architect? Give me a break :)

Davy Brion has posted some rants about the Microsoft MVP program and the type of people that are attracted to it.
What David has mentioned holds true in some other areas of IT industry too.
"Architect" another cool but severely abused title :) If you take David's post and replace "Microsoft MVP" with the word "Architect" you would find everything still holds true. I am a strong believer that "Architect" as a designation\title should be done away with.

In my 8+ years of IT experience I have seen quite a few of this breed :) With exception of few I found most of them just good with

• UML modelling tools (such as Visio)
• Generating high quality project artifacts (Such as Function Specs, Design documents)
• Buzz word mongers.
• Smooth talkers

These maybe important qualities to have in an Architect but a sound technical background is a non negotiable. Everyone knows what is the end result if you engage such people. Such Architects mostly produce things that look impressive on paper but implementing them most often then not becomes infeasible.

Well, its not the Architects fault always. In a typical engagement this is how the Architect works. At the start of the project the Architect

1. Understands the problem domain.
2. Talks to the client coming up with a solution approach.
3. Shares the solution approach with the client and key stakeholders.
4. Gets their feedback.
   
5. and finally creates artifacts for the team to get started.

What starts of as a full time gig for the Architect, gets reduced to a advisory role as the project progresses. And after some time the Architect is gone, entrusting people like us the responsibility of implementing their grand vision. This is where I believe the problem lies.

When we are working in an Agile age where requirements evolve, designs evolve, technology evolves, mandating a design at the start of the project is incorrect. The time where Architectural decisions are made, are times of maximum uncertainly as the project is getting off ground. What ends up happening is that Architectural document\guidelines gets sidelined and the solution evolves based on what the immediate requirements are. This is shear waste of resources.

There is another problem with this approach. Where is the accountability? If I am not going to develop something I am architecting \ designing, I can virtually propose anything. Literally anything !! If things work out fine I can always take the credit else I can always pass the blame to others. Works well for me! I can keep on doing that project after project and keep going up in the organization ladder, with virtual little or no real contribution to any project I work on.

At the end I am not going to present any solution for this situation but point my readers to an excellent presentation by Simon Brown where Simon discusses the role of the software architect, challenging some of the current assumptions and trying to redefine it in the context of Agile development. 

So you got a job offer !!!

So you got a job offer !!! It always a great feeling irrespective of ones experience level. You start envisioning about your fatter pay-cheque, your role, your growth prospects, may be a new city (in case you are transferring).  During this euphoria we may throw caution to the wind and not do a thorough check about the organization, type of work, work culture. The consequence of our carelessness can cost us, sometimes dearly.

Through this post I just want to highlight things one should consider while looking out for jobs and while accepting any job offer. Since i am an IT professional i can and would only talk about IT companies and jobs.

• Product Company vs Services Company: Many may not have any preferences on this but this distinction has an affect. Services company is all about billing and one almost always works under deadline pressure, delivery pressure. The story is different in product companies where activities revolve around the product. Time to market is important in product development organizations too but not as important as services organization.


• Company's IT division vs Pure IT company: If you are driven by technology,  IT division within a large organization may not suite you. One needs to understand, non IT companies are driven by business needs not technology needs. As always there are exceptions to this rule too, but one should be aware of this.

• Background Check: Background check is very important before you accept any offer or join a company. Try to extract as much data about the company's background, the type of work it does, the work culture, company policies. Some of the avenues for such research are 
• Your Friends: Check with you friends, and try to see if someone has some experience with the company. Many a times you friend may get you connected to someone who can help you better in the research.
• LinkedIn: LinkedIn is a professional network, where one can find about any company, it's current and previous employees. There is a wealth of information available on LinkedIn. You can look for your connections within the company. You could find 1st, 2nd or 3rd level connection, so go ahead and leverage these connections. Try to gain insight into the company. If possible find connection who have been past employees with the company. 
• Company Review Sites: I know about two such sites www.jobeehive.com and www.glassdoor.com. Check if someone has posted reviews about the company. Number may not be reliable but if there is a general trend of low numbers and bad reviews, that is a clear RED flag

• Interview Process: The complete interview process is about selecting\rejecting a candidate. The company assess a prospective candidate through these interviews. What we may not realize is that, other way round is also true. Interviewing is a good time for us to judge the company as well. While interactive with the company employees we can get a fair idea about their talent base, their culture. Some of the things that should make you circumspect
• Having things too easy: A good company tried to push the candidate to his limits. They don't want to make things easy for you. Always strive to work with people who are smarter than you. If the interview was too easy for you that may mean you are over qualified for the job.
• Having Single Technical Round: Unless you are directly interview by Director, CEO, CTO etc, single technical round selection is strictly no no.Good companies do not rely on single person feedback. The more the merrier. 

This is what I have currently. I would continue to update this list over time. I want this list to be exhaustive collection of tips\links that highlights what to check for in ones prospective employer.

Case of missing Iron Foundry VMC client

While installing the latest Iron Foundry VMC client and Cloud Foundry Explorer there is an installation issue. Due to this VMC client install gets lost if both the VMC Client and CF Explorer are installed irrespective of the location of the install.

As it turns out, if you install VMC client first and CF Explorer next, installer would delete the VMC install directory.

If you install CF Explorer first and try to install VMC client later you get this error

"This version or newer version of VMC Command Line Tool is already installed." 

Current workaround would be copy the installed folder for VMC before starting CF Explorer install.

Hope it helps.

NoSQL Data Modelling

Recently in one of the project we planned to use some NoSQL  Document database. One of the reasons we though document database would be a great fit was that we could get started without setting up any DB schema and start shoving entities into the document database.
Nothing can be further from the truth. Data modeling is as essential and as fundamental an exercise for NoSQL stores as it is for RDBMS. It is just that the concepts are different as compared to RDBMS where normalization\de-normalization provide some guidance. In my pursuit to understand how to model data for a document database i came across some great reference material that i want to share here.

• MongoDB Schema Design : Great resource from MongoDB. Start with this one first.
• MongoDB Data Modeling: A quick read but explains some important concepts related to modelling. Embedding vs Linking.
• MongoDB Data Modeling and Rails: Covers an example to make things more clear.
• NoSQL Data Modelling Techniques: A great post that explains about data modelling techniques for all NoSQL type stores.

I believe that is enough content for one to have a decent understanding on the topic and get going with the real modeling.

Trying to make sense of REST (over HTTP)

People who come from WCF/ Web Services background and  transition to RESTish type communication infrastructure make mistakes that follow a common pattern. I have seen it with people who are new to REST and with people who have spent some time working with RESTful services. (Throughout the post where every I mention REST I mean REST over HTTP)  The common misconceptions  are

• Not understanding the difference between HTTP POST and GET, in fact having too little or no clue about HTTP Verbs. For most devs interaction with server involves calling a client proxy method, handling the request on server, sending a response back from server, handling the response on client. This abstraction means no one knows what happens at infrastructure level. When programming for HTTP one cannot ignore the abstraction, else we cannot take full advantage of the medium.

• The manifestation of the above affect is, either every call becomes a POST or every call becomes a GET.

• When every call becomes GET. All CRUD are done through url. I have seen people trying to do crazy stuff with urls just to pass data from client to server.
• When every call becomes POST (easy to do as compared to GET) , we fail to leverage the advantages of GET.

• Assuming making HTTP call via GET\POST makes a service RESTful. This is a very common misconception and I too am culprit of thinking the same. But as I read more about REST and looked at examples I realize how far was I from a real RESTful implementation. I highly recommend REST In Practice book which is a great resource if one is serious about understanding REST.

• Thinking the performance gains comes due to absence of SOAP envelop. The real performance gains come when data gets cached.  This caching can occur at different locations starting from the servers network (reverse proxies), intermediaries, client network  (proxies) and client browser.

• Creating RESTful service and marking most of GET's as non cacheable. The common cause of this is not understanding the cache expiration in HTTP and therefore not taking advantage of it.  Moreover during debugging cycles cached data is a pain to work with when one wants to test his\her fix.

These are some of the patterns that are at top of my head. What else can be added?