H tree

January 20, 2018

Introduction

It is the classical recursive algorithm. I had 4:00 pm mock interview and then I had to write H-tree algorithm. It took me exactly 30 minutes to finish the analysis and also coding. I made a mistake in the writing first, draw one H tree first, and then call recursive tree four times for each corners of H-tree.

Code review

Here is the code.

Compared to last practice

Here is my practice in Dec. 2017. The code is almost exactly same. Only difference is that this time I work on the analysis of the algorithm, write down given constraints, and problem to solve. Write down the solution first before I write the code.

I need to work on the structure of recursive function, base case, inductive step. Please write down those steps in analysis first.

  if depth == 0
  return

  // draw one H-tree
  draw horizontal line
  draw vertical left line
  draw vertical right line

 // inductive step
 4  recursive function call for each corner of H-tree
 left top
 right top
 right bottom
 left bottom

Because my first writing in mock interview today has wrong logic like the following:

 if depth == 0
  return

  if(depth == 1)
 {
  // draw one H-tree
  draw horizontal line
  draw vertical left line
  draw vertical right line

  return; 
 }

 // inductive step
 4  recursive function call for each corner of H-tree
 left top
 right top
 right bottom
 left bottom

I found the bug in whiteboard testing and then I fixed it. But I should understand base case 100% before I write the code.

Find all possible strings

January 13, 2018

Introduction

It is my favorite algorithm to write a combination of string "abc". There are eight possible combination, each char with lower case in original string can be lower case or upper case in combinations.

Code study

Here is my code.

A recursion tree

Let me draw a recursion tree to illustrate the problem. The peer and I had some discussion, and the peer told me that there is need for memorization, using dynamic programming. I was not so sure in mock interview, but now 12:18 AM, 1/13/2018, I am pretty sure that no need to do memoization

                           

Total combinations are "abc", "abC", "aBc", "aBC", "Abc", "AbC", "ABc", "ABC"

H-Tree recursive solution

Dec. 26, 2017

Introduction

I had a mock interview at 6 PM this evening and then I met a programmer who prepared a test case for my algorithm. I felt that the peer is the very good programmer and then I gave a lot of feedback on his coding review as well.

Here is my C# code to write a recursive function to implement H-tree.

One more recursive function

Nov. 28, 2017

Introduction

It is the fifth time I write the recursive function related to C# GetType() in mock interview. I wrote a blog about past practice. One of blogs is here.

This time I came cross two issues in mock interview on Nov. 28, 2017, one is to write String.IsEmptyOrNull, I did not know that the API is static function of String class. In other words, String.IsEmptyOrNull(string s) is the prototype of API.

The second one is to write value.GetType() == Dictionary, which should be value.GetType() == Dictionary<string, object>. It is time to learn more about C# strong typing.

Here is C# code.

Actionable Items

Plan to read C# source code of string class, and then write down study notes.
Look into C# strong typing related topic as well.

Can mock interview make difference? Continued

June 20, 2017

Introduction

"It takes a village to raise a child". Related to improve algorithm and data structure, Julia learned that it also takes the hundred people to help her learn depth first search using recursive function.

As a classical depth first search algorithm, Julia worked on the Sudoku algorithm in 2015, she collected over 10 solutions; She thought that she mastered the sudoku algorithm in 2015, actually not! How did Julia find out the fact?

Julia practised Sudoku solver in April and May of 2017. First experience is in April, the peer complained that Julia forgot to write a base case in her first writing and gave a rating of 3 with comment "Do not know how to write code", and then second one is in May, the peer coached Julia to set base case first thing in the design, do not write any small function, keep it short as possible, quick as possible. From those two hours to work with two different people, Julia learned to stay humble, learn and quickly fix her learning issues. With those two mock interview experience, Julia learned the Sudoku solver in totally surprising ways. Learn from people from recent graduate and senior developer, recent graduate explained what to work on through Google onsite experience, and the senior developer showed her later in second meeting with more tips.

June 18 and 19 weekend, Julia worked on the expert level algorithm called path matching, she scored 0.46 out of maximum score 100, she worked on over 5 hours but she learned depth first search again through the problem solving. Julia likes to solve the problem first, it does not matter if she scored less than 0.5%. She likes to get expert level algorithm problem solved first.

Julia starts to meet a person a day to work on algorithm problem solving, she also pays attention to peer's curiosity level on algorithm and problem solving, how good the peer can influence her through one hour conversation. Today she was surprised that the peer shared her link to solve C# problem from stackoverflow.com. Also the peer also typed the test case for her, and then Julia found out that her code had a bug, wrong output.

Julia learns how to do whiteboard testing and she did one today as well. But she missed the bug. So she felt that the peer is much better a tester and maybe she is a project manager working somewhere. It is the second time Julia worked on the algorithm.

A research talk 

The mocking experience is short, only one hour, the peer chose to turn off the video. But the quality of the work is very impressing, Julia found out that she is lacking of this kind of preparation for the mocking experience. 

Julia worked on extra 10 minutes to use Microsoft visual studio to find the bug. It is an excellent experience. 

C# code is here. 

In the line of 44, the new variable should be declared for each key value pair of dictionary. It is called nextPrefix. Do not change the function argument prefix, based on the least astonishment principle.

So share the advice Julia got today.

-very good communication, i liked how you explained your thought process thoroughly -got to the answer fast but still made sure to test before writing code

it's ok to ask the interviewer if you can look up inbuilt/library functions for the language if you need to, that might be helpful sometimes.

Recursive function design talk

May 7, 2017

Introduction

It is the 21th mocking experience this Sunday evening. Julia thought about writing about a blog about 21 mocking experience, what she has learned so far. And then she talked to herself it is better to do one thing at a time. Just talk about one mocking experience a time.

It is the middle of year, May. Julia likes to get started to work on some website project, study some pluralsight.com courses, and then practice some website technology.

Recursive function design talk 

Transcript is here. 

A few issues need to be addressed.
1. cheapestCost in the function name is not accurate, it should be minimalCost.
2. I should ask a lot of questions when designing the function, do I need to store all the paths? Do I need to keep track of each value on the path? Do I need only the value from the root node to the current node? Need to clarify the question.
3. The recursive function can be designed in different wasy, right now Julia chooses to use "ref minimalCost" in the function argument, but people may not have the idea to solve the algorithm.
What is the alternative way to write?

Actionable Items

Read something interesting:

Read one of article - link is here.

International Olympiad Informatics - wiki article is here. 

Recursive function code review

Feb. 25, 2017

Introduction
Julia reviewed 2 years ago in 2015, how she wrote a recursive function in less than 15 minutes, in the important meeting. She was never a manager before, image that she met 2 years ago herself, and read the code, how she thought about the learning style. So many issues in her writing, she found out by herself that there are 5 problems at least, but there are more. Here is ternary tree preorder traversal, middle, left and right in that order, and here is the blog she wrote.

Code review

It is important to take pluralsight.com courses about C#, and take down some notes, and learn one thing a time. 

Here is C# version Julia wrote on Feb. 25, 2017. 


Here is the C# code review on stackexchange.com.

code review - Hackerrank stone division

Feb 23, 2017

Introduction

Julia always chooses a topic to study, today her topic is about Google recruiting.

She came cross the article on Hackernews about Google interview, and she likes to put some number together to help her analyze the situation: (hypothetical skills)

Recruiter goes over millions resume, and start from 2000 people, try to fill 3 positions:

1: 2000 for 3 positions 

resume screen - 100,000 resume -> 2000 resume

phone screen   - 2000 people, each 30 minutes 

code screen     - ?

phone screen   - ?

in-person interview - 1 in 10 or 1 in 20 from that point

hire

and then read the comment from an ex-googler 1825 days ago, probably in 2011: 

With all that said, I haven't found any degree (at least from any school I've interviewed applicants for) to be a reliable signal for programming. Even if they went to a really good school, there's a good chance that they spent all their time learning network protocols and low-level mechanisms, and will happily write up a sliding-window implementation for me, but will stare at me blankly when I ask for a simple recursive algorithm. It's just tough to find people that spent time studying and practicing general-purpose computer science.

An googler's comment on onsite interview more than 5 years ago, Julia is the first time to get the idea:

"So what you are saying is that for me to not have made it through I must have equally messed all my interviews or at least a majority of them. I surely didn't feel like that after the interview, but who knows, since I still don't have a way to know if that is the case. Then this really sucks."

Just a comment from another Google engineer who does interviews (and didn't do yours, since I haven't done any for a couple months now): your own feeling at the end of an interview may not at all reflect your actual performance in the interview, because you have no visibility into what questions weren't asked.

I like to interview candidates by asking them to solve a simple programming problem and then modifying the specification little by little, having them adjust their solution to implement new functionality. There are about 8 steps in my question, and frequently I'm gauging the quality of the candidate by how long it takes him to get through the first N stages; we fix bugs in earlier stages before moving on to the next stage. To calibrate myself, I've tried this question on several of my coworkers, and they were universally able to get about halfway through the question with bug-free code in about 10 minutes. Only one required prompting on my part to fix a bug. Most every candidate I've interviewed has taken 20-30 minutes to get to the same halfway point; by that time I've only got 15-25 minutes left in my interview, and the candidate seems so far like a "no hire", so I move to a different question to find out if the candidate has other strengths to counterbalance his weakness at solving this (simple) coding problem.

From the candidate's perspective, he only sees me ask a series of programming questions which he answers satisfactorily with a little prompting from me. If he answers another question or two satisfactorily, he may think he's done well, but he doesn't know that I wanted to delve more deeply into every question I asked him, and just didn't have time because the pace of his solutions was too slow.

I wish I could give this feedback to the people I've interviewed, but sadly, I can't.

So, Julia searched her blog using keyword: recursive function, and then she read the first blog through the search results, and the blog is about the fact that she failed to deliver recursive function design, code in Nov 24, 2016, after so many years Ph.D. study and 7 years full time work in the city of Vancouver, and then she did some research to catch up. 

More detail, she worked on stone division more than a few hours in the contest - hackerrank woman codesprint, a medium level algorithm, maximum score 50, Julia overcooked the solution, had weak muscle on recursive thinking, and out-of-her-control, scored 0. The algorithm is called stone division.  

Here are five blogs about stone divisions, documented her experience in the hackerrank woman codesprint, series from 1 to 5, failed to score any thing from a medium level algorithm, maximum score 50, over a few hours (5 hours?) in the contest in Nov. 24, 2016, and then she took action to do some research on recursive function, and then she found code review on stackexchange.com. As a matter of fact, she got used to isolate herself so long, and in order to improve hackerrank contest performance, she seeks the change. From a lone coder, work ass off, she barely stays afloat (not in financially), so she decided to find her new schools one by one, the 3 months old new school is called codereview.stackexchange.com, she found the site just after the Nov. 2016 woman codesprint contest. 

So, she spent one hour to review the algorithm, wrote a more readable C# version this time, with 3 months experience with the code review school, with top-rated teachers from JavaScript, C#, algorithm help her to code review her code line by line, debate on basics - hash function, coding style, API design, and numerous rich experience. 

Code reivew

C# code for stone division is ready to be posted to stackexchange.com for a review. And code review link is here. 

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

May 11, 2016

Warm up an algorithm like tennis sports, work on different strokes before she plays matches. 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

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

     https://gist.github.com/jianminchen/589f05f5c87bb6e018de0a472d8a3b6f

Question and Answer:

1. What do you like the approach - DFS, recursive function, use an argument - reference to track the count? 

Julia likes to use an argument to track the count, and let the recursive function return void. 

A binary tree is substree of another binary tree

April 21, 2016

Introduction

It is the great experience to review the recursive function through the algorithm called "Is subtree". Depth first search algorithm is very basic one using recursive function call, it is the fast and quick way to write an algorithm and also very popular in the interviews.

Problem statement:
http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/

Time Complexity: Time worst case complexity of above solution is O(mn) where m and n are number of nodes in given two trees.

Another solution:
http://www.geeksforgeeks.org/check-binary-tree-subtree-another-binary-tree-set-2/

O(n) time, special case handling - for leaf node of tree - append null 

Question and answers:

1. What do you learn through this study? How long does it take you to figure out things? 

Answer: First, it is about the subtree definition: it should be uniquely defined; for any node in the tree, the subtree starting from the node is only one. In other words, the node is the start, and all leaf nodes underneath should all be included.

2. The very good way to think recursively; do not repeat the work, do not do the extra work; only work on root node, since every node can be root node; get in the loop or recursive function. 

3. Let us walk through the code and add some comment: The code link is here. 

Dec. 25, 2016

Read the code review on stackexchange.com.

Algorithm called "is subtree"

http://codereview.stackexchange.com/questions/6774/check-if-a-binary-tree-is-a-subtree-of-another-tree
http://codereview.stackexchange.com/questions/117325/find-if-a-given-tree-is-subtree-of-another-huge-tree

Follow up 

June 17, 2017

Find out leetcode algorithm related algorithm. 

Blog to read:
Need to review KMP algorithm - strstr - O(N) algorithm:

http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/

Algorithm: Merge two sorted singly linked list

February 2, 2016

Always work on simple problem. Enjoy the practice. Recursive function design is most important one. 


recursive solution:
http://stackoverflow.com/questions/10707352/interview-merging-two-sorted-singly-linked-list

Itearative solution:
http://stackoverflow.com/questions/10707352/interview-merging-two-sorted-singly-linked-list

http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/

Julia's practice:
Recursive solution:
https://github.com/jianminchen/AlgorithmsPractice/blob/master/MergeTwoSortedSinglyLinkedList.cs

Leetcode 17: Letter Combinations of a phone number (DFS)

January 24, 2016
 
17 Letter Combinations of a phone number (DFS)

Julia likes to focus on basic things about algorithms, she tries to focus on recursive function design, BFS, DFS, backtracking. Here is her favorite DFS algorithm, she tries to build more fun memory about DFS algorithm, every time she works on DFS algorithm, she is so happy and eager to share her 2 cents, learned from Leetcode blogs - all her favorite blogs.

http://www.cnblogs.com/grandyang/p/4452220.html
Analysis from the above blog:
这道题让我们求电话号码的字母组合，即数字2到9中每个数字可以代表若干个字母，然后给一串数字，求出所有可能的组合，相类似的题目有 Path Sum II 二叉树路径之和之二，Subsets II 子集合之二，Permutations 全排列，Permutations II 全排列之二，Combinations 组合项， Combination Sum 组合之和和 Combination Sum II 组合之和之二等等。我们用递归Recursion来解，我们需要建立一个字典，用来保存每个数字所代表的字符串，然后我们还需要一个变量level，记录当前生成的字符串的字符个数，实现套路和上述那些题十分类似，

Her practice is too weak in 2015.
https://github.com/jianminchen/Leetcode_C-/blob/master/LetterCombinationOfAPhoneNumber.cs

Missing in the last practice:
1. Use iterative solution, but lack of analysis - (comment area, hard to review)
2. Should focus on DFS solution, basic things.

New practice in January 2016:
1. using recursive to solve the problem, it is fast and quick way to solve it in 10 minutes.
2. Only need to write a few lines of code.
3. Need to design recursive function.
4. Need to do backtracking,
5, Need to do char, string, int a few types, and also do type conversion.

Julia's practice, it took her 27 minutes to write down, compile, and have some comment written.
https://github.com/jianminchen/Leetcode_C-/blob/master/17LetterCombinationOfAPhoneNUmber_DFS.cs

January 24, Read more blogs on this question:

和subset, combination问题一样的backtracking。唯一的区别是要先建立一个从数字到字母的转换表。这样每一层递归遍历当前digits[i]所对应的所有字母，并加入当前combination中传到下一层递归。
Iterative solution: 这里需要克隆多份之前的解集。
http://bangbingsyb.blogspot.ca/2014/11/leetcode-letter-combinations-of-phone.html

Java, using hashmap - Good idea
http://blog.welkinlan.com/2015/10/25/letter-combinations-of-a-phone-number-leetcode-java/

终于出现我最不擅长的递归题了，这道题是经典递归题，标准DFS解法，应作为模板牢牢记住。
http://simpleandstupid.com/2014/10/16/letter-combinations-of-a-phone-number-leetcode-%E8%A7%A3%E9%A2%98%E7%AC%94%E8%AE%B0/

So, Julia is not good at recursive function design as well. So, she likes to search a blog and find the most important tip she can grasp in next 20 minutes.

Array initiliazation can be in one line instead of more than 8 lines
http://yucoding.blogspot.ca/2013/01/leetcode-question-42-letter.html

DFS, backtracking is clear in the code.
http://rleetcode.blogspot.ca/2014/02/letter-combinations-of-phone-number-java.html

Java code, member of class - hashmap - static - first time read static - declare variables sharing static in statement. (missing backtracking? or does not matter)
https://github.com/rffffffff007/leetcode/blob/master/Letter%20Combinations%20of%20a%20Phone%20Number.java

very well written,
http://codesniper.blogspot.ca/2015/01/17-letter-combinations-of-phone-number.html

using vector instead of hashmap
http://yumei165.blogspot.ca/2013/04/letter-combinations-of-phone-number-c.html

Good analysis - read the analysis in the following blog -

• 这个是一个结果是排列组合的问题,一个类似的问题就是小组赛N个队, 相互之间的比赛 列表. 这种问题就是回溯法
• 回溯法最重要的就是要"先加再减" (Julia's comment -> backtracking ) 
• 回溯法函数参数的设计是把结果当成参数(此处是用参数引用), 返回值返回一个void. 这样容易设计递归.
• java的做法会比c++看起来麻烦一点, 而且java是无法做到真的const String数组

http://harrifeng.github.io/algo/leetcode/letter-combinations-of-a-phone-number.html

九章算法
http://www.jiuzhang.com//solutions/letter-combinations-of-a-phone-number/

Analysis from the following blog:
Understand the problem:
The problem gives a digit string, return all possible letter combination that the number could represent. Note the the relative order of the number should be reflated in the corresponding strings. For instance, "23", 2 is ahead of 3, so abc should be in front of def as well. For a brute force solution, we can iterate all possible combinations, with the time complexity of O(n^m), where n is the number of characters for each digit, m is the length of the digit string. 

Recursive Solution:
It is a typical recursive problem, you can mimic the solution of Subset. 
http://buttercola.blogspot.ca/2014/09/leetcode-letter-combinations-of-phone.html

use this one as my example to write a good solution. Good style!
https://segmentfault.com/a/1190000003766442

Excellent code style.
http://shanjiaxin.blogspot.ca/2014/02/letter-combinations-of-phone-number.html

So, put together something for DFS /backtracking algorithm - favorite tips:
1. DFS, do not forget backtracking, using Chinese words, "先加再减". 
2. Recursive function design:
    Return result C#: IList<string>, 
    put it as input argument or member variable of class Solution 
3. Remember a tip to convert a char to int, very basic convert using this: 
    Char c (no one can remember the ascii value of '0', but use type conversion c-'0', char to int; in other words, compare to relative char, get the value by type conversion automatically).
    c - '0' 

4. dictionary declaration, common and easy way is to declare one dimension array:

    String[] table = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

5. using C# or Java, string class is not good, using StringBuilder class instead. 

6. Remember one or two DFS algorithms, use them to relax and help to figure out design issue, difficulty level of DFS problem solving - honestly, it is easy and quick solution, less time-consuming compared to an iterative solution, more time-consuming DP with memorization solution.