Thursday, June 30, 2016

JavaScript Array.of Function study

June 30, 2016

Start to work on JavaScript 29 function one by one. Focus on one function at a time.

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

return an array from passed in arguments.

Syntax:
Array.of(element0[, element1][, ...][,elementN]);

Read blogs:

https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/of

https://gist.github.com/rwaldron/1074126

5 functions - indexOf(), filter(), forEach(), map(), reduce() (1 hour study June 30, 2016 10:00pm - 11:00pm)
Learn technique called demethodizing.
http://colintoh.com/blog/5-array-methods-that-you-should-use-today

JavaScript Array's reduce Method:
https://www.youtube.com/watch?v=J21rsVw_NBE

accumlator

Spend 1 hour to watch the video:
Code genius - Using JavaScript to Teach JavaScript by John Resig

https://www.youtube.com/watch?v=H4sSldXv_S4


Actionable Items:
Use JsFiddle to edit JavaScript code snippets.

JavaScript Array.from function - 60 minutes study

June 30, 2016

Array.from study


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



two concepts: 

1. array-like object, an iterable object. 

Array.from 
syntax: Array.from(arrayLike[,mapfn [,thisArg]]); 

Array-like object:

http://stackoverflow.com/questions/11886578/creating-array-like-objects-in-javascript

Iterable object:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_Generators

JavaScript String, Array, TypedArray, Map and Set are all built-in iterables.

Read JavaScript Map
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

JavaScript Array - 2+ hour study

June 30, 2016

Work on JavaScript Array - Design a drill to understand JavaScript Array, and learn some API design.

Target:
Memorize all 29 API, be able to write down API function syntax, understand why, how for each API.


Each practice takes 20 minutes:
10 minutes to remember Array properties.
10 minutes to remember Array 29 APIs.

Prepare the study content first and document the experience:

1. PROPERTY:
3 properties:
constructor,
length
prototype

constructor property:
https://msdn.microsoft.com/en-us/library/jj155291(v=vs.94).aspx

length:
array is sparse, so the array is not contiguous. The length is not necessarily the number of elements in the array.
https://msdn.microsoft.com/en-us/library/d8ez24f2(v=vs.94).aspx

Prototype:
https://msdn.microsoft.com/en-us/library/jj155285(v=vs.94).aspx

2. JavaScript array 29 methods:

Spend 10 minutes a time to remember all the function names,
Spend 10 minutes to guess each API's functionality, and details about arguments, how it is designed. 
Spend 10 minutes reading/ practice/ ask questions. 
Repeat the process. 

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

write down my guess:  (June 30, 2016 - too honest here! Will improve JavaScript knowledge, learn design!)
Array.from   - copy array from, input argument is array.
isArray      - Array.isArray(arr)  input argument arr is array
of           - ? wild guess -
concat       - arr1.concat(arr2), concatenate the string
entries      - entries  - arguments: startIndex, endIndex, return subarray?

Discussion:
Array.from study
two concepts: 
1. array-like object, an iterable object. 

Array.from 
syntax: Array.from(arrayLike[,mapfn [,thisArg]]); 

Array-like object:
http://stackoverflow.com/questions/11886578/creating-array-like-objects-in-javascript

Iterable object:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_Generators

JavaScript String, Array, TypedArray, Map and Set are all built-in iterables.

Read JavaScript Map
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

Detail see the blog: 
http://juliachencoding.blogspot.ca/2016/06/javascript-arrayof-function-study.html

every        - iterator - go through each node in the array to check some logic?
fill         - fill - arr.fill(1), all the elements in the array are assigned to the same value
filter   
findIndex
foreach

indexof
join
keys
lastIndexOf
map

pop
push
reduce
reduceRight
reverse

shift
slice
some
sort
splice

toString
unshift
valueOf
values

challenges:
  Arguments:
  callback function -  
  callback function syntax

  3 things Julia likes the JavaScript Array.fill function design:
   - start, end arguments are options
   - negative start, end arguments handling

Questions:
1. Why JavaScript Array API is designed so differently? need to learn more about functional programming? 


Reference: 
Previous blog: 
Array 
http://juliachencoding.blogspot.ca/2016/06/array-class-c-c-javascript-java.html

Array-like object:
http://stackoverflow.com/questions/11886578/creating-array-like-objects-in-javascript

Iterable object:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_Generators

Wednesday, June 29, 2016

HackerRank: World codesprint #4 - Roads in HackerLand

June 29, 2016

Problem statement:


John lives in HackerLand, a country with  cities and  bidirectional roads. Each of the roads has a distinct length, and each length is a power of two (i.e.,  raised to some exponent). It's possible for John to reach any city from any other city.
Given a map of HackerLand, can you help John determine the sum of the minimum distances between each pair of cities? Print your answer in binary representation.

Max Score: 60
Difficulty: Moderate
Submissions: 1319

The problem is a graph problem, so here is her analysis:

Spent over 1 hour to try to figure out the graph problem, what is my best bet to solve the problem. 
Find simple problems to work on first:
Algorithm 1. Any two directed connected nodes, find shortest distance
distance (n1, n3)  = 10, go through node 1 -> node 2 -> node 3, instead of directly connected edge - 32

2. Any two nodes in the graph, find the shortest distance
based on graph in the step 3, find a route from one node to another node, using BFS or DFS, for example, node 1 to node 4, node 1 -> node 2 -> node 4. 
   min distance (node1, node4) 

Spend a lot of time here to try to design the algorithm: 
1. using DFS/recursive/memorization solution: 
    evaluate the solution, problems in the design cannot be solved: 
    problem and its subproblems are overlapping. 

   min distance (node2, node4)
   Not working 
2. using BFS/queue, the design concerns:
   1. Avoid loops
   2. Stop early - 

3. using DFS/stack, the design concerns:
  
Also, each edge's length is power of 2, different length. 
    
1. Step 1-> Step 2: 
Try to work on this graph, for each directed connected graph, use BFS algorithm, try to find a shorter route. For example, 
edge(1, 3) = 32, 
edge(1, 2) = 8, 
edge(2, 3) = 2, 
edge(1,3)  > edge(1, 2) + edge(2,3), since 32 > 8 + 2, 
So, the edge(1, 3) can be marked removable, this direct route will never be travelled. 

Work out the above case: 
start from node 1, add node 1 to the queue, and then, go through the queue, remove node from queue, add all neighbors to the queue, if it is not visited previously, and if it is the node 3, then only allow twice , as long as the sum is less than edge(1,3) = 32, continue; Make a single linked list, n2.prev = n1, n3.prev = n2, 

2. To work on graph in step 3,
For each node in the graph, for example, n1, using DFS or BFS to find a route to node j, j<>i.
So, with those removed edges, only one route will be found through any two nodes, i<>j.

To be continued.

Follow up 

April 26, 2017
Need to write down C# version to solve this minimum spanning tree algorithm.

---

Monday, June 27, 2016

A small research on HackerRank world sprint #4

June 27, 2016

 On Sunday June 26, Julia spent 3 hours to do some research, evaluate where she is in the competition, and what kind of target she can set, how to reach the target next time. Actually she went through current leadboard, and study who are best players, top-performance programmers.

Statistics:
Time spent on HackeRank world sprint #4: 4+ hours on June 25, 2016
Score: 40, around 2276 rank in over 5000 people.

Target: 
She needs to score another 50 - 100 in order to be competitive, where she found out that some Google, Facebook employee score' range (above 100, some above 140).

Top 16 - full score (420), there are a lot of world champions over there. So, the problems have some pattern, people can get trained to be good at them.

 Here is the link of HackerRank world sprint #4.

 https://www.hackerrank.com/contests/june-world-codesprint/challenges

 She completed first two easy algorithms in first 2+ hours. Get 40 points.

Gamble the luck is not a good strategy. Set low target is also not a good strategy. 4 hours can be spent on more meaningful learning experience. 

Why? 
Julia spent most of time to work on one problem, AorB, try to score another 50 points. She enjoyed coding and found one problem after another, but it is time-consuming, not efficient approach.

In first hour, she needs to write down every small function she should solve first, and then, design well-defined small function to be helpers, understand possible test cases. Simple problems are easy to work on, save time.

Some problems were discovered after she worked on the problem almost 4+ hours. Julia, you have to learn to be a good thinker first, force yourself think hard on first 30 minutes. Write down things to consider in design of function.

1. What is the problem she found out after 3+ hours?
The solution has problem, Hexadecimal should be reversed first, then, first char is least significant bit, much easy to iterate, compare among A, B, C. Mistakes like A, B, C to compare different bit, not align properly.

2. What is the problem she found out after 4+ hours?
how to make A as small possible? 
Provided with extra allowed bits, Give up 1 from A (1->0), by the order of most significant bit first, and then, set B's bit to 1 if need. 

3. What is the problem she found after 8+ hours? 
A|B = C, so C's length as string should be longest one. C's length = Math.Max(A.Length, B.Length). This helps the design and also testing. 


From 12:00pm - 12:00am, she spent a lot of hours to play with code, until midnight, she gave up AorB, scored 0 with many hours passion/ learning experience/ lesson learned.

Lesson learned: 
Passion does not work, good workout; but not practical. 
Break the problem into 5 - 6 well defined small functions;
First 30 minutes, be a good thinkers. Find all possible problems, assertions, read problem statement again and again. (make sense? :-))

Write a few small functions to warmup, fully test with test cases. 2 - 3 hours.
For example, work on this small well-defined function first,
http://juliachencoding.blogspot.ca/2016/06/hexadecimal-or-calculation.html
https://gist.github.com/jianminchen/5442cb579b13ffc203ce89b3e54e8a36

And then, spend 1 hour to put together for solution AorB.

The best performer in the world (172minutes/7 algorithms), average less than 30 minutes/ algorithm.

Good about the practice:
Practice code on problem solving: 
1. reverse a string in C# -> ToCharArray() -> IEnumerable first
2. check least significant bit using And 1 (bit manipulation)
3. check most significant bit using And 1 - define value array {8,4,2,1}
3B: leftshift >>1 in C# practice
4. Hexadecimal char <-> binary format string <-> integer value expression
5. int, long, bigInteger(?) cannot handle big number 10^5000, force me to work on string manipulation
6. Look into C# const keyword, how to separate variables - using existing variable, set new value, less code.
7. StringBuilder class needs System.Text package
8. break statement - be careful when the function is not well-defined small function, causing bugs.
9. A|B = C, what we can tell the length relationship among A, B, C.

Actionable items:

Choose 10 people's code to read.
Learn to be a good thinker - work on first 30 minutes, thinking, reading, define well-defined small functions.

Blog to read:
https://www.linkedin.com/pulse/why-best-designers-problem-solvers-katy-tsai?trk=hp-feed-article-title-like



Hexadecimal OR calculation

June 26, 2017

To work on HackerRank algorithm AoB, Julia found out that it took her more than 10 5+ hours to work on/ debugging/ bug fixing. She needs to work on design carefully, work on small functions first. 

Strategies talk: 
In order to save time and help herself think clearly/ simple, at the very beginning, she should define this small function, play with the code, and make it bug-free first. So, choose an easy battle first, something she can finish in 20 minutes and well-defined, easy to set up test cases and verify, and then, put together a complicate function to complete the task. If there is doubt or unsolvable issues, go back to the easy function, work on it more. 

Problem statement: 
Write a function to do A or B calculation, A and B is bigger than 0, and smaller than 16^(50000)
Analysis:
The size of number is too big, 64 bit integer is only < 2^64, so only work on one char at a time - one Hexadecimal char (0-F) a time. Only convert char and integer between Hexadecimal char(0-F) and integer (0-15). 

Test case:
Hexadecimal: 1000 | 11000 = 11000

 A | B
 For example:
 A = "111A"
 B = "1B"
so, A|B = "111B"
C# practice:  https://gist.github.com/jianminchen/5442cb579b13ffc203ce89b3e54e8a36

A comparison of Microsoft web technology - pluralsight

June 27, 2016

One hour lecture:

A comparison of Microsoft Web Technologies.

Start to work on short course first, work on foundation, and then, move to Angular JS, MVC later.

Course:
A Comparison of Microsoft Web Technologies


https://www.pluralsight.com/authors/michael-palermo

Sunday, June 26, 2016

Hexadecimal number bit manipulation practice

June 26, 2016

Need to work on problem solving, AorB, how to design a few simple APIs first?

Write a few function to check bit by bit from right to left, or left to right.

https://gist.github.com/jianminchen/103859e5e8287c9fd865c59363ad500b

A|B = C, to make A as small as possible, with maximum number of bits to update.

For example,
11001000     A
00000000     B
______________
11001000     C

If there are 2 more bits allowed to be update, then to make A smallest as possible, update A's leftmost bit to 0, and update C's leftmost bit to 1.

01001000   A'
10000000   B'
___________
11001000   C

Review blogs related to bit manipulations:
power of 2:
http://juliachencoding.blogspot.ca/2016/05/algorithm-check-if-number-is-power-of-2.html

Blogs to read:
1. Angular 2 minutes review:
http://henriquat.re/intro/angular/angularjsForDotNetDevelopers.html

2. So many courses on pluralsight, how to choose courses to learn day by day.
http://app.pluralsight.com/author/joe-eames

3. Reading material:
http://web.stanford.edu/class/cs9/
http://web.stanford.edu/class/cs9/lectures/07/Numbers.pdf

https://courses.csail.mit.edu/iap/interview/index.php

Leetcode solution to study

June 26, 2016

Spend some time to study Leetcode solution from the following blog:

http://maskray.me/blog/2014-06-29-leetcode-solutions
Leetcode 56: Merge Intervals
http://xiaoyaoworm.com/blog/2016/06/27/%E6%96%B0leetcode56-merge-intervals/

Leetcode 75: sort colors
http://fisherlei.blogspot.ca/2013/01/leetcode-sort-colors.html

Leetcode 130 surrounded region
http://www.cnblogs.com/higerzhang/p/4149040.html

Learn system design:
https://www.facebook.com/careers/life/preparing-for-your-software-engineering-interview-at-facebook

https://codelab.interviewbit.com/   (facebook codelab)
Plan to work on: 1 hour daily starting from July 1, 2016

http://www.hiredintech.com/system-design

A small research - hiring best:
https://www.toptal.com/freelance/in-search-of-the-elite-few-finding-and-hiring-the-best-developers-in-the-industry

AorB - HackerRank workout example

June 26, 2016

 A small problem related to AorB problem, and get some workout on bit manipulation. Still work on desigining a well-defined problem - something small enough, meaningful enough.

https://www.hackerrank.com/contests/june-world-codesprint/challenges/aorb


 The coding is time consuming, but it is good workout.

Try to put together a meaningful, small function:

           HexaDecimal Char update
           For example, A = 1000
           A | B = C,
           C = 0111
           Then, 4th bit 1 in A should be set to 1.
           number is 1, A' = 0000; assuming that B will provide first 3 bits of 1. 
         
           Another example, A = 1100,
           A | B = C,
           C = 0111,
           then, 4th bit 1 in A should be set to 0
           function return is 1, A' = 0100; assuming that B will take care first 3 bits of 1.
         
           1. count how many bits to update (only bit with value 1)
           2. return A's new value A'
           3. Work on bits from left to right, lowest significant bit first
           4. Assume the value > 0, and value < 10^ 50000
         
           Work on HexaDecimal string,
           For example, D8, work on '8' first, 4 bits 1000, from right to left;
           and then, work on 'D', 1101 - 13
         
           edge case:
           A= "8D",
           C = "E",
           C is short in length, one char only.

Practice 1: with a bug
https://gist.github.com/jianminchen/f4d8761ca6126052e3df792212861436

Question and Answer:
The design has issues, here is the detail:
function updateHexaDecimal_Remove1s (line 55 - 75) has same fatal error:

Review the design:  A|B = C
    D8    A
   A01    C

 For example, A string "D8", AorB string "A01", 
   then, D should compare to 0, and 8 should compare to 1

 So, the solution is to reverse the string. 

    8D   A's reverse
    10A  C's reverse

   But in the the code from line 61 -65, 'D' is compared to 'A'. The design cannot handle difference length correctly.

Practice 2: with bug fix
https://gist.github.com/jianminchen/c8501eabdb774710c100a1aa06049d8e

Read blogs:
From high school:
http://tarawa.github.io/

From Tsinghua University:
http://maskray.me/

https://threads-iiith.quora.com/

http://heliang.me/blog/?page_id=488

http://heliang.me/blog/?tag=%E9%9D%A2%E8%AF%95

https://threads-iiith.quora.com/

https://www.hackerrank.com/roba

https://www.linkedin.com/in/changhai-zhou-823ba265

https://github.com/maximizedchang/projecteuler/tree/master/Java%20Files

http://yufeizhao.com/olympiad.html






Reverse a string

June 26, 2016

Reverse a string in C#:

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

Read blog:
http://stackoverflow.com/questions/228038/best-way-to-reverse-a-string

C# implementation

https://gist.github.com/jianminchen/9ad0fff7c0e1d3f7294ef3dcc24b933d


Reverse, Array reverse, XOR, benchmark testing etc.

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

Convert a HexaDecimal char to an integer value

June 26, 2016

Get an integer value from HexaDecimal char - for example, 'F', return 15; '9' return 9
https://gist.github.com/jianminchen/2fbf865e2bdb49681bb8c7e9899d5908

Convert a binary number from 0 - 16 to a char (HexaDecimal binary string to a char)

June 26, 2016

Get a char from a binary number with 4 bits: 1111, return F; 1000, return 8
https://gist.github.com/jianminchen/fbea867f130b7d84e44085eab3671883

Remove leading 0 in HexaDecimal string

June 26, 2016 

1. Remove leading 0 in HexDecimal string, for example, "08" should be "8"
https://gist.github.com/jianminchen/fb14be371486b0fa3659cc2542a41bc1

HackerRank: AorB - intense workout - 3 hours+

June 26, 2016

HackerRank: AorB

problem statement


Quick summary of 3 practices


1st practice: failed all test cases except first one.
C# practice:  only pass 1 test case, failed all other cases, score 0/ 50


2nd practice: fix the bug - major issue, but failed most test cases still.
Fix the above issue - comparison issue, but still failed most of test cases.

3rd practice: pass all test cases.
Work on the test case, fix the bug. C# practice passes all test cases.

Long story short - 8 hours labor


So, starting from very beginning:

1st practice: failed all test cases except first one.
C# practice:  only pass 1 test case, failed all other cases, score 0/ 50


Spent over hours, go over again and again the problem statement, and then play with HackerRank unknown test case, try to figure out what is wrong.

So, work on problems one by one, it takes hours up to 8 hours. Great workout!

Small problems first


Here are a list of problems to work on, very good workout:

1. Remove leading 0 in HexDecimal string, for example, "08" should be "8". C# code.

2. Get a char from a binary number with 4 bits: 1111, return F; 1000, return 8.  C# code.

3. Get an integer value from HexDecimal char - for example, 'F', return 15; '9' return 9. C# code

4. Work out a small problem - AorB - try to define a function, get count of bits to change from 1 to 0,
in A, based on AorB value.
C# code.

5. (6/27/2016 added)
   Write a function to do A or B calculation, A and B is bigger than 0, and smaller than 16^(50000)
Test case:
Hexadecimal: 1000 | 11000 = 11000

C# code

June 27, 2016

Question and Answer:
1. How is the practice?
The design has issues, here is the detail:
function getChangeBits_From0To1, getFirstNumberFirst1To0_LetSecondOneTake1, getBitNumber_From1To0_strVersion all have same fatal error:

Review the design:  A|B = C
    D8    A
   A01    C

 For example, A string "D8", AorB string "A01", 
   then, D should compare to 0, and 8 should compare to 1

 So, the solution is to reverse the string. 

    8D   A's reverse
    10A  C's reverse

   But in the the code from line 397 - 399, 'D' is compared to 'A'. The design cannot handle difference lenght correctly.
That is the reason of failing most of test cases.


1. line 385 function getChangeBits_From0To1 has a bug:

inside the function,
   line 395: the Hexadecimal char is not matching between from and AorB sum.

   For example, A string "D8", AorB string "A01",
   then, D should compare to 0, and 8 should compare to 1

   But in the the code from line 397 - 399, 'D' is compared to 'A'. The design cannot handle difference length correctly.
That is the reason of failing most of test cases.

2. Same problem applies to funcation getFirstNumberFirst1To0_LetSecondOneTake1

3. And also, line 268 - line 282 can be shortened, remove if/else from line 279 - 291. Just update variable: afterAnd_From value

4. Same problem applies to function getBitNumber_From1To0_strVersion

2nd practice: fix the bug - major issue, but failed most test cases still.
Fix the above issue - comparison issue, but still failed most of test cases:
https://gist.github.com/jianminchen/15c0470a5bb86fb06bc30a4b83465313

Need to make this test case work, through test case provided by downloads:
input:
3
25
B631EB5AE
601C227E1
707AC8792
12
CAF7028FD
59B5AC1CE
CAF1B7B7F
3
81B9BB94E
8AB3CA95E
8BBBFB95E



output:

C8582
707A00790
8AF10287D
48B1B534E
B9BB94E
8BB3CA95E

3rd practice: pass all test cases.
Work on the test case, fix the bug. C# practice passes all test cases:
https://gist.github.com/jianminchen/cf823376a23a36304da82ca975f77fa1

Bug fix comparison - what to change:

2. How long is the practice and bug fix? What are major issues?
Time spent is much more than expected. 

Major issue is about the design of function, too long to handle without a bug. Need to think about breaking into small function. 
function getFirstNumberFirst1To0_LetSecondOneTake1 -
line 249 to 330, almost 100 lines. Need to redesign
the function, into multiple functions.



Warm up the algorithm, write another one in practice:

things to work on:

1. function name should be changed: (A|B = c AorB problem)

function name: 
getFirstNumberFirst1To0_LetSecondOneTake1 


new function name: 
getGreedy_A1To0_BStayUpdateTo1 -> get_A_SmallestPossible

greedy algorithm to make A as small as possible 

2. Use array to reduce the total of variables, and make the code less lines 

  3 variables:   A, B, C 3 string 

  line 260 - line 262, string from, to, fromB, 
  
  Declare a string array with length [3], 

0 - A
1 - B
2 - C

3. line 272 - line 274, 3 variables, 
   intFrom, intTo, intFrom_B, 

   use array to reduce variable to one

4. Line 279,   array variable - arr - move defintion out of for loop (line 270 - 330)

5. Declare an array to store chars, and add a new function called toChar(int)

   line 298, line 317, line 318 

   public static char tochar(int val, int powerof2){

       return (char)(value/powerof2 + '0'); 
   }

6. getCharFromBinaryNumber function name is too long, maybe, define a class BinaryNumber, and then add getChar api





HackerRank: Equal stacks

June 26, 2016

Problem statement:
https://www.hackerrank.com/contests/june-world-codesprint/challenges/equal-stacks

C# practice:
https://gist.github.com/jianminchen/28a6120097026961f9671710fd9a911d


HackerRank: world code sprint #4 - minimum distance

June 26, 2016

problem statement:
https://www.hackerrank.com/contests/june-world-codesprint/challenges/minimum-distances

C# practice:
https://gist.github.com/jianminchen/f2732794c68a5f2602d17e0052ebbd41

Wednesday, June 22, 2016

Leetcode 139: word break I - 3+ practices

June 22, 2016

Work on leetcode 139 - word break I

Problem statement:
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
Programming skills is like muscle, if you do not maintain it, it will go back to fat. When Julia tries to stretch DP muscle, she found out that she has nothing to stretch. She has to work on it, build up by hours, build up again. Leetcode 139: word break I (medium).
Julia read the code/ solution, but she could not figure out in detail, specially for those two loops - for DP algorithm. 
1 hour, play with 2 test cases. 
3 practices using C#; Set up a test case, run the code, and then, understand the algorithm.

Same code, different test cases
1st practice:
https://gist.github.com/jianminchen/f763ce5033ea4b152c7a56aaf98b7075

2nd practice:
https://gist.github.com/jianminchen/a1bafb4271b8bbdb18b92d0b3dad913e

3rd practice:
https://gist.github.com/jianminchen/bd9301c3ad38d801001d1d66a08256fe

Let us walk through a test case:
string test = "abcd",
and dictionary string array: {"a","bc","d"}

We know that, "a" can be constructed by word "a" in the dictionary.
"ab" cannot be constructed by the dictionary.

Now, what we can do to work on substring "abc", assuming that "a", "ab" are processed already.

How to approach the problem?
Use dynamic programming, reduce the work to minimum.

abc, so 'c' is the new comer, assuming that "a" and "ab" have been processed. By debugging the code, Julia put together the following comment:

so, step 1, "ab" cannot be constructed by the words in dictionary, so it does not matter if 'c'  is in dictionary. 
   Use array bool[] dp to store the cached value; 
  
   Cannot conclude that "abc" can be constructed by words in dictionary, need to go through all possible new words: {"c", "bc", "abc"}

    step 2, backward one more char, new word: "bc", 
 "a" is in cache - dp[1] = true, 
 "bc" is in the dictionary. 
 so,  "abc" can be constructed by words in dictionary. 
 Stop here, break the loop.     

    At most there are 3 words ending at 'c':
    "c",
    "bc",
    "abc",
    All other substrings are the substring of  "ab", assuming that DP is used, so no need to worry about.

4th C# practice:
https://gist.github.com/jianminchen/36de4c46292e79290af95098dfee3cb0

Question and Answer:
1. What is most time consuming part in coding?
Julia spent over 20 minutes to figure out what should be looped on - line 80, it is hard to figure out
meaningful ways to loop. She tried a few of ideas, then, she chose to loop on the position of right string.

   "abc",
   i = 2, then, 3 things are tried:
  1.  "ab", "c"
  2.  "a", "bc"
  3.  "",   "abc"

  two strings are in each case, right string's starting position in the original string "abc"
 line 80    for( int pos = i;  pos >= 0; pos--)
  i = 2, "c"
  i = 1, "bc"
  i = 0,  "abc"

4th C# practice:
 https://gist.github.com/jianminchen/36de4c46292e79290af95098dfee3cb0

Spend 10 minutes to write the program again.
5th C# practice:
https://gist.github.com/jianminchen/9766aea70c9015fabbea98fb71b56d6d

hightlight of changes:
1. line 41 - variable name is changed from "left" to "existingWord", existingWord is already processed, which can be looked up through cache array - true/ false.
2. line 42, newWord, each time the new char is processed, there are ith words ending at position i.
Need to check if it is in word dictionary.
Comparison between 4th practice and 5th practice:
comment:

code:
4th practice:
1. Do not know only work on substring 0-i, length i+1 substring, bottom up approach as DP - dynamic programming.
2. Confuse with string left, right, why left string needs to check cache, and then right string checks word dictionary.

Read blog to review dynamic programming:
https://en.wikipedia.org/wiki/Dynamic_programming

Review a few concepts:
Principle of Optimality
optimal substructure
larger problem - sub-problems
Bellman equation - optimization literature names relationship
optimal substructure and overlapping sub-problems
Divide and Conquer   vs dynamic programming
Top-down approach vs Bottom-up approach

Word break I uses bottom up solution -

6th practice:
https://gist.github.com/jianminchen/29758bad5d56d54e87c2a6f52d057835
comparison line by line:
    6th practice                                             5th practice

7th practice:
second loop on DP algorithm, new word loop starts from start position from 0 to i, in ascending order, line 43. 
https://gist.github.com/jianminchen/2e56665d934f9b9cbc2f94adc8e567bb

Statistics:
Time spent:
2 hour +


Train insane or remain the same - focus on training!