Twenty Percent Knowledge: June 2015

Tuesday, June 30, 2015

Longest Common Substring

First method returns length of longest common substring.
Second method is modified based on first method to return the longest common substring.

It's interesting to see the two solutions coming out one year apart.

Second version: done in 2016. I am not improved :)

import java.util.Objects;

/**
 * converting it to 2d array, x coordination is from one string and y coordination is form another string.
 * the matching substrings will be adjacent diagonal sequences. 
 * this way is also easy to retrieve all the common substrings: stating from 1 and diagonally increasing
 * advanced and more efficient way: suffix tree
 * @author Andrew Ma
 *
 */
public class LongestCommonSubString {
 public static int longestCSLength(String s1, String s2){
  /**
   * s1 is y, vertical. s2 is x, horizontal
   */
  Objects.requireNonNull(s1);
  Objects.requireNonNull(s2);
  int maxLength = 0;
  if(s1.length()==0 ||s2.length()==0)return 0;
  char[] s1y = s1.toCharArray();
  char[] s2x = s2.toCharArray();
  int[][] matches = new int[s1.length()][s2.length()]; 
  for(int x=0;x<s2.length();x++){
   for(int y=0;y<s1.length();y++){
    //mark and count
    if(s2x[x]==s1y[y]){
     if(x==0 || y==0){//on top or left boarder, start as 1
      matches[y][x]=1;
     }else{
     matches[y][x] = matches[y-1][x-1]+1;
     }
     maxLength = Math.max(matches[y][x],maxLength);
    }
    else
     matches[y][x]=0;
   }
  }
  return maxLength;
 }
 public static String retrieveString(String s1,String s2, int s1P,int s2P){
  StringBuffer sb = new StringBuffer();
  while(s1P>=0 && s2P>=0&&s1.charAt(s1P)==s2.charAt(s2P)){
   sb.append(s1.charAt(s1P));
   s1P--;
   s2P--;
  }
  return sb.reverse().toString();
 }
 public static String longestCommonSubstring(String s1, String s2){
  /**
   * s1 is y, vertical. s2 is x, horizontal
   */
  Objects.requireNonNull(s1);
  Objects.requireNonNull(s2);
  String longestSubStr = "";
  int maxLength = 0;
  if(s1.length()==0 ||s2.length()==0)return "";
  char[] s1y = s1.toCharArray();
  char[] s2x = s2.toCharArray();
  int[][] matches = new int[s1.length()][s2.length()]; 
  for(int x=0;x<s2.length();x++){
   for(int y=0;y<s1.length();y++){
    //mark and count
    if(s2x[x]==s1y[y]){
     if(x==0 ||y==0){//on top or left boarder, start as 1
      matches[y][x]=1;
     }else{
     matches[y][x] = matches[y-1][x-1]+1;
     }
     if(maxLength <matches[y][x]){
      maxLength = matches[y][x];
      longestSubStr = retrieveString(s1,s2,y,x);
     }
    }
    else
     matches[y][x]=0;
   }
  }
  return longestSubStr;
 }
 public static void main(String[] args){
  int i = longestCSLength("abcdefg","uiubciabcdu");
  System.out.println(i);
  String s = longestCommonSubstring("abcdefg","uiubciabcdu");
  System.out.println(s);
 }
}

First version in 2015.

public class longestCommonSubstr {

 public static void main(String[] args) {
  System.out.println(longestCommonStrLen("aaabbbccc",
    "hshshsabbbcklklkl"));

 }

 public static int longestCommonStrLen(String first, String second) {
  if (first == null || second == null || first.length() == 0
    || second.length() == 0) {
   return 0;
  }
  // a variable to hold the maximum length
  int maxLen = 0;
  // imaging first is listed vertically, each character marks a row
  /**
   * abc
   *a
   *b
   *c
   */
  int row = first.length();
  // imaging second is listed horizontally
  // bcd
  /**
   * together a matric is like this bcd a b 1 c 2 for a matrix like that,
   * if there is a common substring, you will find both dimensions will
   * grow together
   */
  int column = second.length();
  int[][] table = new int[row][column];
  // initialize first row values to be 0
  for (int s = 0; s < column; s++)
   table[0][s] = 0;
  // initialize first column values to be 0
  for (int f = 0; f < row; f++)
   table[f][0] = 0;

  for (int i = 0; i < row; i++) {
   for (int j = 0; j < column; j++) {

    // at current position, it checks previous position's value.
    // common substring means both dimensions grow at same time. the
    // calculation is from low to high, so that in order to
    // determine higher position's length,
    // it need to figure out lower position's length the first
    // for edge matches,it starts with 1, means one match
    if (first.charAt(i) == second.charAt(j)) {

     // starting from edges, initialize count to be 1
     if (i == 0 || j == 0) {
      table[i][j] = 1;
     } else {
      table[i][j] = table[i - 1][j - 1] + 1;
     }
     if (table[i][j] > maxLen) {
      maxLen = table[i][j];
     }
    }
   }
  }
  return maxLen;
 }

 public static String getLongestCommonSubstr(String first, String second) {
  if (first == null || second == null || first.length() == 0
    || second.length() == 0) {
   return "";
  }
  // a variable to hold the maximum length
  StringBuilder sb = new StringBuilder();
  int maxLen = 0;
  // one position in one string is enough
  int maxI = 0;
  // imaging first is listed vertically, each character marks a row
  /**
   * abc
   *a
   *b
   *c
   */
  int row = first.length();
  // imaging second is listed horizontally
  // bcd
  /**
   * together a matrix is like this bcd a b c for a matrix like that, if
   * there is a common substring, you will find both dimensions will grow
   * together
   */
  int column = second.length();
  // do not need to have an extra column and row, this matrix represents
  // all possible matching points, it's value is length of
  // substring as result of growing diagonally
  int[][] table = new int[row][column];
  // initialize first row values to be 0, set it to 1 when there is a
  // match
  for (int s = 0; s < column; s++)
   table[0][s] = 0;
  // initialize first column values to be 0, set it to 1 when there is a
  // match
  for (int f = 0; f < row; f++)
   table[f][0] = 0;
  // traversal the two strings. it check back both dimensions to determine
  // if substring grows
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < column; j++) {

    // at current position, it checks previous position's value.
    // common substring means both dimensions grow at same time. the
    // calculation is from low to height, so that in order to
    // determine higher position's length,
    // it need to figure out lower position's length the first
    // for edge matches,it starts with 1, means one match
    if (first.charAt(i) == second.charAt(j)) {

     // starting from edges, initialize count to be 1
     if (i == 0 || j == 0) {
      table[i][j] = 1;
     }
     // other wise, substring is growing, mark the length and
     // build it out
     else {
      table[i][j] = table[i - 1][j - 1] + 1;

     }
     if (table[i][j] > maxLen) {
      maxLen = table[i][j];
      maxI = i;
     }
    }
   }
  }
  while (maxLen > 0) {
   sb.append(first.charAt(maxI - maxLen + 1));
   maxLen--;
  }
  return sb.toString();
 }
}

Monday, June 29, 2015

Bit Operation Review

And (&):	0 & 0 = 0	1 & 0 = 0	0 & 1 = 0	1 & 1 = 1
Or (\|):	0 \| 0 = 0	1 \| 0 = 1	0 \| 1 = 1	1 \| 1 = 1
Xor (^):	0 ^ 0 = 0	1 ^ 0 = 1	0 ^ 1 = 1	1 ^ 1 = 0

Left Shift:

x << y means x shifted y bits to the left. If you start shifting and you run out of space, the bits just “drop off”. For example:
00011001 << 2 = 01100100
00011001 << 4 = 10010000

Right Shit
x >> y means x shifted y bits to the right. If you start shifting and you run out of space, the bits just “drop off” the end. Example:
00011001 >> 2 = 00000110
00011001 >> 4 = 00000001

((n & (n-1)) == 0) checks if n is a power of 2 (or 0).

XOR
one number, when XOR with another number twice, it turns back to itself again.
e.g. 1000^0101=1101, 1101^0101=1000 that is a^b and ^b again to get back a. similarly, a^b and ^a again to get b. with this feature, you can swap two number by using XOR operations
a=a^b;
b=a^b;//b now is a
a=a^b;//this equivalent to a^b^a=b
(XOR with same number twice equals not applying anything)

Saturday, June 27, 2015

Decode Ways

Question
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.

My Answer:

/**
 * analysis:
 * I thought it is multiplication, then since it adds up conditionally, so better 
 * go with basic addition
 * 1. the numbers that can have two meanings
 * 22, {BB,W}
 * 222, {BBB,BW,WB}
 * ~~~position i-2+22 or i-1+2 when i-1 and i compose a number between 11 and 26 (except 20)
 * 2222, {BBWW,WW,(up to here is position i-1 to current position)BBBB,BWB,WBB(these three are transitioning from position i-1)}
 * 22222 this would be all ways from position i-1 and i-2 if last number has position i
 * so general formular ways[i]=ways[i-1+ways[i-2]
 * it is possible to start from two previous position to transit to current position, because number here is just either 1 digit or 2 digits
 * 
 * 2.if a position has number bigger than 2, then there is only one way to map back to letter
 * 2234
 * 34 is not possible, so it has to be 223(remains all possible combinations) and 4, equivalent to number of ways of 223
 * here i0=1,i1=2,i2=3, i3 is still 3
 * 
 * 3. 0
 * leading 0 is impossible and means wrong input, return 0. mainly because the map has no 0 in it
 * 0,00, 30, 301(30,1 or 3,01 are all invalid)
 * 
 * @author Andrew
 *
 */
public class Solution {

 public static int numDecodings(String s) {
  ///"","0","00", leading with 0
  if (s == null || s.length() == 0 || "0".equals(s.substring(0, 1))) {
   return 0;
  }
  //2,08
  if (s.length() == 1) return 1;

  int[] ways = new int[s.length()];
  char prevChar, curChar;
  int curNum;

  ways[0] = 1;
  ways[1] = 1;
  //for string longer than 2, figure out the first 2 positions possible combinations
  //this might be able to be integrated to the following loop
  if (s.length() >= 2) {
   //impossible situations: 30, 40, only 0 has this problem because it is not in the map
   if (s.charAt(0) > '2' && s.charAt(1) == '0') ways[1] = 0;
   //10 and 20 are valid, and they has only one possible decoding way
   else if ((s.charAt(0) == '1' || s.charAt(0) == '2') && s.charAt(1) == '0') ways[1] = 1;
   //all other numbers such as 11,22 26 are having 2 possible decodings
   else if (Integer.parseInt(s.substring(0, 2)) > 10 && Integer.parseInt(s.substring(0, 2)) <= 26) ways[1] = 2;
  }
  //starting form third position because my basic assumption is ways[i]=ways[i-1]+ways[i-2]
  for (int i = 2; i < s.length(); i++) {
   prevChar = s.charAt(i - 1);
   curChar = s.charAt(i);
   curNum = Integer.parseInt("" + prevChar + curChar);
   //for 20 and 10(0 is position i),i-1 has only one possibility, so it equals ways at i-2
   //this handles numbers between 1-10 in two positions
   if (curChar == '0') {
    ways[i] = ((prevChar == '2' || prevChar == '1') ? ways[i - 2] : 0);
    ways[i - 1] = ways[i]; //i-1 should be same as i
   }
   //this is for numbers that has two possible ways to decode
   else if (curNum > 10 && curNum <= 26) ways[i] = ways[i - 2] + ways[i - 1];
   else //other situation has only 1 possible way to decode, so current ways of decoding is
   //equals to previous ways of decoding
   ways[i] = ways[i - 1];

  }
  return ways[s.length() - 1];
 }



 public static void main(String[] args) {
  //  System.out.println(numDecodings("99")    );
  //  System.out.println(numDecodings("27")    );
  //  System.out.println(numDecodings("301")    );
  //  System.out.println(numDecodings("08")    );
  System.out.println(numDecodings("110"));
  System.out.println(numDecodings("920"));
  System.out.println(numDecodings("20"));
 }

}

Test cases:

import static org.junit.Assert.*;

import org.junit.Test;


public class WaysDecodeTest {

 @Test
 public void testNumDecodings1() {
  int actual = Solution.numDecodings("99");
  assertEquals(1, actual);
 }
 @Test
 public void testNumDecodings2() {
  int actual = Solution.numDecodings("301");
  assertEquals(0, actual);
 }
 @Test
 public void testNumDecodings3() {
  int actual = Solution.numDecodings("27");
  assertEquals(1, actual);
 }
 @Test
 public void testNumDecodings4() {
  int actual = Solution.numDecodings("08");
  assertEquals(0, actual);
 }
 @Test
 public void testNumDecodings5() {
  int actual = Solution.numDecodings("12");
  assertEquals(2, actual);
 }
 
 @Test
 public void testNumDecodings6() {
  int actual = Solution.numDecodings("121");
  assertEquals(3, actual);
 }
 @Test
 public void testNumDecodings7() {
  int actual = Solution.numDecodings("2222");
  assertEquals(5, actual);
 }
 @Test
 public void testNumDecodings8() {
  int actual = Solution.numDecodings("22222");
  assertEquals(8, actual);
 }
 @Test
 public void testNumDecodings9() {
  int actual = Solution.numDecodings("22229");
  assertEquals(5, actual);
 }
 @Test
 public void testNumDecodings10() {
  int actual = Solution.numDecodings("222292");
  assertEquals(5, actual);
 }
 @Test
 public void testNumDecodings11() {
  int actual = Solution.numDecodings("2222920");
  assertEquals(5, actual);
 }
 @Test
 public void testNumDecodings12() {
  int actual = Solution.numDecodings("110");
  assertEquals(1, actual);
 }
 @Test
 public void testNumDecodings13() {
  int actual = Solution.numDecodings("20");
  assertEquals(1, actual);
 }
}

Tuesday, June 09, 2015

Rotating an NxN Matrix 90 Degrees

If space has no limit, rotating it while copying it. This is On^2) in speed.

For in-place rotating, which is memory economy, imaging matrix is divided to layers and edges in each layer is moving clock wise. This is O((n/2)*(n/2-1)!)

 package a.ma;

public class MatrixRotate {
public static void main(String[] args) {
int ma[][] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
printArray(ma);
//rotate(ma, 4);
copyRotate(ma,4);
//printArray(ma);
}
public static void printArray(int[][] matrix) {
System.out.println(matrix.length);
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++)
System.out.print(matrix[i][j]);
System.out.println();
}
}
/**
* based on simple conversion that rows become columns
* first row becomes last column, second row become last second column...
* element wise, first one become
* @param matrix
* @param n
*/
public static void copyRotate(int[][] matrix, int n) {
int tmp[][] = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
tmp[i][j] = matrix[n - j - 1][i];
}
printArray(tmp);
}
/**
* 1111
* 2222
* 3333
* 4444
* imagine there is a center, the ractangle rotate around the center.
* there are n/2 circles/layers without counting the center point, if n is odd number, the center point is not moving
* so there will be 1=n/2 layers to move, for each layer
* top edge, except last corner, will move to right edge
* right edge, except last corner, will move to bottom edge
* bottom edge, except last corner, will move to left edge
* left edge, except last corner will move to top edge
*
* to do the moving, use a variable to hold the variable that is going to be overridden, assign it back to proper
* position after a layer's moving
*
* in this algorithm, (x,x) is the element chosen to be first element in a layer to move, x is up to n/2-1 (counting from 0)
*
* to do the moving, first loop is for all the layers, which is 0..n/2-1
* in each layer, elements need to move is between first and last. first is [x,x], then last should be [x,n-1-layer-1]
* a variable cursor is used to move between first and last
* @param matrix
* @param n
*/
public static void inPlaceRotate(int[][] matrix, int n) {
//first loop is for all the layers, which is 0..n/2-1
for (int layer = 0; layer < n / 2; ++layer) {
int first = layer;//first is [x,x] so it always be [layer,layer]
//last here means last element of an edge in a layer, which is not part of moving element
//for example, first layer top line, the element to move is 1 1 1
int last = n - 1 - layer ;
for (int i = first; i < last; ++i) {
int cursor = i - first;//sequence of moving element
//do the element movement based on top edge
int top = matrix[first][i]; // save top element
// then move left up to top
matrix[first][i] = matrix[last - cursor][first];
// then move bottom to left
matrix[last - cursor][first] = matrix[last][last - cursor];
// then move right to bottom
matrix[last][last - cursor] = matrix[i][last];
// finally put original top element to right edge
matrix[i][last] = top;
}
}
}
}