Julia's coding blog - Practice makes perfect

From January 2015, she started to practice leetcode questions; she trains herself to stay focus, develops "muscle" memory when she practices those questions one by one. 2015年初, Julia开始参与做Leetcode, 开通自己第一个博客. 刷Leet code的题目, 她看了很多的代码, 每个人那学一点, 也开通Github, 发表自己的代码, 尝试写自己的一些体会. She learns from her favorite sports – tennis, 10,000 serves practice builds up good memory for a great serve. Just keep going. Hard work beats talent when talent fails to work hard.

Thursday, August 4, 2016

Leetcode 124: Binary Tree Maximum Path Sum - Single Responsibility Principle (SRP)

August 4, 2016

If you do not have idea how to solve the Leetcode 124, please read the blog first, warm up with ideas to solve the problem:
http://juliachencoding.blogspot.ca/2016/08/leetcode-124-binary-tree-maximum-path.html

Creative way to solve the algorithm problem:

Review S.O.L.I.D. principles, one of principle - Single Responsibility Principle.

Use SRP to write the function, one task a time.

1. Work on a simple problem first:
Maximum value end by root in a binary tree - in other words, maximum value from the root node to any node in binary tree

https://gist.github.com/jianminchen/8f3ec942e90bcdca5a1569d1a70e92df

Goal: be able to write the function in 10 minutes, verify code with static analysis.

1. Step 1: write a simple recursive function - preorder traversal.
A: Pay attention to negative value node.
(if both left and right child node's value are negative value, maximum value path ending at root node is root node's value itself; value >= root node's value) -> come out formula: line 98, maximum value of 3 values.

B: Avoid if statement, just get minimum value through 3 values, make it one line statement - no if/else discussion of left/right child value > 0.

Only 5 lines of code. Short and concise.

2. Add one more task in the above function -

Usually the function should be designed to work on one task only. Need to add a second task to the function.

Based on the simple problem - maximum value end by the root node, add one more task to the function:
maxValueCrossRoot calculation. (bottom up solution)

Try to calculate the maximum path sum cross the root node in the tree.

https://gist.github.com/jianminchen/5eab22189f0fd7a58aa4fbc56b725dd8

Add 2 more lines of code: line 104, 105, add one more input argument - ref int maxCrossRoot, 3 places update

Goal: complete the code change in 10 minutes.

2. Step 2: add 2 lines code (line 104, line 105), 3 changes - add one more argument (line 96, line 101, line 102):

So, overall, less than 20 minutes code writing. Follow the above 2 steps - write a function to complete the first task, and then, add second task to the function.

Questions and Answers:

1. How to make this algorithm an easy one?
A few people complain that the algorithm is too tough to work on through their blogs. Julia also spent hours to work on it in 2015, and then, Feb. 2016.

In August 2016, Julia spent hours to review the algorithm, wrote 2 blogs.

For easy to write, try SRP techniques, work on maximum path end by root first, then piggyback the max path cross the root. It will help to ease the stress.

I learned to stay and work hard every day to get the chance to be the best. - Karolina Pliskova
Julia, can you repeat the sentence word by word?

I like the encouraging verse. https://t.co/7wUhmyPoDx
— jianmin chen (@jianminchen) June 5, 2016

Leetcode 124: Binary tree maximum path sum - a quick review

August 4, 2016
Come back to review the previous work, but it is still not easy to tell the ideas to solve the problem.

Let us talk about an example first:
In the practice on May 31, 2016, line 60 - 79, test case 3:
https://gist.github.com/jianminchen/578656e1079e8c58b08dd19f5b027e68

The maximum path sum in the above tree is highlighted using red color, node 6->9->-3->2->2. Any two nodes in the tree can form a unique path, and the choice of path is N^2, N is the total nodes in the tree.

Walk through the above example in the diagram and have some more discussion:

First talk about "maximum value cross root" - variable: maxValueCrossRoot,
each node is the root of its subtree, so the maximum one will be maximum one from the following list:

1. n1: root node (9): need to calculate maximumEndByRoot on right child (-3) first.
2. n2: left child (6):
3. n3: right child (-3):
4. n4: right->right child(-6): -6
5. n5: right->right->right (2): 4
6. n6: right->rigth->right->left(2) : 2
7: n7: right->right->right->left->left(-6): -6
8: n8: right->rigth->right->left->right(-6): -6

It is comparison by values.
Tip: 1.The idea to get the maximum value is to pass a reference int to any recursive function. Any subtree will have one value, and compare with the global variable's value.
2. Use preorder traversal to travel tree once.

And "maximum value end by root" - variable: maximumEndByRoot

the above node n8: -6
n7: -6
n6: 2
n5: 4
n3: +1
n2: 6

So, the root node maxValueCrossRoot = 9 + 6 + 1 = 16
maximumByEnd = 15.

Tip: 1. use recursive function with return value - maxValueEndByRoot, the formula is easy to recall.
2. use preorder traversal to travel tree once.

The above case is coincident, the maxValueCrossRoot is ended at the root node n1 (value 9), which may be anywhere (ni, i is one value from 1 to 8) in the tree.

Blogs about leetcode 124:

Previous blogs about Leetcode 124:
1. blog 1:
http://juliachencoding.blogspot.ca/2015/07/leetcode-maximum-binary-tree-path-sum.html

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

3.
Practice on May 31, 2016, first version:

https://gist.github.com/jianminchen/432bdb1af38a1ec6f4a0741420891ebf

Second version: add more comment:
https://gist.github.com/jianminchen/578656e1079e8c58b08dd19f5b027e68

4. blog 4:

http://juliachencoding.blogspot.ca/2016/05/leetcode-124-binary-tree-maximum-path.html

I like the encouraging verse. https://t.co/7wUhmyPoDx
— jianmin chen (@jianminchen) June 5, 2016

Monday, August 1, 2016

HackerRank - Prepare to get experience on advanced level algorithms on HackerRank

August 1, 2016

Choose a small topic to work on, when to choose to work on advanced algorithm and what to learn through the practice.

Pragmatic ideas:

1. How is the algorithm developed by editors? Best algorithm lecture material to study.

2. Study some code for classical problems through submissions.

Julia spent over 100 hours to work on HackerRank, solved over 50+ algorithms problems, and then, she is getting better to understand the problem statement on HackerRank. But she only chose to work on easy, medium difficult questions.

Last time - 3 hours - really struggling - world code sprint #5 with advanced, difficult questions.

Some facts on 3 hours activities:
1. Tried to guess, break down small problems.
2. Wrote down some notes
3. Tried to guess what kind of problem it is - DP, DFS, graph, etc.

Julia likes to come back to review, and if she can write a blog on her 3 hours experience:

1. Spent 30+ minutes to read the problem statement
http://juliachencoding.blogspot.ca/2016/07/build-forest-hackerrank-world.html

2. Spent 30+ minutes to read the problem statement
http://juliachencoding.blogspot.ca/2016/07/build-palindrome-hackerrank-world.html

Actionable Items:

1. Work on suffix array first, learn basics first:
http://www.geeksforgeeks.org/suffix-array-set-1-introduction/

2. Read the article, get all questions related to suffix array in the contest:
(plan to spend 2 hours to study)
http://www.stanford.edu/class/cs97si/suffix-array.pdf

3. Review previous suffix array blog and C# implementation of suffix array:
http://juliachencoding.blogspot.ca/search/label/suffix%20array%20C%23

Productivity Tips for the Busy Tech Professional - pluralsight.com

August 1, 2016

Lecture website:

http://app.pluralsight.com/author/richard-seroter

One hour talk - great ideas!

Most favorite tips:

1. Decompose big problems - never see big problem, always small problems (10 out of 10)

2. Learn to say no, and leave buffer for important things to pop up.

3. Establishing a frame of mind - talk about his experience to write books etc.

I know what it takes to win. Forget everyone else and put the work in. @jianminchenMP, you can do it. https://t.co/ZRlVZXlFeG
— jianmin chen (@jianminchen) May 29, 2016

AWS study - pluaralsight

August 1 2016

Canadian statutory holiday - civic day, choose some study material from pluralsight.com - learning AWS.

Lecturer's website:

http://app.pluralsight.com/author/richard-seroter

Choose one or two in the following:

1. Amazon Web Service Databases in Depth

2. Architecting Highly Available Systems on AWS

3.
https://app.pluralsight.com/library/courses/aws-auditing-environments-security-best-practices/table-of-contents

Blog reading:
http://jane4532.blogspot.ca/

I know what it takes to win. Forget everyone else and put the work in. @jianminchenMP, you can do it. https://t.co/ZRlVZXlFeG
— jianmin chen (@jianminchen) May 29, 2016

Sunday, July 31, 2016

Binary search advanced

July 31, 2016

Study blogs:

http://blog.iderzheng.com/binary-search/

http://blog.iderzheng.com/binary-search-advanced/

Go over the blog, and write down great ideas one by one.

Will come back later.

Friday, July 29, 2016

K largest elements in the array - various ideas

July 29, 2016

Top k values in the array - review the following article:

http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

1. sorting the array O(nlogn)
2. use selection sort O(nk)
3. use sorting
4. use min heap
5. use max heap
6. use temporary array
7. use order statistics

7A. randomized selection algorithm - a dertministic algorithm that runs in O(n) in the worst case

http://www.cse.ust.hk/~dekai/271/notes/L05/L05.pdf
1. the idea is to divide n items into n/5 sets (denoting m sets), each contains 5 items. O(n)
2. Find the median of each of the m sets. O(n)
3. Take those m medians and put them in another array. Use Dselection() to recurisively calculate the median of these medians. Call this x. T(n/5)
4. ...

7B. Use QuickSort partition algorithm to partition around the kth largest number O(n).

7C. Sort the k-1 elements (elements greater than the kth largest element) O(klogk). This step is needed only if sorted output is required.

Summary of study for Leetcode 347 - K most frequent element in the array

July 29, 2016

Summary of study - selection algorithm and Language Integrated Query (LINQ)
1. http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/
2. http://www.ardendertat.com/2011/10/27/programming-interview-questions-10-kth-largest-element-in-array/

3. https://en.wikipedia.org/wiki/Selection_algorithm

4. https://msdn.microsoft.com/en-us/library/ms172192(v=vs.110).aspx

LINQ:

1. https://msdn.microsoft.com/en-us/library/bb397906.aspx

2. https://msdn.microsoft.com/en-us/library/bb399365(v=vs.110).aspx

3. http://igoro.com/archive/7-tricks-to-simplify-your-programs-with-linq/

Simplify your programs with LINQ - Language Integrate Query (LINQ) study series IV

July 29, 2016

LINQ - blogs to read:

http://igoro.com/archive/7-tricks-to-simplify-your-programs-with-linq/

http://igoro.com/archive/extended-linq-additional-operators-for-linq-to-objects/

Notes:

1. Initialize an array

int[] a = Enumerable.Repeat(-1,10).ToArray();

int[] b = Enumerable.Range(0,10).ToArray();

int[] c = Enumberable.Range(0,10).Select(i=>100+10*i).ToArray();

Enumerable.Repeat, Range,

no for loops necessary, using LINQ

2. Iterate over multiple arrays in a single loop

foreach(var x in array1)

DoSomthing(x);

foreach(var x in array2)

DoSomething(x);

LINQ

foreach(var x in array1.Concat(array2))

DoSomething(x);

LINQ operates at the enumerator level (?), it will not allocate a new array to hold elements of array1 and array2. So, space-efficient.

3. Generate a random sequence

Random rand = new Random();

var randomSeq = Enumerable.Repeat(0,N).Select(i=>rand.Next());

lazy nature of LINQ, the sequence is not pre-computed and stored in an array, but instead random numbers are generated on-demand, as you

iterate over randomSeq.

4. Generate a string

Generate a strign with the repeating pattern "ABCABCABC..." of length N.

string str = new string(Enumerable.Range(0,N).Select(i => (char)('A' + i%3)).ToArray());

string values = string.Join(string.Empty, Enumerable.Repeat(pattern, N).ToArray());

5. Convert sequences or collections

IEnumerable<string> strEnumerable = ...;

IEnumerable<object> objEnumerable = strEnumerable.Cast<object>();

List<string> strList = ...;

List<object> objList = new List<object>(strLsit.Cast<object>());

var objList = strList.Cast<object>().ToList();

6. Convert a value to a sequence of length 1

IEnumerable<int> seq = Enumerable.Repeat(myValue, 1);

7. Iterate over all subsets of a sequence

For small input, three problems:

subset sum

boolean satisfiability

knapsack problem

NP-complete problems -

solve easily by iterating over all subsets of some sequence:

Generics in .NET framework - Language Integrate Query (LINQ) study series (III)

July 29, 2016

Generics - article reading:

https://msdn.microsoft.com/en-us/library/ms172192(v=vs.110).aspx

Notes:

Advantages:

code reusability and type safety

Better performance - no need to box the value types

type-safe callbacks

lightweight dynamic methods vs entire assemblies

compiler will help to do type safety - enforce at compile time

The need for type casting and the possibility of run-time errors are reduced.

Generics streamline dynamically generated code.

placeholder (type parameters) for one or more of the type that they store or use.

.NET collections - Language Integrate Query - LINQ study series (II)

July 29, 2016

More reading about LINQ:

Google search keywords:

1. basic code patterns used for LINQ

2. .NET collections

https://msdn.microsoft.com/en-us/library/bb399365(v=vs.110).aspx

Notes from the above article:

LINQ queries

in-memory objects

object type

IEnumerable

IEnumerable<T>

object type implements IEnumberable or IEnumerable<T>

LINQ common pattern for accessing data vs standard foreach loops

3+ tips - how to read technical articles quickly

July 29, 2016

Small research - how to save time and more efficient to read technical articles?

Read technical articles - how to save time and more efficient?

Any order in the following:

1. Write down some notes:

keywords

things to remember

things not so clear

things to help memorize

2. Write down the ideas in the article -

short,

concise,

keywords only

And also,

sort by alphabetical order (rate 10 out of 10)
Separate Facts/ Arguments/ Rules/ Tips (rate 9 out of 10)

short chars to iterate (ex: S.O.L.I.D. Principle, easy to remember) (rate 8 out of 10)

Search more on google...

3. Get organized, maybe, better/ clear/ more pleasant ways

Introduction to LINQ Queries (C#) - Language Integrate Query (LINQ) study series (I)

July 28, 2016

LINQ:

https://msdn.microsoft.com/en-us/library/bb397906.aspx

Study more on LINQ:

1. LINQ - introduction

https://msdn.microsoft.com/en-us/library/bb397906.aspx

Languages for different data source:

SQL - relational database

XQuery - XML

LINQ -

a consistent model

basic coding patterns

For example: ? patterns -

Five most popular data source: (5 sources: A, N, S, X, any)

ADO.NET Datasets

.NET collections

SQL databases

XML documents

any other format

2. More reading about LINQ:

Google search keywords:

1. basic code patterns used for LINQ

2. .NET collections

https://msdn.microsoft.com/en-us/library/bb399365(v=vs.110).aspx

3.Generics in .NET framework

https://msdn.microsoft.com/en-us/library/ms172192(v=vs.110).aspx

4. LINQ - blogs to read:

http://igoro.com/archive/7-tricks-to-simplify-your-programs-with-linq/

http://igoro.com/archive/extended-linq-additional-operators-for-linq-to-objects/

http://www.asp.net/mvc/overview/older-versions-1/models-data/creating-model-classes-with-linq-to-sql-cs

Leetcode 347 - Find k most frequent numbers in the array - C++/ Java Solutions

July 28, 2016

Find k most frequent numbers in the array
Problem:
// nums = [5, 3, 1, 1, 1, 3, 73, 1]
// k = 1
// return [1]

// k = 2
// return [1, 3]

// k = 3

// return [1, 3, 5]

Code study: nothing can compare to code reading
C++ code to study:
use unordered_map and priority_queue
1. https://gist.github.com/jianminchen/cd9f536708f6ec42ae229d853c881361

2. use bucket sort -
https://gist.github.com/jianminchen/c3d49c11c090b91c94ae7b05bdc11786

https://gist.github.com/jianminchen/88f3e2d441c62ecb7d9d706d1b9bda37

3. use Map + std::sort
https://gist.github.com/jianminchen/3e5bba61847c5c84d95e1ca7806c81be

Java code to study:

1.use a min-heap - Java PriorityQueue class - underneath heap sort
https://gist.github.com/jianminchen/76b2b3196a4e58312e1ba1d0c288d941

2. use heap:
https://gist.github.com/jianminchen/2482dbacb59e464d94c4a4d16cbc6d3b

3. use bucket sort:
https://gist.github.com/jianminchen/0626a0cb673526d4b7b58698004b87b8

4. use Collections.sort - underneath merge sort,
https://gist.github.com/jianminchen/3d8fab01965efd19a0f72b2109501c8d

5. use quicksort partition

https://gist.github.com/jianminchen/99d2dea800b28e24456827946409d32d

Conclusion: Based on the analysis, the time complexity should be better than O(nlogn), if using heap sort or merge sort, when k is big enough close to n, then, O(nlogk) is close to O(nlogn).

However, the bucket sort is always O(n), so the time complexity is O(n), no matter k's size.