Algorithms night (1)

January 17, 2016

Spent Sunday evening (8pm - 12pm) to work on algorithms questions. Just read the blogs, and get some ideas how to solve the problems. 

1. String parenthesis to see if all of them are pair correctly

Leetcode 20: valid parentheses

http://buttercola.blogspot.ca/2014/07/leetcode-valid-parentheses.html

http://www.shuatiblog.com/blog/2014/05/09/Valid-Parentheses/

2. Count the number of palindromes in  a string

 (January 28, 2016)
    Come back to write down ideas:
    1. First of all, do not count duplicate.
    2. Brute force solution:
 any substring of O(N^2) substrings to see if it is a palindrome;
 Add the substring of palindrome to a hashset if it is not in the hashset.
  And return the length of hashset
    3. Use recursive solution - using subproblem to solve. Cannot filter out duplicate - not good
    4. Better solution - use center point of string - 2n + 1, and then, go over each one, add all palindromes substring.

  Requirement: write a C# code in 10 minutes for the solution, using brute force one.

  https://github.com/jianminchen/AlgorithmsPractice/blob/master/NumberOfDistinctPalindromes.cs

3. Write a function to detect if the string has the unique character. 

Read the blog: 

http://stackoverflow.com/questions/19484406/detecting-if-a-string-has-unique-characters-comparing-my-solution-to-cracking

this blog provides good answers for the question of unique character:

Notice that this method doesn't allocate an array of booleans. Instead, it opts for a clever trick. Since there are only 26 different characters possible and there are 32 bits in an int, the solution creates an int variable where each bit of the variable corresponds to one of the characters in the string. Instead of reading and writing an array, the solution reads and writes the bits of the number.

Julia's comment: first blog about bit manipulation - surprising, after the reading, it is much easy to understand the code: 
Two bit operation: 
1<< val 
 |=  

It is always helpful to understand the 

public static boolean isUniqueChars(String str) {
    if (str.length() > 256) { // NOTE: Are you sure this isn't 26?
        return false;
    }
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0) return false;
        checker |= (1 << val);
    }
    return true;
}

http://javahungry.blogspot.com/2014/11/string-has-all-unique-characters-java-example.html

4. A single linked list, delete a node but only know the node pointer which needs to be deleted. How to do it?

http://www.geeksforgeeks.org/in-a-linked-list-given-only-a-pointer-to-a-node-to-be-deleted-in-a-singly-linked-list-how-do-you-delete-it/

5. Leetcode/ Lintcode: binary tree maximum path sum

Leetcode 124: binary tree maximum path sum
http://fisherlei.blogspot.ca/2013/01/leetcode-binary-tree-maximum-path-sum.html


Review the blog:
http://juliachencoding.blogspot.ca/2015/07/itint5-tree-maximum-path-sum.html

6. Minimum height of a binary search tree

http://www.programcreek.com/2013/02/leetcode-minimum-depth-of-binary-tree-java/