Joining an array of numbers to form the biggest number

Given an array numbers, we have to join them in such a way that it forms the biggest number.

For example consider the simple three element array [10,3,2], they can be joined in following ways
1032, 1023, 2103, 2310, 3102, 3210. Among these numbers 3210 is the biggest number.

To solve this problem we definitely have to sort the given numbers using some criteria to form the biggest number.
Considering the above example, if we simply sort them in descending order, the array becomes [10,3,2] which does not form the biggest number.

Similarly we can also sort numbers by comparing the numbers string comparison. This does not work in cases like [1,10]. Since “10” > “1” the array in sorted as [10,1], but 110 is the biggest number.

We should think of a custom comparison function which guarantees us the biggest number when joined. Let us join the two numbers to be compared in two ways and compare them.

Considering the above example, they become 110 (“1″+”10”), 101( “10”+”1″). Since 110 is higher we place 1 first in sorting order before 10.

Here is the simple python implementation of the above algorithm. Also see my post on geeksforgeeks for C++ implementation of the same algorithm.

Longest common subsequence problem

This is a famous computer science problem with various applications in tools such as file diff, bio informatics etc. For more information read this on wiki.
Given a set of strings, how do we find the longest common sub-sequence(LCS) among them?

For example, LCS{“ATDACG”,”CTDACGA”} is  “TAG”.

In this post, we will look at the algorithm to find the LCS of two strings. To understand the solution, let us walk through a simple example.

Let us consider the strings “ACDG”, “CAG”. We can recursively define the LCS of two strings str1, str2 of lengths n,m as follows.
LCS(str1, str2) =
LCS(str1[0:n-2], str2[0:m-2])+str1[n-1] if str1[n-1] = str2[m-1]
Max(LCS(str1,str2[0:m-2], LCS(str1[0:n-2],str2)) otherwise
Using the above definition
LCS(“ACDG”,”CAG”) = LCS(“ACD”, “CA”) + “G”

This means that since the last character is same, in the sub-problem we can delete it from both the strings.
Further calculations go as follows

LCS(“ACD”, “CA”) = Max( LCS(“AC”, “CA”), LCS(“ACD”,”C”) )
LCS(“ACD”, “C”) = Max( LCS(“AC”, “C”), LCS(“ACD”,””) )

and so on…

we can see that LCS(“ACD”,”CA”) is “C”; so “CG” is the final output.

If we implement this naive recursion, we repeat the calculation for many sub problems. For efficient implementation we use a 2 dimensional array of size (n+1)*(m+1).The table is calculated using the rules given below which directly follow from the recursive definition given above.

table[i][j]= 0 if either of the string is empty
= 1 + table[i-1][j-1] if their last characters are equal
= max(table[i-1][j], table[i][j-1]) otherwise

Here is an example table.

∅ B A C B A D
∅ 0 0 0 0 0 0 0
A  0 1 1 1 1 1 1
B  0 1 1 1 2 2 2
A  0 1 2 2 2 3 3
Z  0 1 2 2 2 3 3
D  0 1 2 2 2 3 4
C  0 1 2 3 3 3 4

Here are the python implementations of both approaches.