Flood fill algorithm small talk

April 19, 2017

Introduction

Flood fill algorithm is a term Julia learned through wiki article reading in 2017. Julia learned the algorithm through various situations and found out that it is very important to follow the structure to practice. The structure she follows starting less than 1 month is to start from one small example, work through the example. If Julia has 30 minutes to work on the algorithm, she will spend first 10 minutes to work on a small example, go over the problem and think out loud with ideas to solve the problem, write pseudo code, and walk through some test cases. To show the intelligence, Julia will write down something to help herself track the progress. And next 10 minutes to write the code, and 10 minutes for potential issues.

As showed in the following transcript, Julia went through the sample test case, and then counted one by one island and marked them using A, B, C, D, E, F. And then she went over the detail in 10 minutes to write and communicate ideas through her writing. She likes to write and reminds her to go through everything in her preparation to a perfect bug-free coding stage.

Good conversation is like this, Julia said that there is 5 of islands, the peer said that it is six. So Julia just marked one by one using A to E, and then she found F at last moment. It is called cognitive ability, both of players know each other through counting activities. Good warmup. Julia did very well on this, showed that she could collaborate very well, adapt to uncertainty and learn.

Flood fill algorithm 

Here is the 30 minutes transcript in mocking experience.


Julia tried to make the code more clear as possible, and she should push the code to the visit function.

Code review after the practice, fix grammar errors, code is here.

Make the code less verbose, and short. Here is the code to add extract a visit function.

Here is the progress report, the 30 minutes transcript has been worked on to fix grammar errors first, the compiled C# code is optimized to add extract visit function next.

Actionable Item

Read the article one more time, Google hire, write down notes here:


General cognitive ability - the capacity to learn, the combination of raw intelligence

Argument 2:
A diligent interviewer will probe deeply to assess the veracity and thought process - how to do it?

Argument 3:
People who score high on conscientiousness “work to completion”—meaning they don’t stop until a job is done rather than quitting at good enough—and are more likely to feel responsibility for their teams and the environment around them.

Code review: KinghtL on a chessboard

March 3, 2017

Problem statement

Need to study how to put math symbol into the problem statement:

Study the webpage - what HTML tags are allowed.

Won a fanatic badge - visit the codereview.stackexchange.com in last 100 days. Official statement:
Visit the site each day for 100 consecutive days. (Days are counted in UTC.).

Code review is here. 

March 8, 2017

Julia got excellent review with 5 advices in March 7, 2017, she will put together the C# code and post here as well. 


C# code updated version based on the recode review is here.

JS1 showed me how to do flood-fill algorithm. Also read this tutorial.

Leetcode 317: Shortest distance from all buildings (Part 4)

Feb. 16, 2017

Introduction

Julia was trying to find a good one to ask code review on stackexchange.com, and the she noticed that her blog is coming to a landmark 100,000 views. So, she likes to celebrate her hard work, she saw one of visitor was from search result using keyword: Leetcode 317 in last 7 days. So, the user of the blog solved her problem - find a nice algorithm to review. She worked on the algorithm before, she did twice. 

Her first practice is more than 12 months, she reviewed the blog in January 2016. In May 11, 2016, she practised again the algorithm. Her practice code is here. Through her practice, she likes to track her progress. She likes to say just so so, coding is like tennis sport, she has to learn from best - Roger Federer.

Workout

Julia likes to rewrite the C# code based on last practice in January, 2016. And here are the highlights of change.

To challenge herself, she designed several classes to track intermediate result, for example, empty land and building distance, building key and empty land position should also be recorded, so she can test the API first.

Because there is no concern about timeout or space limitation, Julia likes to design a few APIs, and also learn how to write code to follow S.O.L.I.D. principles.

In C# code, function WalkFromBuildingBFS is set as public API, and also a test case is added. Make sure that BFS search algorithm is working fine.

Here is the C# practice ready for review. Here is the code review link. 

Read some posts about SOLID principles on stackoverflow.com first.

Feb. 17, 2017 10:15pm 
Read the post about SOLID principles, the link is here.

Feb. 18, 2017 11:05am 
1. Update the question of Leetcode 317 to make it more instructional - the breadth first search, including some research I did on community challenge. 

2. Study the community challenge question code review, Rainfall challenge.
     Study Java code implementation first, and then write a C# one to ask for review.


Feb. 20, 2017
Read leetcode solution discussion, one of discussion is to expedite the search, great idea I read first time:
I also tested the other three C++ solutions posted so far, they took 340-1812 ms. I think mine is faster because I don't use a fresh "visited" for each BFS. Instead, I walk only onto the cells that were reachable from all previous buildings. From the first building I only walk onto cells where grid is 0, and make them -1. From the second building I only walk onto cells where grid is -1, and I make them -2. And so on.

Code Review - Find biggest basin

Dec. 31, 2016

Find biggest basin

Julia's favorite review: 

http://codereview.stackexchange.com/a/49477/123986

Julia, write a C# practice as well.

BFS/ DFS algorithms' Review

Julia, please review BFS/ DFS algorithms practiced this year.

Search blog using keyword: BFS

1. Connected Cell in a Grid - Warm up with Five Practices

Use Queue/ Stack/ Recursive function, get familiar with all five algorithms.

2. Leetcode 317: Shortest distance from all buildings

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

May 30, 2016

Study the blog:
http://juliachencoding.blogspot.ca/2016/05/leetcode-126-word-ladder-ii-study-c.html

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.
https://gist.github.com/jianminchen/9e45848c86ebaaa8f0bc0d881cfd1ad5

2. Fix the bug and pass the test case, add line 112:
https://gist.github.com/jianminchen/e3466a9f1319f62f869aa53487c05536

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. http://www.cnblogs.com/shawnhue/archive/2013/06/05/leetcode_126.html

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

May 30, 2016

Study the code:
http://mrsuyi.com/2016/01/31/leetcode-126/

C# code:

https://gist.github.com/jianminchen/3e99a564341995e2dd93e2fd3580aaef

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 17: Phone Number - Practice using DFS/ Stack and BFS/ Queue

May 12, 2016

 Write two more practice using Queue/ BFS and DFS/ stack on this leetcode question:

Using Queue/ BFS
https://gist.github.com/jianminchen/5691a3488a2ef4f0660194502ae15f68

Using Stack/ DFS
https://gist.github.com/jianminchen/872bf70039fa8c61ff208b34a591c8ec

Previous blogs about practice:

April 21, 2016 using recursive function, DFS
http://juliachencoding.blogspot.ca/2016/04/window-sum.html

January 24, 2016 using recursive function, DFS
http://juliachencoding.blogspot.ca/2016/01/leetcode-17-letter-combinations-of.html


Question and Answer:

1. What is the difference using Queue and Stack on space usage?

For example, using Queue/ BFS, source code line:

Line 31: IList<string> list = letterCombination("234"); // test result: "abc", "def", so 3x3 = 9 cases. If the string is "2345678", 7 digits string, then, when first string is added to the list, on line 86, the queue's count is around 3^7 = 9 * 9 * 9 * 3, more than 2000 records in the queue. However, using Stack/ DFS, source code line 31, the string is "2345678", when the first phone number is added to the list, the stack size is around 3*7 = 20, around 20 records in the stack. So, it takes more space to use queue/ BFS on this problem solving, not efficient on space usage.

2. Please look into string, stringBuilder on this problem solving.
Read more blogs on this discussion:

Leetcode 317 - shortest distance from all building - a warm up practice (Part 3)

May 11, 2016

Julia spent time to rewrite the algorithm on Leetcode 317.

Here is her last practice on January, 2016. The blog is top 3 most visited blog - 138 visit up to May 11, 2016. So, she is encouraged to rewrite the code.

Her practice after 4 months is here.

She likes to do more writing on this algorithm, try to figure out ways to improve the performance.

HackerRank – Connected Cell in a Grid - Warm up with Five Practices (II)

May 11, 2016

Being a software programmer, it is easy to spend hours to read and catch up technologies, work on new algorithm, but no coding, one day, or one week, even half month/ month. 

So, warm up like sports. Julia chose the algorithm - Connected Cell In a Grid to warm up for a few hours. 

Last time, less than 1 month ago, Julia did work on this algorithm – connected cell in a grid. And then, she started to warm up again.

Here is one of blogs last practice on April 16, 2016:

http://juliachencoding.blogspot.ca/2016/04/hackerrank-connected-cell-in-grid.html

Warmup coding: 

Her practice, using queue, but use jagged array:  (20 minutes to write), using queue, jagged array, 

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

Question and answer: 

1. How is the warmup experience? 

Because this is the second one, after 1 hour writing, debugging the code in first practice using dimensional array/ queue, this one is much easy. Just replace the dimension array using jagged array. 

HackerRank – Connected Cell in a Grid - Warm up with Five Practices

May 11, 2016

Being a software programmer, it is easy to spend hours to read and catch up technologies, work on new algorithm, but no coding, one day, or one week, even half month/ month. 

So, warm up like sports. Julia chose the algorithm - Connected Cell In a Grid to warm up for a few hours. 

Last time, less than 1 month ago, Julia did work on this algorithm – connected cell in a grid. And then, she started to warm up again.

Here is one of blogs last practice on April 16, 2016.

First practice, it takes her close to 60 minutes to write, fix issues.  Use dimensional array, use queue to do BFS – breadth first search.

C# code 

Here are mistakes:

      1. Forget to add boundary check function, do boundary check (source code: line 108)

      2. Forget to introduce neighbor_X, neighbor_Y  (source code: line 90, 91)

      3. Neighbor_X is mistakenly written as neighbor_Y, so wrong answer;

          Debug the code and find the issue. It takes more than 20 minutes, a lot of stress. (source code: line 96)

So, it is excellent chance to learn and improve the performance.

Write a small function to debug the code, figure out the wrong answer issue – testRoutine, source code: line 36.

C# code with an extra debug function

Second practice, using queue, but use jagged array:  (20 minutes to write)

C# code using jagged array

          

Third practice, use DFS – recursive function, which also returns the count.

C# code using DFS, recursive function

         

Fourth practice, using DFS – recursive function, but use an argument – reference int to track value

C# code using reference integer in function argument     

Fifth practice, using stack instead of recursive function, implement the DFS algorithm:

C# code using stack

Question and answer:

      1. What do you learn through the warm up? Do you learn some better ways to fix the bugs?

It is better to write down the functions needed to help the task, this way, you will be more efficient.

Here are 4 tasks:

     1. Calculate the key

     2. Boundary check 

     3. Maximum value search

     4. Using queue to do search

     2.  Why do you do warm up this time? What are the advantages?

Julia still remembers the favorite tip to work on the tasks:

1.    Just mark the visited node as 0 from value 1

2.    Update node value from 1 to 0 before it is added to the queue

3.    Use key = row * 10 + col, since row < 10, col < 10 to track each node in the queue

Julia likes to write code and do some warm up, therefore, she can get more experience; she tries to improve performance to 20 minutes for this kind of DFS, BFS, matrix, search algorithm.

3. Do you reproduce the experience of high stress to trouble shooting and work on bug fix? 

Julia reproduced the issue of high stress, she could not fix the bug on her first practice. So, she wrote a small debug function try to figure out; actually, it is a mistake in writing. 

Next time, reexamine every line of code, every variable, every executable path, when the code is executed. Do not depend on debugging, running the code, because stress level is high. 

Algorithm: reading blog

February 2, 2016

 Think about learning Python today, since Julia likes to read Python code and get some great ideas in the code. She starts to read the blogs from Leetcode question 331 to 1 in descending order.

  As a programmer, she spent over 6 months to learn Javascript in 2014, and then she loves to read Javascript code now. So, spend 10 - 20 minutes a day to learn Python, one day she will love to read Python code.

  Here is the blog she starts to read.

  http://bookshadow.com/leetcode/

  https://www.hrwhisper.me/leetcode-algorithm-solution/

  http://www.cnblogs.com/grandyang/p/4606334.html

  http://www.cnblogs.com/EdwardLiu/tag/Leetcode/

  http://www.jiuzhang.com/problem/

 Here is the log of her reading:

 Feb. 3, 2016
Leetcode: 331, 330, 329, 328, 327, 326

331. Verify Preorder serialization of a Binary Tree
idea: Use stack

330. Patching Array
Read the blog, understand the idea:
https://leetcode.com/discuss/82822/solution-explanation

329. Longest Increasing Path in a matrix
idea: go through each node in the matrix, BFS search, and get minimum one;

328. Odd Even Linked List (Easy)
Julia's comment: think about O(N) space solution first (using array, and then, easy to go through), and then, work on O(1) space solution, the following blog helps:
http://www.cnblogs.com/EdwardLiu/p/5138199.html

Feb. 4, 2016
327 Count of Range Sum
Still confused about the question, the example is also hard to understand.

324. Wiggle Sort II
Julia figured out the easy way to do it, O(n) time, O(1) space. So motivated. Next time, think about algorithm by yourself, start from brute force, and then, work towards requirement - efficient solution.

https://segmentfault.com/a/1190000003783283
public class Solution { public void wiggleSort(int[] nums) { for(int i = 1; i < nums.length; i++){ // 需要交换的情况：奇数时nums[i] < nums[i - 1]或偶数时nums[i] > nums[i - 1] if((i % 2 == 1 && nums[i] < nums[i-1]) || (i % 2 == 0 && nums[i] > nums[i-1])){ int tmp = nums[i-1]; nums[i-1] = nums[i]; nums[i] = tmp; } } } }

322 Coin change
http://www.cnblogs.com/grandyang/p/5138186.html

这道题只让我们求出最小的那种，对于求极值问题，我们还是主要考虑动态规划Dynamic Programming来做，我们维护一个一维动态数组dp，其中dp[i]表示钱数为i时的最小硬币数的找零，递推式为：

dp[i] = min(dp[i], dp[i - coins[j]] + 1);

其中coins[j]为第j个硬币，而i - coins[j]为钱数i减去其中一个硬币的值，剩余的钱数在dp数组中找到值，然后加1和当前dp数组中的值做比较，取较小的那个更新dp数组

321. Find Maximum number 

https://www.hrwhisper.me/leetcode-create-maximum-number/

319 Bulb Switch 
http://www.cnblogs.com/grandyang/p/5100098.html

Analysis from the above blog:

那么我们来看这道题吧，还是先枚举个小例子来分析下，比如只有5个灯泡的情况，'X'表示亮，‘√’表示灭，如下所示：

初始状态：    X    X    X    X    X

第一次：      √    √    √    √    √

第二次：      √     X    √    X    √

第三次：      √     X    X    X    √

第四次：      √     X    X    √    √

第五次：      √     X    X    √    X

那么最后我们发现五次遍历后，只有1号和4号锁是亮的，而且很巧的是它们都是平方数，是巧合吗，还是其中有什么玄机。我们仔细想想，对于第n个灯泡，只有当次数是n的因子的之后，才能改变灯泡的状态，即n能被当前次数整除，比如当n为36时，它的因数有(1,36), (2,18), (3,12), (4,9), (6,6), 可以看到前四个括号里成对出现的因数各不相同，括号中前面的数改变了灯泡状态，后面的数又变回去了，等于锁的状态没有发生变化，只有最后那个(6,6)，在次数6的时候改变了一次状态，没有对应其它的状态能将其变回去了，所以锁就一直是打开状态的。所以所有平方数都有这么一个相等的因数对，即所有平方数的灯泡都将会是打开的状态。

那么问题就简化为了求1到n之间完全平方数的个数，我们可以用force brute来比较从1开始的完全平方数和n的大小

February 7, 2-16
Please understand the question, if the problem is too complex, then the understanding may not be not correct. 

Leetcode 318: Maximum Product of Word Length 
Given a string array words, find the maximum value of length(word[i]) * length(word[j])where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/

Solution 1:

直接看看每个字符串都包括了哪个字符，然后一一枚举是否有交集：

• 有交集，则乘积为0
• 无交集，乘积为 words[i].length() * words[j].length()

Solution 2:

其实因为全部都是小写的字母，用int 就可以存储每一位的信息。这就是位运算

• elements[i] |= 1 << (words[i][j] – ‘a’);   //把words[i][j] 在26字母中的出现的次序变为1
•  elements[i] & elements[j]    // 判断是否有交集只需要两个数 按位 与 （AND）运算即可

read the blog to understand bit operation, take some time to refresh the memory:
http://www.cnblogs.com/onlyac/p/5155881.html

在一个字符串组成的数组words中，找出max{Length(words[i]) * Length(words[j]) },其中words[i]和words[j]中没有相同的字母，在这里字符串由小写字母a-z组成的。

对于这道题目我们统计下words[i]的小写字母a-z是否存在，然后枚举words[i]和words[j]，找出max{Length(words[i]) * Length(words[j]) }。

小写字母a-z是26位，一般统计是否存在我们要申请一个bool flg[26]这样的数组，但是我们在这里用int代替，int是32位可以替代flg数组，用 与（&），或（1），以及向左移位（<<）就能完成。如“abcd” 的int值为 0000 0000 0000 0000 0000 0000 0000 1111，“wxyz” 的int值为 1111 0000 0000 0000 0000 0000 0000 0000，这样两个进行与（&）得到0， 如果有相同的字母则不是0。