Tuesday, May 31, 2016

Leetcode 124: Binary Tree Maximum Path Sum - reasoning and analysis (I, II, III)

May 31, 2016

Review the blog:


Practice on May 31, 2016, first version:


Second version: add more comment:

The above second version line 133 - line 137 can be simplified as one statement:
int value = root.val + ((left>0)?left:0) + ((right>0)?right:0);

Third version: line 133 - line 137 -> one line

Reasoning and analysis (I):

Write some reasoning and analysis.

Let us talk about an example first:
In the practice on May 31, 2016, line 60 - 79, test case 3:

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.

If we do not use recursive solution, try to use brute force solution:
1. Find any two nodes in the tree, and then find the path, and calculate the sum of path.
(June 24, 2016 but least common ancestor is much more difficult problem to solve!)
For example, maximu path, we have to find the common ancestor of those two nodes with value 6 (root->left) and node with value 2 (root->right->right->left) first, and then, the path can be formed.

So, the recursive solution can be based on the following facts:
1.  Any node in the tree can be visited from top to down, preorder traversal, once. And the node is treated as root node of one subtree.

2. So, just consider the maximum path starting from root node, this way, the recursive function can be set up.
2.  Any two nodes in the tree  ->  the root to any node in the tree (simplify the case)
3.  the maximum path in the above diagram: 6->9->-3->2->2 -> construct by the root to any node in the tree.

 value1:  Root node with value 9,
 value2:  Root-> left node's maximum value of "the root to any node in the tree"
 value3:  Root-> right node's maximum value of "the root to any node in the tree"

 the maximum path = value1 +(value2>0?value2:0) + (value3>0?value3:0)

So, the recursive solution can be formed quickly.

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

Reasoning and analysis (II):
Add one more explanation to walk through the example:
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.

Reasoning and analysis (III):
Creative way to solve the problem:
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


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

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

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

Goal: make it 10 minutes to add

So, overall, it should be less than 20 minutes code writing. Follow the function - do one task only. a time.

1. Step 1: write a simple recursive function - preorder traversal. Pay attention to negative value node, just ignore them if it is. 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. Step 2: add 2 lines code (line 104, line 105), 3 changes - add one more argument (line 96, line 101, line 102):

Leetcode 103: Binary Tree ZigZag traversal - a practice

May 31, 2016

Review the blog:

practice in 2015:

Warmup practice on May 31, 2016, write a C# solution again:

Practice notes:

1. source code line 107 ,  Stack, use ref, pass reference.

Lookup why Stack is different from Array. Array reference is passed automatically.

Read the blog:

2. Extract a function named swap(), actually, the last practice:

line 57, Stack<int> tmp is declared, but line 92 tmp is used. The scope is too large to pay attention. So, extract it to a function.

3. The last practice first while loop on line 59:

It is confusing, so in current practice, line 72, while(true),
line 72: while(true)

later, on line 112, break the while loop.
line 112: if (currLevel == null || currLevel.Count == 0)
113: break;

4. line 61, if (root == null), return empty list instead of null pointer.

Nov. 14, 2016
Google/Bing Search Result:
zig-zag traversal of a binary tree in c

Review the blog, and then, need to document about array reference passing in C#, see stackoverflow article:

Monday, May 30, 2016

Distributed System, noSQL, operating system Quick Review

March 30, 2016

1. Operating System - Review

Spend one hour to study:

Review operating System:

1. http://blog.csdn.net/u012290414/article/details/48782375

2. Distributed System

Network service and app framework

Load balance, caching, replication, rest, nosql

Reading time:


3.Jquery github open source project - source code style.

4. Visit this Leetcode blog - most popular blog I have seen - over 10,000 visitor


5. NoSQL

Learn a few key features:
1. "non SQL" or "non relational"
2. Compared to relational database, tabular relations -
3. Motivation of NoSQL:
Data structures in NoSQL are different.
name of data structures: key-value, wide column, graph, or document
4. ACID - Atomic, Consistency, I - Isolation, D - Durability
NoSQL - "eventual consistency"

Leetcode 126: word ladder II - using BFS - Queue, Set Paths (Practice VI)

May 30, 2016

Study the blog:

And continue to write C# solution - focus on coding, design ideas.
1. First practice, with a bug on just after line 111 - missing to add tmpList to newList.

2. Fix the bug and pass the test case, add line 112:

Questions and Answers:

1. How is the practice?

Here are some sharing:
1. Write down the comment about the idea to solve the problem, from line 23 - line 58

Good idea is to solve 50% of problem. Repeat the idea in the following:

Explain the idea using the test case:
                             dot -> dog
          hit->hot ->                    -> cog
                              lot -> log
          so, the queue process is (breadth first search)
          first  layer:        hit
          second layer:   hot
          third  layer:      dot, lot
          forth  layer:      dog, log
          fifth  layer:        cog
          build ladders step by step, from startWord to current. 
          Dictionary<string, List<List<string>>> ladders
          each string will be the key in ladders
          hit -> hit
          hot -> one list, {"hit", "hot"}
          dot -> one list, {"hit", "hot", "dot"}
          lot -> one list, {"hit", "hot", "lot"}
          dog -> one list, {"hit", "hot", "dot", "dog"}
          log -> one list, {"hit", "hot", "lot", "log"}
          cog -> two lists,
                           {"hit", "hot", "dot", "dog", "cog"}
                           {"hit", "hot", "lot", "log", "cog"}

2. Some highlights?

First of all, first writing is wrong. There are 5 levels, 4 loops and then one if, Julia got confused the position of code.
So, marks are added in the comment just after the loop - start statement and also close }.
Work on indentation - Better to write down your own marks. 

line 75   // level 1, while loop
     line 88   // level 2, for loop
          line 93   // level 3, for loop
                  line 97   // level 4, for loop
                      line 104  // level 5, if statement
                      line 121 //  end of level 5, }
                  line 122 // end of level 4, }
          line 125 // end of level 3, - end for loop for hop string length
    line 128   // end of level 2, - processing - all nodes in the same distance in the queue
line 139  // level 1 - processing queue - queue.Count > 0

line 95, char variable name: char backtracking_char, just friendly remind to do backtracking later on line 124.

line 102, string variable name change: newstring -> nextHop, hopefully the current one is more meaningful.

3. Actionable items?

Write again a few times, try to finish coding in 30 minutes, and write down issues not resolved.
Coding is like sports, just do it! 

4. More to share about the algorithm?

Share one graph to illustrate the graph problem of word ladder:
5. A lot of people complained the problem is too tough. Julia, you miss the most important things in the design?
Time out is a big issue. And also, we need to discuss how to avoid a cycle in the list; multiple paths can be found from start word to end word.
Challenge 1:  The visited word must be removed sometime to avoid a cycle;
Challenge 2:  When to remove visited words from dictionary properly? Same distance, one word can repeat multiple times.

Sure, let us talk about it!
on line 84, inside the while loop, Hashset<string> nextHops_BFS are defined. We need to examine this Hashset:
on line 120, nextHop is added one by one to the HashSet, but no action is taken on the HashSet. Lazy processing here!
Until all nodes in the current layer are processed, dequeue from the queue. From line 133 - 137, add next layer hops into the queue, where to find the nodes - nextHops_BFS . Remove the words from wordList just before adding to the queue.

Put line 135 just after line 120, and see what is difference.
The program will generate no output for test case:
                              dot -> dog
          hit->hot ->                    -> cog
                              lot ->  log

log word's next layer is cog, and dog word's next layer is cog as well. Both routes have same word, terminate word. cog can not be removed from wordDist Hashset until two routes are processed both. Actually, the graph should look likes the following: 
                             dot -> dog -> cog
          hit->hot ->                   
                              lot -> log -> cog 

In fifth layer, cog word shows up on line 102 twice:
line 102 if (wordList.Contains(nextHop))
So, 2 lists can be added with the same word "cog" as last one.

It is important to keep wordList untouched until the whole layer is processed, then, remove
words in HashSet nextHops_BFS from wordList. 

Rules to obey in the design:1. The same word does not repeat twice in the same list. For example, hit->hot->lot->log->lot-log..., it may go on forever. 

2. One word does not show up in more than one list, except start word and end word. For example, test case, hit, cog are only exceptions. 
Not True. "hot" shows up in two lists. 

3. Words in the distance n should not be any word in distance 0 to n-1. 
                             dot -> dog
          hit->hot ->                    -> cog
                              lot ->  log

So, when dog or log are processed in the queue, all words less than 4, hit, hot, dot, lot should be removed from HashSet wordList. 
Need to go through those cases one by one. 

Actionable items:
Read the blog and then implement the solutions as well.

Leetcode 126: word ladder II - study C++ code using BFS - Queue (Practice V)

May 30, 2016

Study the code:

C# code:


Questions and Answers:

1. How is the practice? 

Julia spent more than 1 hour to work on practice.

Test case:
hit -> hot -> dot -> dog - > log
hit -> hot -> lot -> log  ->  cog

1. Line 40 - 43, add beginWord into Dictionary. The code can be extracted to one standalone function.

2. Line 52, inside while loop, HashSet, try to figure out the purpose, named: bfs_nextNodes
    same distance nodes to startWord will stay in the same HashSet.

3. Line 70, arr.ToString(), debug runtime error, the string will be "new String()". Bug is fixed, using "new string(char[])"

4. Line 84 - 87, add discussion of ladders.ContainsKey(newstring), otherwise,
    ladders[newstring].AddRange(newList) through runtime error. ladders[newstring] is null pointer.
Test case:
1. First time try, only one path is added; miss the second path (hit -> hot -> lot -> log  ->  cog)

5. line 99, Dictionary API ContainsKey, not Contains, vs. HashMap

2. What is the idea to implement the solution using your own words?

The idea is much clever. Explain the idea using the test case:
                             dot -> dog
          hit->hot ->                    -> cog
                              lot -> log
          so, the queue process is (breadth first search)
          first  layer:        hit
          second layer:   hot
          third  layer:      dot, lot
          forth  layer:      dog, log
          fifth  layer:        cog
          build ladders step by step, from startWord to current.
          Dictionary<string, List<List<string>>> ladders
          each string will be the key in ladders
          hit -> hit
          hot -> one list, {"hit", "hot"}
          dot -> one list, {"hit", "hot", "dot"}
          lot -> one list, {"hit", "hot", "lot"}
          dog -> one list, {"hit", "hot", "dot", "dog"}
          log -> one list, {"hit", "hot", "lot", "log"}
          cog -> two lists,
                           {"hit", "hot", "dot", "dog", "cog"}
                           {"hit", "hot", "lot", "log", "cog"}

Leetcode 126: word ladder - a practice (IV)

May 30, 2016

Study the Java code shown in the blog:

Here is the C# code to use the same ideas in the above blog (programcreek.com)

Previous blogs on Leetcode 126: word ladder

Study Java Code,

and then, write C# code, and then, improve code readability, play with styles etc. Time spent: more than 8 hours +.
the code runs ok, but need more changes:
1. https://gist.github.com/jianminchen/dc64ad0cf06220d293278f874ac07ad4

2. http://juliachencoding.blogspot.ca/2016/05/leetcode-126-word-ladder-ii-warm-up.html
3. http://juliachencoding.blogspot.ca/2016/05/leetcode-126-word-ladder-ii-warm-up_29.html
4. http://juliachencoding.blogspot.ca/2016/05/leetcode-126-word-ladder-ii-warm-up_52.html

Questions and Answers:

1. How about the practice? 

The practice is with better ideas, short code.
idea 1: To track the actual ladder, we need to add a pointer that points to the previous node in the WordNode class.

For example, hit -> cog, each hop with distance 5:
hit, prev = null, 
hot, prev = hit, 
dot, prev = hot
dog, prev = dot
cog, prev = dog
So, using BFS - breadth first search, queue, once the WordNode with "cog" is found, then, whole path can be retrieved. This is a singly linked list. 
Same applies to the path: hit->hot->lot->log->cog

idea 2: In addition, the used word can not directly removed from the dictionary. The used word is only removed when steps change.

2. C# practice vs. Java practice?
Java code - use LinkedList as queue, so Julia tried to use C# LinkedList to implement the queue as well. 
C# LinkedList API used in the practice:
line 48, line 115: AddLast()           <- queue.enqueue, force to add at the end
line 63: First()                 <- queue.Peek(), just look up the front node's value, but do not remove the node
line 64: RemoveFirst()   <- queue.Dequeue()

C# practice: 
line 101: string.ToCharArray()
line 112: new string(char[])  - constructor 

Amazon Leadership principle study

May 27, 2016

 Julia likes to do small and quick research about Amazon leadership principle.

 Here is the public link about Amazon leadership principles:

 Videos she watched and she understands the basic things - things can be controllable, long term sustainable - customer central culture, not on competitor etc.. Do not feel good when stock go up 10%, feel 10% smarter; vice versa.

 1. Interview: Amazon CEO Jeff Bezos (1 hour video)

1. Amazon headquarter campus is in downtown vs.  remote area - environment concern.
2. Senior manager stress level - More control, and should be less stress.
3. AWS - tremendous transaction of distributed computing, resource etc.

2. https://www.youtube.com/watch?v=56uxnKbvbJ4

1.big selection 2. fast and quick delivery, 3 price - customer concerns, repeated customers.
offer wider selection, lower prices and fast, reliable delivery.

Intense hard working, high IQ; can hire great people.

3. Building Amazon One Box at a Time

4. BBC documentary: Amazon - Lead principles study:

5. Jeff Bezo's Top 10 Rules For Success

6. Read the article:

1. In 2006,  Amazon Web Services as a standalone business. AWS story - processing 150,000 picture in 2 hours, cloud service, in-house takes 15 days, cost 200 dollars.
2. TV ads about customer of Kindle reader gets hurt, Jeff asked to replace the funny video. Care about customers.
3. Two pizzas feeds a team, team is too big.
4. Even the tiniest delay in loading a Web page isn'’t trivial. Amazon has metrics showing that a 0.1 second delay in page rendering can translate into a 1% drop in customer activity.
The respect for that ethic explains why Amazon screens its job candidates for a strong bias to action and an ability to work through ambiguity. Both help identify people who can innovate fast and do right by the customer. One popular interviewing tack: asking candidates to create an action plan as brand managers in an area where they lack any direct knowledge— and then being told they have no budget.
Stumped candidates will find their path into Amazon slipping away. Those who cobble together guerrilla answers—informal polls through free online tools such as SurveyMonkey—tend to thrive at Amazon. They are the same people who might have challenged Bezos in math class and also succeeded on Grandpa’s ranch.

To ­attend two days of call-center training each year. The payoff: humility and empathy for the customer.

7. 2001 Interview "How Did Jeff Bezos Start Amazon? His Background, the Internet & the Future of E-Commerce (2001)"

Stock market is a voting machine in short term, in long term it is a weighing machine.

More reading - Chinese articles: (June 1, 2016)


8. Stanford university artificial intelligent graduate certificate

9. Amazon student program

June 12, 2016
10. UTC 2012 Hall of Fame - Jeff Bezos Keynote
Amazon is looking for people thinking out-of-box, creative, be able to invent something.

June 19, 2016
2005 Entrepreneurship Conference - Taking on the Challenge. Jeffrey Bezos, Amazon


August 30, 2016
Microsoft research - Amazon 14 leadership principles


Take notes on Sept. 5, 2016 10:17pm
1. AWS - how to get there?
Separate application team from infrastructure  team, force infrastructure team to make external customer's happy, high-reliability product

2. Future release - concept?

Nov. 1, 2016

Nov. 5, 2016 How to Get a Job on Amazon’s Alexa Team

Nov. 22, 2016
Look into the blog - Find out about Amazon device team

Amazon lab 126 - 1 stands for a, 26 stands for z - 126 stands for A-Z


Dec. 14, 2016

Take some notes:

The Method
Second Round:
Presentation: we evaluate their communication skills, their thought process, and their depth of knowledge in the specific area of machine learning

The score:
We evaluate the candidate's possession of the technical and functional knowledge and skills for the role and demonstration of our leadership principles throughout each phase of the process.

How to Ace it
Do speak up. "Be a loud thinker. Discuss your thought process". Also, have "a clear communication style."

Do ask questions about the job, and show that you're "interested in our efforts and [have] new ideas on how to improve them."

Do be obsessed with the customer. "We would like to see candidates that put a considerable amount of weight on the customer experience when making decisions."

Don't be vague. For example, "to avoid ambiguity the candidate can reply: I used SVM to build a classifier given 100K data points," instead of "I used some technique to build a classifier with the given data point."

Don't be stubborn. You don't want to demonstrate "an inability to think flexibly and open-mindedly" or be "missing hints from the interviewer and insisting on a particular approach."

January 2 2017

Talk about interview by Amazon VP

June 25, 2017

Amazon leadership interview - blog is here.

Sunday, May 29, 2016

Leetcode 126: Word Ladder II - warm up practice (III)

May 29, 2016

 Share one tweet from profession tennis play Angelique Kerber (2016 Australian Grand Slam champion):

"Everyone asks me what's next. I'm here to stay, taking it one game at a time."

 One algorithm at a time. Still work on Leetcode 126: word ladder II,

 Here is the practice version on May 28, 2016, less than 15 hours ago.

 And then, she spent over 2 hour to make changes on the code, here is the 2nd version:


 And then, she continued to spend over 2+ to write the code again, here is the third version:


Question and Answer:

1. What do you learn through the practice? 

Julia created three bugs: 
1. First, function call on line 59, return dist = 0. 
Because endWord, such as "cog" should be added to HashSet<string> and then use it in the function call on line 59, 
instead of original HashSet<string> wordList. 

line 144, wordList.Contains(trial), last word "cog" is not in wordList, therefore, function can not function normally. 

2. Second, function call on line 73, wordListExtended should be used instead of wordList, 
otherwise, the endWord is not in HashSet<string>, cannot find ladders. 

line 247 cannot return true when ij_word is endWord "cog": wordList.Contains(ij_word)

3. Third, in function getLadder_DFS_Backtracking  on line 204 - 271, line 219 is commented out, 
dictionary[runner] < dist, cannot be =, otherwise, ladders with distance 5 and 6 both are included. Instead of 2 list, 
there are 6 lists. 

2. What improvement does this practice make? 

2nd version:

3rd version:

a.  In 3rd version, remove 2nd version from line 37 - 44.
b.  In 3rd version, line 71, variable name is changed from visited to visitedHelper.
c.  In 3rd version, function findDistAndPrepareDictionary_BFS_UsingQueue, last line,
d.  line 153, return 0; in 2nd version, length is return.
e.  In 3rd version, line 106, int length - variable, can be removed, no use at all.
f.  In 3rd version, removed 2nd version nested if - line 141. 
g. In 3rd version, Tuple class is used to avoid using two queues.

Actionable items:

1. More practice, goal is to write executable code with correct result.
2. Study more solutions.

Leetcode 126: Word Ladder II - warm up practice (II)

May 29, 2016

 Share one tweet from profession tennis play Angelique Kerber (2016 Australian Grand Slam champion):

"Everyone asks me what's next. I'm here to stay, taking it one game at a time."

 One algorithm at a time. Still work on Leetcode 126: word ladder II,

 Here is the practice version on May 28, 2016, less than 15 hours ago.

 And then, she spent over 2 hour to make changes on the code, here is the new version:


 Here are the list of things she made the change:
1. line 21, class member variable is commented out. ladders.
    It is replaced by an argument in the function:
line 189 getLadders_DFS_Backtracking, 8th argument - ladderHelper

2. line 27, comment out member variable ladderHelper, pass an argument in
function getLadders_DFS_Backtracking line 189, last argument: List<string> ladderHelper

3. line 60, change function name to getLadders_DFS_Backtracking, remind myself two things:
1. it is a DFS algorithm
2. Do not forget to do backtracking

4. line 102, change function name to getLadderLengthAndDictionary_BFS. BFS stands for 
breadth first search.

5. line 203, line 204, add two more explanation variable, make code more readable.

6. line 220, add explanation variable, backtracking_char, helps user to understand 
the backtracking process.

7. line 221, add explanation variable replace, the char will be replaced by any one of from 'a' to 'z'.

8. line 225, 226
if(j == replace)

Make the code more flat, no nested two if statements, only one if statement.

9. line 229, ij_word, ij prefix helps to track index i and index j.
10. line 245, line 249, line 251 3 backtracking statements.

Saturday, May 28, 2016

Leetcode 126: word ladder II - warm up practice

May 28, 2016

  Share professional tennis player Kristina Mladenovic tweet:

I know what it takes to win. Forget everyone else and put the work in.

Spend one hour to work on the word ladder II, Leetcode 126.
Previous blog:
http://juliachencoding.blogspot.ca/2016/05/leetcode-127-word-ladder-medium_24.html work on one test case:
hit-> cog
Dictionary<string, int> has entries:
Let us talk about a test case to help understand the work:
           hit -> cog
           Two transformation paths:
                         dot -> dog
           hit -> hot ->            -> cog
                         lot -> log
           dist value is 5
           Dictionary<string, int>
           key    value      new value
           hit     0            4
           hot     1            3
           dot     2            2
           lot     2            2
           dog     3            1
           log     3            1
           cog     4            0

Extract a function called resetDistanceFromEnd