Sparse Matrix Transposition

Sparse matrix is very useful in some scientific computing, such as calculating the similarity between two web pages or clustering multiple web pages. The vector representation tends to be sparse.

There are many ways to represent sparse matrix, one of them is called COO, coordinate list which is list of tuples storing row index, column index and its value; See wiki page for COO: https://en.wikipedia.org/wiki/Sparse_matrix#Coordinate_list_.28COO.29

Now we need to transpose a sparse matrix with COO list to another COO list. Below is the code with comments containing the detailed explanation of the algorithm.

Sparse Matrix Multiplication

The sparse matrix multiplication algorithm can be seen here:
http://mathforum.org/library/drmath/view/51903.html

and at stackoverflow site too
http://stackoverflow.com/questions/15693584/fast-sparse-matrix-multiplication

The key to the linear algorithm is to find all non-zero entries in one the sparse matrix and then loop through them, update the impacted entries in the final result matrix.

Here is the code: 

palindrome permutation

This is a leetcode problem.

Write an efficient function that checks whether any permutation of an input string is a palindrome. Examples:
 "civic" should return true
 "ivicc" should return true
 "civil" should return false
 "livci" should return false

In a palindrome string, all characters appears symmetrically, except the middle character if the string length is odd. The key observation is that to count the appearances of each characters in the string, if all counts are even, or there is only one characters appears odd times, then the word is palindrome. And we use an array to store the counts for each character in the string. This kind of simple counting array is more space effective than using hash map to store character and its count. Here is the code.

The beauty of recursion

There are several programming models or techniques are powerful, yet simple and beautiful to solve problems. Recursion is one of them, others include dynamic programming, sliding windows, binary search.

Today I use recursion to solve two problems are permutation and combination of list of characters. For example, permutation of a, b, c are abc, acb, bac, bca, cab, cba. combinations are a, ab, abc, ac, b, bc, c.

Let's talk about permutation first, to generate them, image we have 3 balls in a bag with labels of a, b, c, we first one ball of 3 in the bag, then another ball out of 2 balls left, then last ball left in the bag. When there is no balls left in the bag, we are done, which is our recursion termination condition. So how we make sure we don't take the same ball twice in a permutation, we can mark it and unmark it once a permutation is generated. Here is the code:


Now let's talk about combination, which is a bit complicated than permutation. For the first position, we have possibilities of a, b, or c. And if we have a in the first position, we can have b or c; if we have b in the first position, we can only have c followed after; if we have c, nothing can follow. And every time we put a character in the string, we have one new combination. So we have
a
ab
abc
-->recursion terminated
remove c => ab
-->recursion terminated
remove c => a
ac
-->recursion terminated
remove c => a
-->recursion terminated
remove a=> ''
b
bc
c

Here is the code:

find all possible words based on phone numbers

This is a classic code problem:

http://www.geeksforgeeks.org/find-possible-words-phone-digits/

This can be done beautifully in a recursion approach. The key here is to loop through all digits in the phone number from left to right, set the corresponding char in the word based on the phone keyboard, the recursion will terminate when the last digit is passed.


Another approach is to do it iterativelly. The key here is to find a way to calculate next word from a current word. for example, if the current word is ADG, then next word is ADH, next after that is ADI, AEG.

Products of all numbers in the array

This is google coding interview question:

Given an array of numbers, replace each number with the

product of all the numbers in the array except the number itself *without* using division

https://www.glassdoor.com/Interview/Given-an-array-of-numbers-replace-each-number-with-the-product-of-all-the-numbers-in-the-array-except-the-number-itself-w-QTN_9132.htm

The key to this solution is construct the accessory arrays which assists the solution. Here are the code 


Recursive way


Iterative way:

Minimum Size Subarray Sum

This is a leetCode problem: http://www.programcreek.com/2014/05/leetcode-minimum-size-subarray-sum-java/

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length of 2 under the problem constraint.

We can solve this by a sliding window, aka inch worm algorithm. Essentially we grow this sliding window to the right if the sum is smaller than the s, once sum >= s, then we update the minimal length of the window and then start to shrink the window from the left until sum < s. Here is the code:

minimum path sum of a number triangle

This is from leetcode: http://www.programcreek.com/2013/01/leetcode-triangle-java/

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). 

The key observation here is that viewing this triangle as a tree, for any given subtree, the minimum path sum is the minimum of all of its subtrees plus the number at the root. At the leaf level, the minimum path sum is the value at the leaves.

If we use dynamic programming, keep track of the minimum path sum at lower level, and then going up to calculate the min path sum at higher level.




Further observation of the dynamic programming solution is that we don't need a 2D table, in stead we can use an array and keep on updating it when going up.