Largest continuous sub array problem

April 22, 2016

 Buy and sell stock - Leetcode question

http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

It is Dynamic programming problem.

Check Kadane's algorithm:

Question and Answer Time:
Question: What do you learn through the study?
Answer: This is a dynamic programming problem. Use two variables to track the statistics:
One is called maximum value ending here. max_ending_here;
Another one is called maximum value so far. max_so_far.

Let us walk through the code:

int maxSubArraySum(int a[], int size)

{

   int max_so_far = 0, max_ending_here = 0;

   for (int i = 0; i < size; i++)

   {

       max_ending_here = max_ending_here + a[i];

       if (max_ending_here < 0)

           max_ending_here = 0;

       /* Do not compare for all elements. Compare only  

          when  max_ending_here > 0 */

       else if (max_so_far < max_ending_here)

           max_so_far = max_ending_here;

   }

   return max_so_far;

}

Handle the case when all numbers in the array are negative:

int maxSubArraySum(int a[], int size)

{

   int max_so_far = a[0];

   int curr_max = a[0];

   for (int i = 1; i < size; i++)

   {

        curr_max = max(a[i], curr_max+a[i]);

        max_so_far = max(max_so_far, curr_max);

   }

   return max_so_far;

}




gray code

April 21, 2016

Work on algorithm called "gray code".

1) Given two words, find if second word is the round rotation of first word.
For example: abc, cab
return 1
since cab is round rotation of abc

Example2: ab, aa
return -1
since aa is not round rotation for aa

2) Given two hexadecimal numbers find if they can be consecutive in gray code
For example: 10001000, 10001001
return 1
since they are successive in gray code

Example2: 10001000, 10011001
return -1
since they are not successive in gray code.

problem statement source:

http://www.geeksforgeeks.org/amazon-interview-experience-set-137-assessment-test-sde/

Read the blog:
http://www.cnblogs.com/lautsie/p/3909927.html

choose some questions to work on, practice!
http://www.cnblogs.com/lautsie/tag/hackerrank/

try this one - see if the content is related to gray code
https://www.hackerrank.com/contests/w6/challenges/consecutive-subsequences

Leetcode gray code:
https://leetcode.com/problems/gray-code/

Two solutions:
http://bangbingsyb.blogspot.ca/2014/11/leetcode-gray-code.html

http://fisherlei.blogspot.ca/2012/12/leetcode-gray-code.html

Question and answer time:
Q: Julia, tell me what you know about gray code. 
Answer:
1. Gray code is very specific for the one to build up using previous results. 
    To extend, append all the number in the set in reverse order, with number adding 2^n, n is the number in binary format length. 

2. Let us work on some coding:
n = 0: 0
n = 1: 0, 1

n = 2: 00, 01, 11, 10  (0, 1, 3, 2)

n = 3: 000, 001, 011, 010, 110, 111, 101, 100 (0, 1, 3, 2, 6, 7, 5, 4)

C++: 

 vector<int> grayCode(int n) {
        vector<int> greySeq;
        if(n<0) return greySeq; // julia's comment:
        greySeq.push_back(0);   // first, start from n=0, 0
        int inc = 1;            // incremental value is 1, 2^n, n =0;  
        for(int i=1; i<=n; i++) { // loop starting value: 1
            for(int j=greySeq.size()-1; j>=0; j--) // reverse order iteration
                greySeq.push_back(greySeq[j]+inc); // add incremental value for each one
            inc <<= 1;  // inc = inc *2  or inc <<=1; 
        }
        return

Remove Vowels From A String in Place

April 21, 2016

Work on algorithm called "Remove Vowels From A String in Place ".

problem statement see the blog:
https://www.careercup.com/question?id=2698

Take any word, remove vowels and place them in reverse order by untouching consonants and place them back. Word is AIRPLANE.

HackerRank has one algorithm, but only 4 submissions:

https://www.hackerrank.com/contests/knockout-coding/challenges/pair-odd

Read the blog about "Remove vowels":
http://shashank7s.blogspot.ca/2011/03/wap-to-remove-remove-vowels-from-string.html

https://www.quora.com/How-do-I-remove-vowels-from-a-string

Question and Answer:
Walk through the code, add comments:

1. const string vowels = "aeiou"; // Julia: all vowels in a string
3. void remVowels(string &s){
4. int k=0; // pointer: int k, mark the next available position for non vowel char
5. for(int i=0; i<s.length(); i++){ // Julia: go through the string once, in a loop
6. if(vowels.find(s[i]) == string::npos) // if current char is not a vowel
7. s[k++] = s[i];
8. // skip vowel, do nothing.
9. }
10. s.resize(k); // mark the end of the string removing all vowels.
11. }

Read api how resize is defined in C++:
http://www.cplusplus.com/reference/string/string/resize/

A binary tree is substree of another binary tree

April 21, 2016

Introduction

It is the great experience to review the recursive function through the algorithm called "Is subtree". Depth first search algorithm is very basic one using recursive function call, it is the fast and quick way to write an algorithm and also very popular in the interviews.

Problem statement:
http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/

Time Complexity: Time worst case complexity of above solution is O(mn) where m and n are number of nodes in given two trees.

Another solution:
http://www.geeksforgeeks.org/check-binary-tree-subtree-another-binary-tree-set-2/

O(n) time, special case handling - for leaf node of tree - append null 

Question and answers:

1. What do you learn through this study? How long does it take you to figure out things? 

Answer: First, it is about the subtree definition: it should be uniquely defined; for any node in the tree, the subtree starting from the node is only one. In other words, the node is the start, and all leaf nodes underneath should all be included.

2. The very good way to think recursively; do not repeat the work, do not do the extra work; only work on root node, since every node can be root node; get in the loop or recursive function. 

3. Let us walk through the code and add some comment: The code link is here. 

Dec. 25, 2016

Read the code review on stackexchange.com.

Algorithm called "is subtree"

http://codereview.stackexchange.com/questions/6774/check-if-a-binary-tree-is-a-subtree-of-another-tree
http://codereview.stackexchange.com/questions/117325/find-if-a-given-tree-is-subtree-of-another-huge-tree

Follow up 

June 17, 2017

Find out leetcode algorithm related algorithm. 

Blog to read:
Need to review KMP algorithm - strstr - O(N) algorithm:

http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/

valid parenthesis pairs

April 21, 2016

Work on algorithm called "Valid parenthesis pairs".

Review blog:
http://juliachencoding.blogspot.ca/2016/01/leetcode-questions-20-valid-parentheses.html

longest palindrome substring

April 21, 2016

Work on algorithm called "longest palindrome substring".

Review the blog:
http://juliachencoding.blogspot.ca/2015/06/leetcode-longest-palndromic-substring.html

August 8, 2016
Java practice:
https://gist.github.com/jianminchen/ee7e6512cd8fbffb1895e51ebaa4487c

Merge two sorted linked list

April 21, 2016

Work on algorithm called "Merge two sorted linked list".

Recursive call:

http://stackoverflow.com/questions/10707352/interview-merging-two-sorted-singly-linked-list

http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/

Search in Matrix

April 21, 2016

Work on algorithm called "Search in Matrix".

搜索杨氏表:
https://leetcode.com/problems/search-a-2d-matrix-ii/

Read the blog: 
http://noalgo.info/397.html

Two sum pair

April 21, 2016

Work on algorithm called two sum pair.

Problem statement:
https://www.careercup.com/question?id=12887674

Given an array. Find pairs of numbers that add up to a given value 'x'. with time complexity less than O(n^2) and use no additional space.

Also, Array Pair Sum, look up the google:
http://www.ardendertat.com/2011/09/17/programming-interview-questions-1-array-pair-sum/

work on this hackerRank problem to entertain the time:
https://www.hackerrank.com/contests/infinitum8/challenges/pairwise-sum-and-divide

Moderate level
https://www.hackerrank.com/challenges/sherlock-and-pairs

Leetcode 17 Phone number combination - practice (II)

April 26, 2016

To master this DFS algorithm, Julia likes to do more practice.  Every time she practices, she finds new issue, new concern. She also knows that to memorize a solution is not a good idea, do not focus on what you remember about the algorithm, even you have some memory about the algorithm and solution. You may have to solve a totally different problem. 

Leetcode 17 phone number combination

Review the blog:
http://juliachencoding.blogspot.ca/2016/01/leetcode-17-letter-combinations-of.html

One more practice - write the code using the same idea, still makes a bug, and learn how to do fast coding, add more explanation variable, and temporary variable.

https://gist.github.com/jianminchen/acbbf5fbd5fefa1a9fb2f7b3664bf4ed

https://gist.github.com/jianminchen/90ac4390929704ce439d0a1f255f4546

Make function more flat, close to left side, more readable - remove if/ else statement in the function, more flat; also, more readable code, less chance to have a bug. 

https://gist.github.com/jianminchen/b866a5c331556ea8f36aecfe123befea

Reading:
https://msdn.microsoft.com/en-us/library/zcbcf4ta.aspx
http://geekswithblogs.net/robp/archive/2008/08/13/speedy-c-part-3-understanding-memory-references-pinned-objects-and.aspx

Question and Answer: 
Julia has some concerns about recursive function, she will find some articles to read:
1. General about stack, recursive function.
2. How to check using C# - recursive argument one copy or its own copy?
3. Play safe, use extra variable to save the value.