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.

	//given a sparce matrix Coordinate list (COO) representation, transpose the matrix and output new COO representation
	//first, for each tuple in the list; (r, c, v), it will map to (c, r, v) in the final output
	//second, when go through the COO list from index at 0 to the last item COO.length-1, we need to calculate
	//the correponding index in the new COO
	//the observation is that for the COO tuples in the first row will transpose to first column in new COO,
	//and its index equals to the total number of COO tuples in the previous rows
	//so we need an array to record the total number of COO tuples in previous rows for any given row
	//we also need to update the numbers in the array when we generate new tuples in each row
	//you need to try out samples and draw pictures to understand the last two sentences
	class Solution {
	static class Tuple {
	int r, c, v;
	public Tuple(int r, int c, int v){
	this.r = r; this.c = c; this.v = v;
	}
	}
	//input are tuples and number of rows and cols
	//output are the tuples array after the transpose
	public static Tuple[] transpose(Tuple[] input, int rows, int cols){
	//first create the assessary array to store the numbers of tuples for any given row for the new matrix
	//this is done by counting the tuples in each column of the original matrix
	int[] values = new int[cols];
	for(Tuple t : input){
	values[t.c]++:
	}
	//then we build the array store the total numbers of tuples in previous rows for any given row for the new matrix
	int[] rows = new int[cols];
	rows[0] = 0;
	for(int r = 1; r<cols; r++){
	rows[r] = rows[r-1] + values[r-1];
	}
	//now we can do the tranposition
	Tuple[] ret = new Tuple[input.length];
	for(Tuple t : input){
	//so far there are rows[t.c] tuples before the current tuple we are creating here
	ret[rows[t.c]] = new Tuple(t.c, t.r, t.v);
	//remember we have to update the count
	rows[t.c]++;
	}
	return ret;
	}
	}

view raw sparseMatrixTranspose.java hosted with ❤ by GitHub

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: 

	public static class Pair {
	int r, c;
	public Pair(int r, int c){
	this.r = r; this.c = c;
	}
	}
	//assume A has more 0s than B, more sparse!
	public int[][] multiply(int[][] A, int[][] B) {
	//create a set store all non-zero entries in A
	Set<Pair> storeA = new HashSet<>();
	for(int r=0; r<A.length; r++){
	for(int c=0; c<A[0].length; c++){
	if(A[r][c]!=0)
	storeA.put(new Pair(r, c));
	}
	}
	//create a map to map row index in B to non-zero indices on that row
	Map<Integer, Set<Integer>> storeB = new HashMap<>();
	for(int r=0; r<B.length; r++){
	storeB.put(r, new HashSet<Integer>());
	for(int c=0; c<B[0].length; c++){
	if(B[r][c]!=0)
	storeB.get(r).add(c);
	}
	}
	int[][] result = new int[A.length][B[0].length];
	//now go through each entries in storeA to populate the entries in result which depends on it
	for(Pair p : storeA){
	for(int c2 : storeB.get(p.c)){
	result[p.r][c2] += A[p.r][p.c] * B[p.c][c2];
	}
	}
	return result;
	}

view raw SparseMatrixMultiplication.java hosted with ❤ by GitHub

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.

	// Leetcode: Palindrome Permutation
	public static boolean hasPaliPermu(String s){
	int[] apps = new int[256];
	for(int i=0; i<s.length(); i++){
	char c = s.charAt(i);
	apps[c] = (apps[c]+1)%2;
	}
	int count = 0;
	for(int i=0;i<256;i++){
	if(apps[i] == 1)
	count++;
	}
	return count<2;
	}

view raw palindromePermutation.java hosted with ❤ by GitHub

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:

	public static void permutationOf(char[] chars){
	permutationOfRec(chars, new char[chars.length], 0, new HashSet<Character>());
	}
	private static void permutationOfRec(char[] chars, char[] curr, int index, Set<Character> visited){
	int len = chars.length;
	if(len == index)
	System.out.println(curr);
	else{
	for(char c : chars){
	if(!visited.contains(c)){
	curr[index] = c;
	visited.add(c);
	permutationOfRec(chars, curr, index+1, visited);
	visited.remove(c);
	}
	}
	}
	}

view raw permuation.java hosted with ❤ by GitHub

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:

	public static void combinationOf(char[] chars){
	combinationOfRec(chars, 0, new StringBuilder());
	}
	private static void combinationOfRec(char[] chars, int index, StringBuilder sb){
	int len = chars.length;
	for(int i=index; i<len; i++){
	sb.append(chars[i]);
	System.out.println(sb);
	combinationOfRec(chars, i+1, sb);
	//once we finish all possible extensions we remove the last char
	//so we can start with new possiblities
	//e.g. we have ->a->ab->abc shorten to ab a
	// ac shorted to a ''
	//then we have ->b->bc shorted to b to ''
	//then we have ->c
	sb.setLength(sb.length()-1);
	}
	}

view raw combination.java hosted with ❤ by GitHub

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.

	private final static Map<Integer, char[]> store = new HashMap<>();
	static {
	store.put(1, new char[]{'1'});
	store.put(2, new char[]{'A', 'B', 'C'});
	store.put(3, new char[]{'D', 'E', 'F'});
	store.put(4, new char[]{'G', 'H', 'I'});
	store.put(5, new char[]{'J', 'K', 'L'});
	store.put(6, new char[]{'M', 'N', 'O'});
	store.put(7, new char[]{'P', 'R', 'Q', 'S'});
	}
	public static void phoneNum2String(int[] phone){
	char[] curr = new char[phone.length];
	phoneNum2StringRec(phone, 0, curr);
	}
	private static void phoneNum2StringRec(int[] phone, int index, char[] curr){
	int len = phone.length;
	if(index==len)
	System.out.println(curr);
	else{
	char[] chars = store.get(phone[index]);
	for(char c : chars){
	curr[index] = c;
	phoneNum2StringRec(phone, index+1, curr);
	}
	}
	}

view raw phoneNum2String hosted with ❤ by GitHub

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.

	public static void phoneNum2StringIter(int[] phone){
	int len = phone.length;
	char[] curr = new char[phone.length];
	for(int i=0;i<phone.length; i++)
	curr[i] = store.get(phone[i])[0];
	System.out.println(curr);
	while(findNext(phone, curr)){
	System.out.println(curr);
	}
	}
	private static boolean findNext(int[] phone, char[] curr){
	//we loop through from right
	for(int i=phone.length-1;i>=0;i--){
	char[] chars = store.get(phone[i]);
	int found = -1;
	for(int index = 0; index<chars.length; index++)
	if(chars[index] == curr[i])
	found = index;
	if(found!=-1 && found+1<chars.length){
	//we find the index of curr[i] and set it to next char
	curr[i] = chars[found+1];
	//also set all of the chars to its right to mimimum values
	for(int j=i+1;j<phone.length;j++){
	curr[j] = store.get(phone[j])[0];
	}
	return true;
	}
	}
	return false;
	}

view raw phoneNum2StringIter.java hosted with ❤ by GitHub

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

	public static int[] products(int[] nums){
	int[] products = new int[nums.length];
	productRec(nums, products, 0);
	return products;
	}
	public static int productRec(int[] nums, int[] products, int i){
	if(i==nums.length-1)
	return 1;
	products[i] = (i==0?1:products[i-1] * nums[i-1]);
	int p = productRec(nums, products, i+1) * nums[i+1];
	products[i] = products[i] * p;
	return p;
	}

view raw productRec.java hosted with ❤ by GitHub

Iterative way:

	public static int[] product(int[] nums){
	int len = nums.length;
	int[] result = new int[len];
	result[0] = 1;
	for(int i=1; i<len; i++){
	result[i] = result[i-1] * nums[i-1];
	}
	int p = 1;
	for(int i=len-2; i>=0; i--){
	p = p * nums[i+1];
	result[i] = result[i] * p;
	}
	return result;
	}

view raw productIterative.java hosted with ❤ by GitHub

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:

	public static int minimumSizeArray(int[] nums, int s){
	int min = Integer.MAX_VALUE, sum = 0;
	int p1=0,p2=0,len=nums.length;
	while(p2<len && p1<len){
	sum += nums[p2];
	while(p1<len && sum >=s){
	min = Math.min(p2-p1+1, min);
	sum -= nums[p1];
	p1++;
	}
	p2++;
	}
	return min == Integer.MAX_VALUE?0 :min;
	}

view raw minimumSizeArray.java hosted with ❤ by GitHub

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.

	public static int minPath(List<int[]> input){
	int levels = input.size();
	int[][] dp = new int[levels][levels];
	//we start at the bottom
	//here the min path sum is the numbers at the bottom
	dp[levels-1] = input.get(levels-1);
	//now we go up
	for(int l=levels-2; l>=0; l--){
	for(int pos = 0; pos<=l; pos++){
	dp[l][pos] = Math.min(dp[l+1][pos], dp[l+1][pos+1]) + input.get(l)[pos];
	}
	}
	return dp[0][0];
	}

view raw gistfile1.java hosted with ❤ by GitHub

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.

	public static int minPathBetter(List<int[]> input){
	int levels = input.size();
	int[] dp = new int[levels];
	//we start at the bottom
	//here the min path sum is the numbers at the bottom
	dp = input.get(levels-1);
	//now we go up
	for(int l=levels-2; l>=0; l--){
	for(int pos = 0; pos<=l; pos++){
	dp[pos] = Math.min(dp[pos], dp[pos+1]) + input.get(l)[pos];
	}
	}
	return dp[0];
	}

view raw minpath.java hosted with ❤ by GitHub