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.

Wednesday, July 20, 2016

CSS in-depth - pluralsight.com

July 20, 2016

Plan to find 6 hours to work on this course: 30 minutes a time, one by one.

CSS in-depth 6 hour course
http://app.pluralsight.com/author/estelle-weyl

1. Go over the slides on the website: (plan to take 1 hour first)
http://lanyrd.com/profile/estellevw/slides/

2. Julia's favorite - great input for Julia to build great mobile website!

http://estelle.github.io/mobilecss/#slide4

3. Get to know a new tool: YSlow
http://yslow.org/

Read 34 rules of web performance best practices and rules:

Yahoo!'s Exceptional Performance team has identified 34 rules that affect web page performance. YSlow's web page analysis is based on the 23 of these 34 rules that are testable. Click each performance rule below to see the details.

4. Julia loves the CSS Filter Effects

http://html5-demos.appspot.com/static/css/filters/index.html

(memorize 10 keywords: b b c d g h i o s s)
blur
brightness
contrast
drop-shadow
grayscale
hue-rotate
invert
opacity
saturate
sepia

5.
http://static.lukew.com/TouchGestureGuide.pdf

Core gestures:
Tap,
double tap,
Drag,
Flick,
Pinch,
Spread,
Press,
Press and tap,
Press and drag,
Rotate

6. Google page speed tools
- Analyze your site performance -

https://developers.google.com/speed/pagespeed/?csw=1

6B. Page Speed - Go over each main point for 5 minute study:
1. leverage browser caching

Leveraging Browsing caching for images, CSS and JS
https://www.siteground.com/kb/leverage-browser-caching/

http://stackoverflow.com/questions/23923039/wordpress-leverage-browser-caching

2. Enable compression
3. Defer parsing of JavaScript
4. Minimize request size
5. Specify a cache validator
6. Optimize images
7. Minify JavaScript
8. Minify HTML
9. specify image dimensions
10. Specify a character set
11. Specify a Vary: Accept Encoding Header
12. Avoid long-running scripts
13. Avoid CSS @import
14. Avoid bad requests
15. Enable Keep-Alive
16. Make landing page redirects cacheable
17. Minify CSS
18. Minimize redirects
19. Optimize the order of styles and scripts
20. Put CSS in the document head
21. Remove query strings from static resources

7. Sprites - reduce requests -

8. ImageAlpha

Reduce image file size - lossy compression

9. https://pngmini.com/

10. Responsive design - RDS

http://estelle.github.io/rwdpanacea/#slide12

11. Debugging tools for mobile website:

1. Charles proxy

https://www.charlesproxy.com/

2. fiddler

3. browser stack
www.browserstack.com

4. device anywhere
www,keynotedeviceanywhere.com

Julia's comment:
1. Great teaching, first CSS expert Julia knows - love the course - CSS in-depth - pluralsight.com
2. web performance best practices and rules - how many Julia breaks?

Introduction to website layout - pluralsight.com

July 20, 2016

Relax and try to find 3 hours to work on course provided by pluralsight.com

http://app.pluralsight.com/author/susan-simkins

HackerRank: World codesprint #4 - Roads in HackerLand - II - code study

July 20, 2016

First blog on this algorithm:

HackerRank: World codesprint #4 - Roads in HackerLand

http://juliachencoding.blogspot.ca/2016/06/hackerrank-world-codesprint-4-roads-in.html

Come back to work on this problem. Study editorial solution provided by HackerRank, and then,
review union find, minimum spanning tree algorithm with code first:

3 steps:
step 1: union find algorithm
step 2: minimum spanning tree
step 3: roads in hackerLand

Blogs to read:
1.
https://en.wikipedia.org/wiki/Minimum_spanning_tree

2.
http://www.ics.uci.edu/~eppstein/161/960206.html

Work on union find algorithm first: (step 1)
July 21, 2016

1. Union find algorithm - detect cycle

http://www.geeksforgeeks.org/union-find/

2. Union by rank and path compression

http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

Then, work on minimum spanning tree algorithm: (step II)

3.
http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/

4.
http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/

And then, study 10 code submission scoring 60/60 in Java, C++, C#. Practice one by one. (step III)

A better way to learn an algorithm - minimum spanning tree - work on a concrete example, make it fun learning experience.

1. Java implementation:
https://gist.github.com/jianminchen/20775a7ac1eeb83fa141e92633ea7d78

2. C++ 14
https://gist.github.com/jianminchen/28b5c3bf191a27250b67ce4e7656166b

3. C#
https://gist.github.com/jianminchen/7a21dfe2a62f1bcf4bc305480ef2f51e

4. C#
https://gist.github.com/jianminchen/8a15be7b83770d22647f34371fb48a97

5. C++
https://gist.github.com/jianminchen/5a3e680b86d2c5ffc0f090f29f074089

6. C++
https://gist.github.com/jianminchen/dcac67099aa7ddcb4497565f0732fe5e

7. C++
https://gist.github.com/jianminchen/10983fdcbbe15fef37bd73a60fe87430

8.

9.

10.

Follow up after 8 months

March 9, 2017
Read the tutotial first. And then write a C# solution, post a question on code review.

Tuesday, July 19, 2016

Leetcode 23: Merge K Sorted Lists

July 19, 2016

Problem statement:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Julia's first two practices in 2015:
1. Naive solution:
https://github.com/jianminchen/Leetcode_C-/blob/master/MergeKSortedLists_A_No23.cs

2. Implementation using merge sort: August 12, 2015
https://github.com/jianminchen/Leetcode_C-/blob/master/MargeKSortedLists_B_No23.cs

Come back to work on this problem in 2016, July 19:

Study those blogs:
1. Most favorite one:
http://bangbingsyb.blogspot.ca/2014/11/leetcode-merge-k-sorted-lists.html

Specially, the third discussion using divide and conquer, the conclusion that the merge solution is same time efficiency using heap solution Nklog(k), k is the number of arrays, and N is the length of the array, assuming that each array has same length.

1. http://www.cnblogs.com/TenosDoIt/p/3673188.html

2. http://bangbingsyb.blogspot.ca/2014/11/leetcode-merge-k-sorted-lists.html

3. http://codeganker.blogspot.ca/2014/08/leetcode_26.html

4. http://www.cnblogs.com/springfor/p/3869217.html

5. https://github.com/shawnfan/LintCode/blob/master/Java/Merge%20k%20Sorted%20Arrays.java

7. Excellent article - Julia, share your personal story as well.
http://codeganker.blogspot.ca/2014/08/leetcode_26.html

Read the article:

http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/04MergeQuick.pdf

Julia's question and answer:
1. Ideas to improve practice?
Answer:
Ideas to construct the practice:
1. Need to work on blog 7 - 3 solutions using C#, apply to "merge k sorted array".

Learn bottom-up merge sort, and know the time complexity as well.

C# solution - merge k sorted array - using bottom-up implementation merge sort
https://gist.github.com/jianminchen/d5fab2036647d380f20c908e91a81132

2. Write down the proof of "divide and conquer" time complexity comparison using heap, O(nk logk)
Show some simple example to help understand the time complexity.
3. Warm up the code practice a few times, aiming to write 20 minutes for a solution
4. Need to figure out master theorem quickly.

2. Can you work on a small example to illustrate some analysis?
Copy the image from Princeton's lecture note:

3. Can you write some C# code this time to make your own mark?

Actionable items:

Read the article, and write down questions - prepare a further reading list. (30 minutes reading )
https://en.wikipedia.org/wiki/Merge_sort
Notes:

keywords: (remember 14 keywords)
average and worst-case performance
Bitonic Mergesort
Bottom-up implementation
comparison-based sorting algorithm
external merge sort - disk/ tape drives

external merge sort
master theorem
merge sort - not inplace - must be allocated for the sorted output to be stored in
parallel mergesort
polyphase merge sort
natural merge sort - similar to a bottom up merge sort

stable sort,
TimSort,
tiled merge sort algorithm
Top-down implementation

Variants:
1. reducing the space complexity
2. cost of copying

locality of reference

memory hierarchies
cache-aware version of merge sort algorithm
tiled merge sort algorithm

Parallel merge sort

Merge sort parallelizes well due to use of the divide-and-conquer method.

-
Comparison with other sort algorithms

heapsort vs merge sort

O(1) auxiliary space instead of merge sort's O(n).

efficient quicksot implementations generally outperform mergesort for sorting RAM-based arrays - ?

merge sort is a stable sort and is more efficient at handling slow-to-access sequential media.

Merge sort is often the best choice for sorting a linked list.

the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others(such as heapsort) completely impossible.

Java, Array.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficicency switch to insertion sort when fewer than seven array elements are being sorted.

Python uses Timsort, another tuned hybrid of merge sort and insertion sort.

--
More reading:
30 minutes to review:
http://algs4.cs.princeton.edu/lectures/22Mergesort.pdf

5 minutes reading:
http://infolab.stanford.edu/~ullman/fcscnotes/notes9.pdf

20 minutes reading - plan to read - parallel merge sort
http://stanford.edu/~rezab/dao/notes/Lecture04/cme323_lec4.pdf

Read 10 minutes a time - get lost and enjoy reading ...

http://web.archive.org/web/20150120063131/https://android.googlesource.com/platform/libcore/+/jb-mr2-release/luni/src/main/java/java/util/TimSort.java

Will come back very soon.

Monday, July 18, 2016

Leetcode 173: Binary Search Tree Iterator - facebook code lab

July 18, 2016

Problem statement:

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

The first call to next() will return the smallest number in BST. Calling next() again will return the next smallest number in the BST, and so on.

Note: next() and hasNext() should run in average O(1) time and uses O(h)memory, where h is the height of the tree.
Try to optimize the additional space complexity apart from the amortized time complexity.

The time estimated is 41 minutes in facebook code lab.

Plan to work on this problem in short future.

A small research how top tennis player progresses to be top 7 from 152 ranking

July 18, 2016

Julia likes to spend some time - more than 1 hour to do some research every day. She chose to study the Wimbledon runnup - Milos Raonic. She was too busy to play tennis to do some study about top players.

Spend time to get familiar with a tennis player - Milos Raonic -
Watch the tennis player - Milos Raonic`s interview

How to get top 37 from over 152 ranking in just one month?
Children's foundation
1. https://www.youtube.com/watch?v=ZIk6k-RJk8E

Philanthropy[edit]

In 2011, while recovering from a hip injury sustained at Wimbledon, Raonic decided to become involved with philanthropic work, focusing on helping disadvantaged children.^[38] The following year, in 2012, Raonic launched the Milos Raonic Foundation,^[39]^[40]^[41] which aims to "support children from disadvantaged backgrounds in order to remove economic, physical and other barriers that might prevent them from becoming healthy, productive members of society. ... In the initial stages of its work, the foundation will focus, in particular, on children with physical disabilities."^[42]

Is Time Running Out?
2. https://www.youtube.com/watch?v=4IeeDF5Qla4

John McEnroe talked about his coaching - how to help Raonic?

3. https://www.youtube.com/watch?v=9Kd2cuhp5LI

4. https://www.youtube.com/watch?v=qYt98fHNksE

Hardwork pays off, but the timing may not be you expect.

Raonic's expectations sky high - Julia likes the seeded tennis professional players, really smart and also good at talking/ sharing.
5. https://www.youtube.com/watch?v=fTAR38gcL6U

Julia's most favorite:
How to handle the success?
Sudden success? It is difficult to manage the success as managing failure.
How does Raonic copy with the sudden success?

6. https://www.youtube.com/watch?v=WLzADfghPDA

7. https://www.youtube.com/watch?v=FwVgrhWq6oA
Took risk to turn down tennis scholarship for college, and chose to be a professional tennis player. There is a life after tennis, and tennis professional can be very short career.

Blogs:
Leetcode 47 Permutation II

Leetcode 75 Sort colors
http://www.jianshu.com/p/82fe72072226

Leetcode 286 Walls and Gates

Majority - facebook code lab - optimal solution

July 18, 2016

Problem statement:

Given an array of size n, find the majority element. The majority element is the element that appears more than floor(n/2) times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example :

Input : [2, 1, 2]
Return  : 2 which occurs 2 times which is greater than 3/2.

Think about brute force solution first,
sort the array first, and then, medium of the array is the majority element. And the time complexity is O(nlogn).
If the size of the array is even, then, medium is two nodes in the center. And if the size of the array is odd, the medium is the middle one.

Spent 10 -15 minutes to find the optimal solution, beat the time complexity O(nlogn). The array does not need to be sorted, try to think about the partition of the array, pivot value - how to find the one?

No progress in over 15 minutes. Then, read the hint from the facebook code lab.

Optimal solution idea:
Just try to go through the array once, and set the majority element, and keep the count of majority element.

Really like the hint from facebook code lab:
If two distinct elements are removed from the array, the majority element is still the same one in the array.

1st practice:
https://gist.github.com/jianminchen/c6f01498a6de4ca2df3d813b375a3d6d

Study the code provided by facebook code lab:
https://gist.github.com/jianminchen/7406702476e8fe7b58934fccb9a4e674

The code is much simple and short.
Julia wrote ugly if statement for 4 cases, but the editorial solution only has one if statement. How does that happen?

The reasoning is ~~more~~ ~~stronger~~ one step further, if the count is 0 for majority element, then just set last one as majority element and count = 1. No candidate, and then, set the last one as the candidate. There is no worry about it. But make the code more simple, not too much if statement.

Sunday, July 17, 2016

Big Data Analytics with Tableau - pluralsight.com

July 17, 2016

Plan to spend a few hours to study the course on pluralsight.com

Saturday, July 16, 2016

DiffK - facebook code lab - practices

July 16, 2016

Problem statement:

Given an array ‘A’ of sorted integers and another non negative integer k, find if there exists 2 indices i and j such that A[i] - A[j] = k, i != j.

Example:

Input :

    A : [1 3 5] 
    k : 4

Output : YES

as 5 - 1 = 4

Return 0 / 1 ( 0 for false, 1 for true ) for this problem

Try doing this in less than linear space complexity.

First practice: The solution is not optimized for the time. Almost there.

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

Second practice: The solution works
https://gist.github.com/jianminchen/f24bc4f8561f29ef5a98d8bd3460d8dd

Study the solution provided by code lab:

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

Remove duplicates from Sorted Array

July 16, 2016

Problem statement:

Remove duplicates from Sorted Array
Given a sorted array, remove the duplicates in place such that each element appears only once and return the new length.

Note that even though we want you to return the new length, make sure to change the original array as well in place

Do not allocate extra space for another array, you must do this in place with constant memory.

Example:
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

First practice:

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

Reverse unsigned 32 bit integer - facebook code lab - how to express Math.pow using bit shift

July 16, 2016

Julia enjoyed the workout using facebook code lab. She actually learned a few things about Type conversion in bit manipulation:

int - java - 32 bit
Java does not have unsigned int, use long.
But it causes problems!

She struggles and then she learns lessons.

This blog has everything about more than 5 practices, but it is hard to know what is going on.
http://juliachencoding.blogspot.ca/2016/07/reverse-unsigned-32-bit-integer.html

So, dedicate one blog on this issue:

2nd practice: not working, error on 32 bit integer, left most significant bit 1 means negative number.
https://gist.github.com/jianminchen/7bfdcd0c1643bf01c2bf6ba7acea6f70

Sorry, wrong answer. Your program's output doesn't match the expected output. You can try testing your code with custom input and try putting debug statements in your code.

Your submission failed for the following input:

A : 3

Your function returned the following :

-1073741824

The expected returned value :

3221225472

line 11: ret += 1 << power;
1 is int with 32 bit.
http://stackoverflow.com/questions/1032982/is-a-java-int-always-32-bits

should be: ret += ((long)1) << power;

3rd practice: fail to fix the issue.
https://gist.github.com/jianminchen/2b753978ffe983600a031a0fcda7b3a6

4th practice: Use bit manipulation - left shift to get 2^n value - code is working

https://gist.github.com/jianminchen/6a5c1ab71b01414f008b22386000ee59

Everyone faces challenges on court and I’m no different. Get out on court and overcome yours to #CreateYourMark pic.twitter.com/RSNn7AqFch
— Ana Ivanovic (@AnaIvanovic) May 21, 2016

Reverse unsigned 32 bit integer - facebook code lab - 5th practice - C++, swap bits

July 16, 2016

First, study the solution provided by lab, great idea:

Reversing bits could be done by swapping the n/2 least significant bits with its most significant bits.

The trick is to implement a function called swapBits(i, j), which swaps the ‘i’th bit with the ‘j’th bit.

If you still remember how XOR operation works:

here

0 ^ 0 == 0, 
1 ^ 1 == 0, 
0 ^ 1 == 1, and 
1 ^ 0 == 1.

We only need to perform the swap when the ‘i’th bit and the ‘j’th bit are different.

To test if two bits are different, we could use the XOR operation. Then, we need to toggle both ‘i’th and ‘j’th bits.

We could apply the XOR operation again.

By XOR-ing the ‘i’th and ‘j’th bit with 1, both bits are toggled.

Bonus approach (The divide and conquer approach):

Remember how merge sort works? Let us use an example of n == 8 (one byte) to see how this works:


              01101001

             /        \

           0110       1001

          /   \       /   \

         01    10    10    01

        /\     /\    /\     /\

       0  1   1  0  1  0   0  1

The first step is to swap all odd and even bits. After that swap consecutive pairs of bits, and so on …

Therefore, only a total of log(n) operations are necessary.

study the code in C++:
https://gist.github.com/jianminchen/3526dd68e72ae97563cdd61580052016

Swap odd bit and even bit of unsigned 32 bit integer

July 16, 2016

Work on bit manipulation is so much fun. Julia likes to get workout on bit manipulation, and work on the code one by one.

This blog has everything, but it is hard to know what is going on.
http://juliachencoding.blogspot.ca/2016/07/reverse-unsigned-32-bit-integer.html

For the first step, you would do:

    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);

Julia's comment:  5 minutes workout - how to swap odd bit and even bits?
5 = 101
How to swap odd bit and even bits?
In other words, odd bit becomes even bit; even bit goes to odd bit

First, odd bit shifts to left; even bit shifts to right.

32 bits: 0101 0101 0101 0101 0101 0101 0101 0101
all odd bit number in x:
  x & 0x55555555
left shift 1 bit:
(x & 0x55555555) << 1)

So, even bits shift to right;
A in bits presentation: 1010
all even bit number in x:
x & 0xAAAAAAAA

After the swap, the new value is
   x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
-- end of Julia's comment --