Friday, June 30, 2017

Effective C# 50 Specific Ways to Improve Your C#

June 30, 2017

Plan to read a book:

Effective C# 50 Specific Ways to Improve Your C#


Leetcode 76: Minimum Window Substring

June 30, 2017

Introduction



Leetcode 76 minimum windows substring is such a popular algorithm, Julia was asked to work on the algorithm in mocking experience, the peer likes Julia to work on the string algorithm, and the peer gave the advice that Julia's solution will have time out issue.

Algorithm study 



Mocking 8:00 pm - 8:30 pm

Here is the C# practice in mocking experience, the code has timeout issue. Time complexity should be cut down.

Here is the C# practice to pass online judge of Leetcode 76.

Leetcode Discussion


Read one of discussions - link is here.

Need to write a short and better solution.

The current window is s[i:j] and the result window is s[I:J]. In need[c] I store how many times I need character c (can be negative) and missing tells how many characters are still missing. In the loop, first add the new character to the window. Then, if nothing is missing, remove as much as possible from the window start and then update the result.

Julia is very good at writing the code, she just need a good idea to work on.

C# code is rewritten, link is here.

What can I say after I debug the code using a test case? This code is hard to understand, one dictionary serves multiple purposes. It reminds me the algebra.

For example, "xxyz", search string is "xyz".
We can keep the search string in the dictionary<char, int>
dict['x'] = 1,
dict['y'] = 1,
dict['z'] = 1

Now, we like to use those values to track how many in the sliding window. If the sliding window is "xx", then dict['x'] = -1. If the value is 0, then the number of char is exactly what need. -1 means that there is extra one.

We also keep count of how many chars we need in search string. First visit of x in sliding window "xx" we increment count variable once, but second one we do not do that. In other words, there is only one 'x' in search string. From any iteration, it is easy to tell if the sliding window contains the search string by comparing count variable with the length of search string.

Queue is not necessary, just track the left position of sliding window. One advantage to use queue is to filter out characters not in the search string.

Move Queue from the code, and come back to work on the algorithm later.

Most important is to check time complexity of this idea, it is better than O(s.Length * t.Length), actually it is O(s.Length).

C# SortedSet talk

June 30, 2017

It is a great idea to learn C# programming language using Leetcode. Julia searches Google using keyword "C# SortedSet Leetcode", and then she finds the following algorithms to work on:

Leetcode  23  Merge K Sorted Lists
Leetcode  57  Insert Intervals
Leetcode 128 Longest Consecutive Sequence
Leetcode 220 Remove Duplicate III
Leetcode 239 Sliding Window Maximum
Leetcode 295 Median of Streams


It takes a few hours to study those algorithm written using C# SortedSet.

Leetcode 295: Median of Stream

June 30, 2017

Work on the C# code using SortedSet. Here is C# practice.

Review book: Effective C# 50 Specific Ways to Improve your C#, Item 31: Implement ordering relations with ICompare<T> and IComparer<T>


Leetcode 23: Merge K Sorted Lists

June 30, 2017

Julia tried to learn more about C# SortedSet, so she googled "C# SortedSet Leetcode" first, and worked on a few algorithms implemented using SortedSet.

C# practice is here.


Leetcode 220: Remove Duplicate III

June 30, 2017

C# practice is here.

Leetcode 239: Sliding Window Maximum

June 30, 2017


Julia is learning C# SortedSet, so she chose the algorithm to practice SortedSet. C# practice is here.

Leetcode 57: Insert intervals

June 30, 2017


Julia likes to learn to use C# SortedSet, and then the algorithm can be implemented using the class. C# code is here.

Leetcode 128: Longest Consecutive Sequence

June 30, 2017

It is a great idea to learn C# SortedSet by looking up Leetcode algorithms, search Google using keyword: "C# SortedSet Leetcode". Here is the C# practice code.


Wednesday, June 28, 2017

Common mistakes talk

June 28, 2017

Introduction


It is a good idea to celebrate 80 times mocking experience with a coding blog. What is the good topic? Julia learned a lot, and she likes to write common mistakes in the mocking experience.

Julia did some research on the topic "Do mocking make difference?". Julia likes to set a new goal for her practice, improve her communication.

One interesting topic Julia likes to bring up is 3000 algorithm practice, Julia likes to build up skills by playing hackerrank contest, Leetcode practice and mocking experience. And also Julia learns to journal her emotions through the practice in order to build mental toughness.

Julia started to cut short those long hours for Hackerrank contest, she likes to write a few blogs when she prepares to solve a medium or expert level algorithm, she also likes to read some good lecture notes and do some research on the topic, certainly Julia learns to succeed on week code of 33 and enjoyed her first gold medal.


Common mistakes 


Julia was complained once that she made the mocking experience like an exam, it should be a conversation. And another time Julia was told that if she was given a hint, she should take it, do not be a hacker. Julia learns to respect the peer and follow the direction right away. So she was surprised that today mocking experience, she tried to give same advice, but the peer did not take it. 

Here are 10 more mistakes Julia learns from her last 80 mocking experience:

1. One of the peers asked very politely in the first minute, how does the mocking work? Are you a professional?  Question is how to show up very professionally? Age difference?
2. Prepare peer's algorithm very well as an interviewer. For example, quickly look up Google and get  an API stackoverflow link for the peer.
3. Miss base cases in the algorithm analysis
4. Do not talk and explain the base case in DFS design in the first place. Need to learn more about DFS algorithm design, know different kinds of solutions, and then communicate efficiently.
5. Easy to get stuck or be distracted from the algorithm.
6. Fail to come out dynamic solution or recurrence formula quickly. Julia did notice the issue in her first round.
7. Some of peers expect the code ready to run with test cases and you should show the correct result.
Work hard until you can write the algorithm and make sure that the algorithm can run. Practice more.
The third time Julia wrote the same algorithm and then she was asked to run the code, she had a few bugs to fix.
8. Do not write code until you have fully figured out the algorithm. Explain the algorithm and share your thinking process. Julia had the mistake in one of her first 20 mocking practice.
9. Learn whiteboard testing. But test the code very hard. Do not fake it. Julia still found bugs by running the code using sample test case, after whiteboard testing. Do not fake the testing, work hard.
10. Prepare to extend the algorithm if the peer finish only first 10 minutes, try to extend the algorithm until the peer fails. Know how to measure the depth of the knowledge. Julia figured out after practicing more than 80 mocking practices.
11. Miss the optimal solution for an algorithm after more than 3 times practices. Julia knew the issue after 90 mocking practice.
12. There are always something new coming out in each mocking experience. Julia noticed that after she started third round.


Related work from Hackerrank contest 




Julia likes to play tennis sports and play hackerrank contests. Both needs hard work.

Julia played over hundreds of hours tennis sports, hundreds of double and single matches, experienced the muscle pain and all kinds of issues, she also experienced a lot of joy through the hard work. She learns to control the ball and placement so well over thousands of strokes, she gains the new sports skills.

Related to tennis sports, from June 2016 to June 2017, Julia built up similar experience through Hackerrank contests, she journal every practice, wrote down her emotion, time to play, short term and long term goal, she started to collect 7 bronze medal, 2 silver medals, one gold medal last 12 months. Exactly after 12 month, she got her first gold medal, top 4% in ranking of over 11,000 players. She adapted her skills on tennis sports to competitive programming field. 

Julia plays so many contests, there is always next one. No time to get frustrated long because she has to play next one and stay at the moment. It is hard to deal with frustration and expectation, but Julia learns to take care of herself with a lot of sports competition matches, just remind her that hard work beats the talent. Wishful thinking wastes time, but choose to sports therapy, learn from tennis professional players to work on basics. 

Learn to count algorithms


It is not easy to stay humble for computer science Ph.D. students. Julia worked on the computer science Ph.D. study from 2001 to 2010, she never learned to count how many algorithms she works on. There is no target, no goal setting on algorithm practice, and there is no result.

How does Julia happen to make changes after her full time work last 7 years? Julia learned the tough lesson when she developed the sales analysis report. She was challenged again and again about the number she provided, she did not handle the pressure very well the first few years. From 2010 to 2015, Julia does not count how many algorithms she works on.

Starting from 2015, she put months hard work together to rewrite C# code with the new design, she likes to integrate with Microsoft Excel easily so she can continuously build some analysis.

One day she sets a goal, she likes to be able to verify the final number in less than five minutes; she added the drill-down functionality in her report, she can quickly export large data sets and use Microsoft Excel to do further analysis to find root cause if need.

Be a top player in algorithm and data structure contest on hackerrank, Julia also sets up a goal.

Her goal is to complete 3000 algorithm practice, enjoy the journey; she works on leetcode, meanwhile playing hackerrank contest; when she plays hackerrank contest, she uses Leetcode algorithms to help her to be a better player. She only completes over 100 algorithm related to Leetcode algorithm. Her gists shows 851 gists on June 29, 2017. 

C# Minimum Heap implementation

June 28, 2017

Introduction


There is a PriorityQueue class in Java for minimum heap, but in csharp programming language, there is no class. Julia has to figure out how to write one by herself.

Search the blog using minimum heap implementation, the link is here.

Algorithm study 


8:00 pm - 8:30 pm C# practice is here.

Julia met a peer who is a computer science Ph.D., and she was asked to simulate the minimum heap using Array, Array.Sort. Julia followed the hint and she did write one. It works and the solution is correct. But she likes to make her simulation better. There is only 30 minutes in mocking experience, Julia could not write a real minimum heap so she chose to use an array and then sort it using O(nlogn) algorithm.

She needs to look into C# books and figure out how to do it better in short future.

One of ideas is to use C# SortedSet class. Review previous practice on Leetcode 295: Median of stream.


Book reading: Essential C# 4.0

June 28, 2017

Introduction



It is the seventh year Julia works on C# programming on the current job in the city of Vancouver. Last 2 years Julia tried so hard to reinvent herself, she chose to work on Leetcode, coding blog, and focus on the basics.

Julia knows that it is so enjoyable to read a C# book in her spare time, she did today using 20 minutes, on the topic called "16 Building Custom Collections".

Book reading plan 


Actionable Item

Next book to read:
Effective C# 50 Specific Ways to Improve Your C#
Second Edition Scott Meyers

Book review is here.

Algorithm design talk

June 28, 2017

Introduction


It is very interesting to learn different issues to learn binary search algorithm. Most popular algorithm is a binary search algorithm. When is your last time to write a binary search algorithm?

In last 6 months, Julia wrote at least 5 times binary search algorithms, she had at least 5 peers to work on binary search algorithm. She knows so many ways to create bugs in binary search algorithm, but today's mocking experience the bug is new, the series are not convergent at all.

Binary search algorithm


It is a long journey to work on binary search tree algorithm in 2017. Julia struggled over a few hours on binary search tree algorithm in one of Hackerrank contest, she could not figure out why she failed on an issue and could not make significant improvement even after the contest.

Julia did over 80 mocking experience since March 2017. One thing she learned most is the binary search algorithm. She wrote a few times and also she watched how peers worked on binary search tree algorithm. It is most favorite algorithm Julia likes to practice again and again.

One thing Julia was so surprised is the design the peer gave out in binary search algorithm which cannot be convergent. (Mathematics series –convergent)

Mocking experience


Julia regularly attended the church but she never practiced algorithm and data structure with a peer from 2010 to 2015. Those five years Julia learned a lot through small group church activities.

Julia used to have one real experience in 2015 and then she did not have any mocking experience. In 2016 Julia only did 8 mocking experience and then she moved on. In 2017 March, Julia started to try to practice mocking, and then she did very well last few months.


As a hackerrank player, Julia can relate mocking experience learning to contest playing. At the very beginning, Julia studied a lot of hackerrank players through leaderboard and blogs they share, code in submissions. Until November 2016, Julia was lucky to start to get involved with code review community and learned a lot through asking questions. She asked help on code review and then she learned to solve hackerrank contest problems better and more understanding. 

Now Julia had 80 mocking experience since March 2017, she met so many peers and then she starts to look into possible topic for her short research. What Julia likes most in the algorithm problem solving?



Tuesday, June 27, 2017

Inorder successor binary search tree

June 27, 2017

Introduction


It is time to work on a few solutions on this binary search tree inorder successor. A simple idea is to go over the leetcode discussion on the algorithm, and study a few solutions.


Algorithm practice


May 20, 2017 C# practice is here
June 27, 2017 8:00 pm - 8:30 pm, 30 minutes practice is here.

The C# practice with test cases is here. More simple code is here.

July 4, 2017
Work on the solution without using parent node pointer.



Monday, June 26, 2017

Leetcode weekly contest 38

June 26, 2017

Introduction


It is a good idea for the summer day. Get up early one week day morning, like 6:00 am or 7:00 am, work on one Leetcode weekly contest and get some morning workout.

Here is the link of Leetcode weekly contest 38.

Algorithm practice 

N-th root of a number

June 26, 2017

Introduction 


Plan to work on N-th root of a number on geeksforgeeks.com.

Algorithm practice 



May 3, practice is here

May 30, C# practice is here. Root a number by power of n, for example, 0.001 - n = 3, root number is 0.1. 

June 26, C# practice is here

Julia did white boarding test on her own code, and then she found a bug on line 29 on test case 0.001, n = 3, search value 0.1. Julia tested her own code very carefully, and then find a bug on line 29. The peer asked the question to point out the bug on line 75, return integerValue/ 1000.0; not integerValue/ 1.0. At the end, there is a dead loop, so Julia put some debug code and traced down the bug on line 74, type conversion bug. 



Sunday, June 25, 2017

Weight control project

June 25, 2017

Introduction



Summer is here in the city of Vancouver. One of goals in the summer is to play more sports, and also learn new skills to apply weight control.

Julia is busy working with hackerrank contests last 6 months, she also found out that she missed a lot of hours on tennis court. She used to spend a lot of summer time hours on tennis courts, play a lot of double matches, long hours to stay outdoor.

Weight control study 


Study BMI index again. Link is here. Plan to reduce the weight and get back to overweight, say goodbye to obesity weight. 




3000 algorithm practice

June 25, 2017

Introduction



It is estimated that a good software programmer should practice at least 3000 easy and medium algorithm based on her research on competitive programming. Right now, Julia had around 800 algorithm in her gist profile. It takes a while Julia adopts the idea called one algorithm a time based on her research on tennis coaching and mental strategies study. Never rush herself to finish algorithms. She used to study 10 algorithms in 3 hours, or 30 algorithms in one week, or tried to go over 70 algorithms in 3 or 4 hours.

It is better to learn one algorithm a time. Based on her study of the book "The art of competition programming", the book chapter the game plan of contest, Julia learned that it is also very helpful for her to go over each algorithm as many as possible ideas based on Leetcode discussion. She also learned that it is also very helpful to solve an expert level algorithm, in order to find a solution, Julia will quickly build up skills to do some research on algorithm, review the basics, and tries a few ideas.

Small research talk 



Read the blog again, link is here. Read the article again called "Competitive programming is a good use of time".

Review 3 advanced topics for competitive programming:

1. Fenwick tree
2. Max flow algorithm
3. Bitmask DP

Try to answer a few questions on Fenwick tree - binary index tree

One discussion on binary index tree is here on cs.stackexchange.com.

Second discussion on Fenwick tree is here on cs.stackexchange.com.

Study Hackerrank ProjectEuler+ leaderboard - link is here.

Codefights.com study

June 25, 2017

Plan to spend 30 minutes to study codefights.com website.

Friday, June 23, 2017

Game plan for a contest

June 23, 3017

Introduction


It is most enjoyable time to read a book chapter called "Game Plan for a contest", one chapter from book "The Art of Programming Contest".



Book chapter: Game Plan For a contest 



Julia likes to memorize classical problems for each classical algorithm. Here is the set of problems.





ACM ICPC world final problems - link is here

Leetcode 140: Word Break II

June 23, 2017

Introduction


Problem statement 


Plan to work on word break II algorithm sometime in short future.


Julia worked on Leetcode 139: Word Break I before, here is the blog.

Leetcode 55: Jump Game I

June 23, 2017

Introduction




Julia worked on the algorithm in 2015. Here is her C# practice.

Leetcode 45: Jump Game II

June 23, 2017

Introduction


It is one of hard level algorithm. The problem statement is here.

Julia worked on the algorithm in 2015. Here is her C# practice.


Algorithm 


Julia spent over 30 minutes to study one of greedy solution posted in the discussion, and then C# practice is here using greedy algorithm. 

Wednesday, June 21, 2017

Leetcode 72: Edit Distance

June 21, 2017

Introduction



Plan to work on Leetcode 72: Edit Distance again. The problem statement is here.

Algorithm study 



Julia's C# practice is here

Follow up

Dec. 10, 2019 10:49 PM

It is better to add code to the blog. Also I spent 10 minutes to review the code, there are three cases involved to build next iteration in dynamic programming, left, top, and left and top, first two the increment is 1, last one may be one or zero, depending on last char in two strings are the same or not.

This definitely is a good practice question for dynamic programming.

Tuesday, June 20, 2017

Can mock interview make difference? Continued II

June 20, 2017

Introduction



It is the first time Julia continuously works on mock interview experience starting from March 2017. Now she starts to understand the process better, and she starts to learn more things from the activities.

"It takes a village to raise a child". Julia knows that she could not do something alone and one day she is expert on algorithm and data structure. It is the great learning experience to work on the same algorithm together with a peer and learn from each other. 

Recently a computer science undergraduate student asked Julia what advice she has, because the peer likes to get more professional interviews from refdash.com. 

Julia learned a few things through the conversation. Julia was told that interviewbit.com is very popular site to practice coding.




Research talk 


Julia had her first professional mock interview experience in May 2017, and she got the comment like the following:

"Pretty solid interview overall. Algorithms and problem comprehension was on a pretty high level. Coding was good as well, but got a bit sloppy at times when we got to details (very minor edge cases)."



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.


Can Leetcode weekly contest make difference?

June 20, 2017

Introduction



It is a ritual to do small research every day. Today Julia chooses a topic called "Can Leetcode weekly contest make difference?"

The reason Julia chose the topic is that she found out her last leetcode weekly contest reminded her to work on the basics - linear scan array more efficiently. The blog is called Leetcode 605: Can place flowers.  Julia found a very short solution through Leetcode discussion after she spent 48 minutes in the contest, she learned to solve the problem using 5 minutes. Only 10% of time, she learned the basics of linear scan an array, looping first.

On June 19, Julia noticed that she performed better on mocking experience of algorithm Leetcode 151 compared to her last one more than one month ago.

The argument is that "Leetcode weekly contest makes difference".


Performance talk 


Leetcode.com is so helpful because it attracts million players to share ideas, compared to code review on stackexchange.com, Julia found out that Leetcode.com is a good place to find excellent ideas to solve a Leetcode algorithm, but codereviwe.stackexchange.com is an excellent place for Julia to practice good writing and learn how to share her learning. 




Monday, June 19, 2017

10 steps to master dynamic programming (step II)

June 19, 2017


Plan to work on interviewbit.com dynamic programming tutorial. Here is the link of dynamic programming algorithms.


First Gold Medal on Hackerrank

June 19, 2017

It is time to celebrate first gold medal on Hackerrank. Julia won her first gold medal on hackerrank, she played week of code 33, and then she worked hard and then she was in top 4% ranking.

Here is the image she likes to show the medal to celebrate. It is not easy, after more than 12 months, she finally made it happen.


Here is julia's hackerrank profile link.

Julia likes to play hackerrank contest, and also she works hard on basics through Leetcode algorithm practice.

Here are the contests she attended and she likes the failure and also likes the progress to gain skills to perform better. It took her six months to get her first gold medal in 2017.


She still remembered in April she played this contest called world codesprint 10, she documented that the huge difference between top 10 players and Julia's performance. The blog link is here.

In April, Julia set a goal for a gold medal. Here is the blog called "Talent small talk".

Psalm 126: 5 Those who sow with tears will reap with songs of joy.

Sunday, June 18, 2017

Leetcode 76: Minimum Windows Substring

June 18, 2017

Problem Statement

First step Julia spent over 60 minutes to write and then failed several times, she finally passed first 267 test cases, and last test case failed with timeout error. C# code is here.

A lot of failed test case in her practice:

1. A lot of out-of-boundary index error, "abc", "a"
line 57 and 58, search[left] - make sure that left is in the boundary of the array

2. "a", "aa", need to check counts as well.

Knight Covering - codeChef

June 18, 2017

Introduction



It is very good learning experience to play contest on codeChef. Julia is a rookie to play short contest, 2.5 hours. She started to choose to read chinese version of problem statement, here is the problem statement.

She also did some google search, and found the similar algorithm, N x N board instead. She spent 10 minutes to read the algorithm. Link is here.

Saturday, June 17, 2017

Leetcode: Number of Connected Components in an Undirected Graph

June 17, 2017

Introduction



Julia has to work hard on expert level algorithm, she plans to work on the algorithm called "Path Matching" in the week of code 33. Julia needs to find some topics to study in order to come out a working idea to solve partial the algorithm.

One of her studies is about network, n nodes with n - 1 edges, what implies to this graph? Julia likes to find path for any two nodes. What should be included for a good consideration before she comes out the idea to search a pattern.

Algorithm study


Read the blog written by Grandyang, the blog link is here.

Leetcode: Number of Islands II

June 17, 2017



Introduction




Julia has to work hard on expert level algorithm, she plans to work on the algorithm called "Path Matching" in the week of code 33. Julia needs to find some topics to study in order to come out a working idea to solve partial the algorithm.

One of her studies is about network, n nodes with n - 1 edges, what implies to this graph? Julia likes to find path for any two nodes. What should be included for a good consideration before she comes out the idea to search a pattern.



Algorithm study


Plan to read a blog written by jcliBlogger, the link is here

Leetcode number of islands II, the link is here



Leetcode: Graph Valid Tree

June 17, 2017


Introduction


Julia has to work hard on expert level algorithm, she plans to work on the algorithm called "Path Matching" in the week of code 33. Julia needs to find some topics to study in order to come out a working idea to solve partial the algorithm.

One of her studies is about network, n nodes with n - 1 edges, what implies to this graph? Julia likes to find path for any two nodes. What should be included for a good consideration before she comes out the idea to search a pattern.

Algorithm study 


One blog written in Chinese called grandyang is here.  It is now 9:15pm, Julia likes to go over the algorithm 15 minutes before she moves on to the Leetcode discussion session for broad discussion. 

Plan to study the code in the blog, and write a C# version. UnionFind using array is very good practice. 


Hidden message algorithm code review

June 17, 2017

Introduction



The algorithm "hidden message" is the medium algorithm in stryker contest in 2016. Julia decided to review the algorithm based on her blog since she likes to get more idea on how a trie data structure to solve the string search algorithm very well. Recently Julia noticed that she could not figure out using trie to solve a timeout issue on Leetcode algorithm 212 Word Search, she knows that her training has some issues, she needs to emphasis more on trie. 


Algorithm code review 



The C# code is here to review.

Leetcode 572: subtree of another tree

June 17, 2017

It is time to review one of blogs written for the algorithm. The blog link is here.

Leetcode 459: repeated substring patterns

June 17, 2017

Problem statement


Leetcode 44: wildcard matching

June 17, 2017

Problem statement

It is hard level algorithm. Julia tried the algorithm a few times in mocking experience, she used the algorithm a few time to interview and also was interviewed.

Now it is 9:36 am, Julia likes to read some discussion. Plan to spend 20 - 30 minutes.

First, Julia was advised in mocking experience to use recursive function to make the code more easy to write.

Special test cases are looked into:

1. ?*, any character repeated multiple time, ? represents any character, * means repeating multiple times.

2. If string is finished, but the pattern string is not, it is still possible to match. Pattern string ?*, a* or a*b* etc.

3. Some challenging matching, like "aaa" to match "a*a", how to wisely calculate a* pattern to match first two chars instead of all three characters.

Study code using DP solution - link is here.

Path Matching - week of code 33

June 17, 2017

Problem statement


Research and study plan 


It is the expert level algorithm. As a hackerrank player, Julia is still learning how to solve the expert level algorithm partially. What she likes to do is to dedicate a few hours, think about ideas, study related topic, and most important is to go over related algorithms in Leetcode, topcoder, hackerearth, and read some lecture notes.

After a few hours study, Julia starts to come out some idea to solve basic sample test cases first, leave timeout and performance issues as is until she comes out the great idea to solve the issue.

1. Leetcode 44 - wildcard matching - 20 - 30 minutes research and study, documented in the blog:
wildcard matching.

2. Review string search algorithm KMP, Rabin algorithm on topcoder. Link is here.

3. Review KMP and other string search algorithm on Julia's coding blog as well. Now it is 10:11am.

4. Review "the hidden message" algorithm on hackerrank contest. The blog is here.

5. Leetcode: Graph Valid Tree - the coding blog of grandyang is here.

Time is 9:07 pm, June 17, 2017
It is hard to figure out the idea to solve the path between two nodes. Julia likes to study some good algorithm.

She googled n nodes n - 1 edges meaning - no cycle in the graph, a tree?

6. Read lecture notes about union find data structure - lecture notes by Princeton is here. Now it is 9:55 pm.

Follow up after the contest


The code submitted in the contest is here. Score 0.47 out of maximum score 100.

Plan to study the Java code written by Salmur - score 100, link is here.

Plan to study the discussion provided by one of players. Link is here.

Friday, June 16, 2017

Bonnie and Cylde - week of code 33

June 16, 2017

Introduction


It is the expert level algorithm and Julia likes to work on the algorithm. 


Expert Level


Julia chooses to work on the expert level algorithm, Bonnie and Cylde. She chooses to study graph algorithm for a few hours, and then tries to find a solution. 

First, she reads the topcoder graph blogs. Blog link is here

Next, she will search all graph algorithm in Leetcode marking hard level, she will quickly go over 5 - 10 of them. 


Third, undirected graph lecture notes - link is here

Fourth, detect cycle in directed graph, link is here. Detect cycle in undirected graph, link is here

Fifth step, go over graph algorithms on geeksforgeeks.org website. The link is here

One of graph algorithms, "Print all paths from a given source to a destination". The blog is here

"Competitive Programming" authored by - Graph

Union find algorithm on hackerearth - link is here




Progress Report



Now it is 8:44 am Saturday morning, Julia has to review her submission result. The interesting part of expert level algorithm is that Julia has to go over a lot of content about graph, a lot of reading, and then she decided to use one of algorithms to solve the problem. 

The idea to solve the problem was original wrong, and then she made a minor change to make sense on second sample test case. 

The another interesting fact to write code for expert level algorithm is that Julia does not have a lot of code to write. The idea is quiet simple, but a few test cases timeout. It is hard to find the right idea. Julia has to do time analysis for the algorithm and see which one can survive the time limit. 


Follow up after the contest


Julia submitted the code in the contest and score 25% of maximum score, 22.86 out of maximum score 80. Julia just used union find algorithm and then used another idea to apply union find second time to exclude one of two source nodes. Code is here

Thursday, June 15, 2017

Leetcode 516: Longest palindromic subsequence

June 15, 2017


Work on Leetcode 516: longest palindromic subsequence

Julia's C# practice is here.

Palindromic table - week of code 33

June 15, 2017



Here is the progress report of the algorithm at 10:05 pm.



Now it is 10:41 pm, Julia checked the edge case:

1. A single digit is a valid palindrome.
2. Note that a sequence of only  element can contain , but  is invalid as it contains a leading zero.

Julia fixed the bug related to edge case, now she scored 60 out of maximum score 60. Very good, Julia started to go over the problem statement and found the bug. She checked that scores on leader board from 50.00, 51.67, 53.3, 56.66, 58.33, 60.00.  Last time she scored 50.00. So she tried to find small edge cases, but she found all of them. 



Progress report


One thing Julia learned through the algorithm is that she has to take care all small edge cases, she failed test case 40 and 41, and then she figured out the edge case and submitted on June 16, 2017. 

Now it is 8:53 am. And Julia had one test case with timeout issue, she has no idea to solve the issue. 

To play the contest, Julia learns a few things, one thing is to write down test cases for small edge cases. Think carefully. 


Follow up after the contest 


Here is the code submitted in the contest, which passed all test cases except timeout on test case 30.