Hackerrank RookieRank 2 - prefix neigbhors (II)

Feb. 12, 2017

Problem statement

After the contest, Julia likes to study a few of solutions in C#, Java and other languages.

Code study of submissions

C# code

C# code.

Have some difficulty to understand the algorithm behind Index.Add method. Need to figure out later. Add some test cases to C# code, debug and understand the code one line by one line.

Study a few things about C# coding style, pascal case, set, get, and then using GroupBy, OrderBy, Aggregate, Stack, HashSet, Dictionary.

Second Study 

C# code study II

C# code is here. 

Third Study 

Java implementation

Problems

The most readable code is here with trie implementation. Julia chose one solution from near 100 solutions, this one is easy to follow. Will rewrite the C# solution based on this Java implementation.

Actionable Items

1. Instead of studying other people's code, Julia decided to look into test case 11 and figured out why her submission failed the test case. 

2. Read editorial notes from hackerrank, understand the idea, google search them:

This problem can be solved using Trie and DP. Create a trie from the given set of strings. Find the prefix neighbor of each string. Now create a graph such that each string is a node and there exist a bidirectional edge between two nodes only if they are prefix neighbors. Now find the maximum weighted independent set.

Statistics

Difficulty: Medium

Time Complexity:

O(N*max_length_of_string)

Required Knowledge: Trie

Publish Date: Mar 25 2016

Read the wiki article - Independent set ( graph theory)

GeeksforGeek problem - Largest independent set problem. 

3. Julia did not know the importance of problem solving in the contest and after the contest from Feb. 11 - 13, 2017. She tried to understand the other people's submission after the contest, and she had difficult time. She needs to understand the algorithm first, just follows the notes: find the maximum weighted independent set

4. Spent over 2 hours to rewrite the C# code, and post a question on stackexchange.com.  

Problem solving - community help

Feb. 25, 2017 5:27pm

With the help from Peter Taylor through his code view, Julia learned so much about the problem solving skills. She answered code reviews one by one, and then felt so comfortable with the algorithm problem solving. The code review experience is top-rated performance. 

Share some comments here:

Advice #6, KISS, why? what is wrong to insert them all into one trie? This is a good question. I tried to use the above code, but use one trie instead of going through A to Z one by one, run the code on hackerrank, error from test case 6 to 19; And then, I tried not to sort by the length of string, error from test case 6 to 19. – Jianmin Chen Feb 15 at 5:06   

Very good review, I did spend over a few hours in the contest and also a few hours after the contest. I like the last review "KISS, why?" most, remind me 5 whys for root cause analysis. Bravo! – Jianmin Chen Feb 15 at 5:11  

Hackerrank RookieRank 2 - prefix neighbors (I)

Feb. 12, 2017

Problem statement

Julia spent a day to work on the algorithm in the contest, Feb. 11, 2017. She reviewed her previous practice on trie, and then solved the algorithm to gain 14 out of maximum 50 points.

Her C# code is to create a trie to go over all strings, and then set each string to an array with size 11. Since the string's length is less and equal to 11, go over each length from 11 to 1, and then add those nodes to selected subset, set prefix neighbor node to exclude.

Actionable Items:

In the contest, Feb. 11, 2017, Julia spent over 3 hours to study the algorithm, over 2 hours to work on her trie implementation C# code in Sept. 7, 2016, make it more readable.

And then, Julia also spent over 3 hours to work on C# code to solve prefix neighbor algorithm. This is the perfect practice Julia learned to solve. It is out of her comfortable zone, and then she started to think on her feet and figured out something working.

More concerns about time spent, Julia should spend time wisely.

Hackerrank Rookierank 2 contest

Feb. 11, 2017

Introduction

Julia got excited. She still has 20 hours to go, and she only needs to work on last algorithm with medium level. She likes to document her practice starting from 12:42pm, how does she do to study, research, and catch up, and make some points from maximum 50 points.

Let us review what she has done so far, compared to the top 1 ranking player.

Some facts to share:
1. The last algorithm can be implemented in 20 minutes by the top performer.
2. The KnightL on a Chessboard is implemented by the top performer in 34 minutes; Compared to the best one, Julia spent 160 minutes.

Practice in the contest

Julia likes to work on the algorithm Prefix Neighbors, try to make things simple as possible. She started from 12:25, and then spent 3 hours to work on the algorithm.

Progress report 

12:25 - 3:22pm - Feb. 11, 2017

Discussion about sorting strings, radix sorting is a good idea to try. More detail, I think that string sorting is using radix sorting. The test case 4 A ABC AC ACD is sorted by 26 O(N), N <= 11.

Passed first 10 test cases

Worked on the coding from 7:00pm - 12:00pm, and then fixed bugs until 2:26am. Gave up. Learn a ton of patience, develop some skills. 

Here is the comparison: 

Coding is like tennis sport

Julia likes to work hard on the algorithm problem solving. So, she plans to take a break 1 - 2 hours first and then continue to work on the algorithm. 

Have 30 minutes workout to relax first, 90 minutes shopping trip. Saturday is the fun day. 

Try to remember the whole paragraph: 
frustrating sport, 
no way around the hard work, 
embrace it, 
put int the hours to improve somethings, 
a lot of sacrifice and effort, 
sometimes little reward, 
but you have to know that, if you put in the right effort, the reward will come. 

Code review - Leetcode 17: Letter combinations of a phone number

Feb. 8, 2017

Julia decided to review her previous practices, and then she rewrote the C# code to prepare code review on stackexchange.com. The question was reviewed in less than 8 hours.

The review is conducted by the C# expert.

Actionable Items:

1. Julia did not know C# StringBuilder.Length property can be used to modify the length of string. Read the document about the comparison with string.Length. Through code review, Julia learned the lesson.

Please go over all the properties and function of StringBuilder.

2. The review's highlights:

  Julia put together the C# code with code review's advice.

  1. Declare a class PhoneKeyboard
  2. Declare a public static readonly variable:
 private static readonly string[] keyboard = new string[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
3. Function name FindAllWordsForNumber
public static IEnumerable<string> FindAllWordsForNumber(string digits)

Coding is like a sport, you have to give yourself
chance to play against top players. Thanks for
the code review to show me the great strength
from one of top players.

- jianmin chen Feb. 11, 2017

Google OKR study

Feb. 7, 2017

Study Google OKR

Watch How Google sets goals: OKRs, and read an article of Google Internal Grading System uses for its employees.

SMART
. Specific
. Measurable
. Achievable
. Relevant
. Time-bound

18 minutes video, OKR Crash Course - How to set Goals
28 minutes video, How to Align your Company with OKRs

Hash function, hash table lecture notes study

Feb. 6, 2017

3 lecture notes to study 

Spent more than 2 hours to study the lecture notes - Lecture 6 about Rabin-Karp algorithm from MIT, and also lecture 7, resize of hashtable. 

Will come back to write down some notes and also share something about the algorithm.

Lecture 5 notes: 

Hash functions

Consider a function h(k) that maps the universe U of keys (specific to the hash table, keys could be integers, strings, etc. depending on the hash table) to some index 0 to m. 
We call this function a hash function. 

A good hash function

. satisfies ( approximately) the assumption of simple uniform hashing: each key is equally likely to hash to any of the m slots. The hash function shouldn't bias towards particular slots

. does not hash similar keys to the same slot (e.g. compiler's symbol table shouldn't hash variables i and j to the same slot since they are used in conjunction a lot)

. is quick to calculate, should have O(1) run time

. is deterministic. h(k) should always return the same value for a given k

Example 1: Division method 

prime number vs should ok be a power of 2 

h(k) = k mod m 

if m = 2 ^p, then the h(k) only looks at the p lower bits of k, completely ignoring the rest of bits in k. A good choice for m with the division method is a prime number ( why are composite numbers bad?). 

Example 2: Multiplication method


h(k) = floor(m(k A mod 1))

Collisions

Chaining - 

load factor alpha

If there are n keys in a hash table with m slots, we can the load factor alpha for the hash table to be n/m. 
Under the assumption of simple uniform hashing, the length of each linked list in the hash table is alpha. 

Open addressing collisions 


Linear probing 

Linear probing resolves collisions by simply checking the next slot, i.e. if a collision occurred in slot j, the next slot to check would be slot j + 1. More formally, linear probing uses the hash function 

  h(k, i) = (h'(k) + i ) mod m. 

Quadratic probing resolves collisions in a similar fashion: 

h(k, i) = h'(k) + c₁ i + c₂ i²) mod m

for some constants c₁, c₂. Instead of linearly traversing through the hash table slots in the case of collisions, quadratic probing introduces more spacing between the slots we try in case of a collision, which reduces the clustering effect seen in linear probing. 

Double hashing resolves collisions by using another hashing function to determine which slot to try next. 

Lecture 6 notes 

Rabin-Karp algorithm

probe sequence  

Performance of Open Addressing

linear probing 
quadratic probing 
double hashing 

simple uniform hashing assumption (SUHA)
a hash function mapped to any slot from 0 to m -1 with equal probability 

uniform hashing assumption (UHA) 
a random permutation of the slots 0 to m-1 

load balance alpha, p = 1 - alpha probability that the first probe will find an empty slot under UHA. 

Universal hashing  

Rolling hash 

Lecture 7 notes

Hash table

Learn a few keywords:

probe sequence  

Performance of Open Addressing

linear probing 
quadratic probing 
double hashing 

simple uniform hashing assumption (SUHA)
a hash function mapped to any slot from 0 to m -1 with equal probability 

uniform hashing assumption (UHA) 
a random permutation of the slots 0 to m-1 

load balance alpha, p = 1 - alpha probability that the first probe will find an empty slot under UHA. 

Universal hashing  

Rabin-Karp algorithm

Feb. 6, 2017

Introduction
Julia usually does some sports workout after intensive study. This time she chose to study Rabin-Karp algorithm, play with Rolling Hashing algorithm.

She needs some break from the code review Leetcode 49. Julia also traces the top performer's review, here is the one review Rabin-Karp algorithm.

Study

Read Rabin-Karp algorithm wiki article, some keywords from the article:

hash collisions

linear congruential generator 

modular arithmetic

prime

Rabin fingerprint

rolling hash - moving average 

Rabin-Karp rolling hash - read twice, very good talk about time complexity analysis 

Read the article - write down some words: 

https://courses.csail.mit.edu/6.006/spring11/rec/rec06.pdf

Actionable items:
review string algorithm - hidden message.

Rabin-karp algorithm implementation is here in C#.

Strategy and tactical/ technical development - tennis sports coaching

Feb. 5, 2017

Introduction
Julia learns tennis sports and rebuilds her character a lot through last 5 years sports activitities. So far, she has played over 300+ hours tennis, and also she is very famous to play with every one, she does not choose to stay in elite group, she just takes herself out of comfortable zone, and then meets people and play her sport while enjoying outdoor activities. She learns Canada as a country through her tennis sports, she talks to people, she starts to think and analyze, compare to United States as well.

She now is a Canadian citizen starting from 2015 and tries very hard to integrate her activities to the country, and learn the society. She knows the value of her time and also appreciates that she learns from her most favorite friends over 80 years old, over 70 years old, over 60 years old, encourage them to play with her. She enjoys to play with new players, and enjoys the running and chasing the tennis ball. She keeps out-of-breath and back-to-normal back and forth, and she builds up the strength, believe that hard work beats talent. She is just a sports woman who knows that it is never too late to fall in love with sports, enjoys your own strong muscle and strength to make a living, it does not matter how hard for her to run for the ball, sometimes she just goes for it.

But tennis sports is also very highly-skilled sports, you learn more and then you are more popular on the court. That is something Julia likes most, her power to grow her skills on the court.

Strategy and tactical/ technial development, the top coach gives out a talk around 45 minutes.

Study

47 minutes lecture of tennis strategy and tactical/ technical development. Video is here.

Quality on-court coaching - tennis sports study

February 5, 2017

Introduction

Julia spent a lot of time on tennis sports training starting from 2012, but she always looks for great coaches and their videos. She prefers to take courses by herself. One course a time.

Share her most favorite on-court coaching, a few minutes, tennis player safarova. 

But Julia also likes to spend one hour lesson from tennis icoach, she could relax and enjoy the weekend. 

One time in Burnaby central park tennis courts, Julia played double game with an a gentleman, and then she thought that her partner ran slow in the match and wondered if she should push him a little bitter, but she hold the thought. But she was told that her double partner is over 82 years old. Julia just learned that life is such amazing thing, when you are patient, even people over 82 years old likes to work for you. Bravo!

Julia just learns to play sports, and play with all age groups.

So much fun to play, but Julia really likes to coach new player as well when she has chance. She have to take lessons first.

Video study lesson

1 hour lecture, Julia enjoyed so much. 

This is from the 2015 LTA National Coaches’ Conference covering the responsibilities of a coach, development phases and the importance of training loads when working with junior players. This is an on-court presentation with a focus on how to make the exercises relative to the goals, age and standard of the players, how to set long term and short term goals and the significance of having a daily plan with each player to reflect the needs of the player. The presentation includes practical examples of drills and how to communicate with different ages.

Customer review - a blog writer learning experience

February 4, 2017

Introduction
Julia got a few comments in 2016, she never knew that she had to learn how to treat her customer nicely until Feb. 3, 2017. She got a comment about the very well-written blog, after 6 months, she read it again and amazed that she can learn something from her blog as well. The customer reminds her to stop and enjoy her own document, she comes back to learn the counting inversions algorithm again.

She writes blog and she welcome people to read and make comments. Since the blog has too many items, even herself has some difficulty to recall what she has written before. Every time she reviews statistics, she reads the blog posts people views, she has to rush to fix it to make it more readable, understandable. She is growing more ideas to make the blog full-fledged (she first time uses this word :-)).

Here are some blogs she got comments up to Feb. 4, 2017.

1. Feb. 3, 2017, Count inversions
2. January 13, 2017, Award budget cut.
3. Sept. 14, 2016, Bonetrousle - HackerRank world code sprint #6
4. August 6, 2016, Productivity Tips for the busy tech professional - pluralsight.com
5. April, 2016, HackerRank: Bear and Steady Gene algorithm (IV)

Workout

Share all blogs she got comment to Google+, therefore, people are more happy to read the blogs and get more involved as well.

Leetcode 49: group anagrams

Feb. 4, 2016

Introduction

New habit

Julia spent some time to read question on code review first thing in Saturday morning, and then she read about Leetcode 49: group anagram. After a few minutes, she did a few things in steps, first think about solution by herself, a little nervous, and then read the discussion. She quickly decided to practice the algorithm in Saturday morning, no hackerrank contest, and she could not get up at 8:00am to catch Leetcode 1.5 hour contest. 

Anagrams

Share some facts about anagrams. Julia did a lot of research on anagram recently, she answered the time complexity code review recently on algorithm Hackerrank sherlock anagrams, but no one gave her up-vote. She worked on the algorithm over a week, and spent over 10 hours to think, asked a review also. She tried twice but no one had responded to her, she knows that she need to open a new question and invite her friends JS1 to come to help. 

Leetcode vs Hackerrank

Also, Julia checked her previous Leetcode practice but she never did practice this algorithm before. She had difficulty continuously completed most of Leetcode algorithms, a few of her Chinese friends advised her to work on leetcode, after 12 months practice, she chose to work with Hackerrank starting from April 2016, her new favorite platform to practice, and also later to play Hackerrank contests, she had more fun and sense of achievements.

So, Julia did practice the algorithm using C#, and gave her answer for code review. Hopefully, this time she can get her answer to be chosen as the answer in her first time. Wishful thinking, this day may never come. Julia will open a new question based on her answer and then ask JS1's help to review the code.  

Code review sportsmanship

Most of important, she understood how code review works in 48 hours time frame. People will answer the question first, and then, a person like Julia will rush to help, because Janos is the moderator of code review, he just did make a lot of good review, Julia likes to make it complete and thorough. That is part of sportmanship Julia learned recently on code review. Haha, Julia is full of sportsmanship in her talk. She also learns from her favorite double tennis player ranking No.1 in Feb. 2017 - Bethany Mattek-Sands, she chose high-ranking player to partner with her, single player ranking Safarova is around 55.

Code review

Julia likes to conduct some study on this algorithm, study other people's solutions first, and then prepare to make the C# code best of her understanding, ask a code review on stackoverflow.com as well. 

She has weakness on work against test cases, and need to catch up more on C# as a language. So many things she likes to do in the weekend, but she needs to write some code, and get some research done on Leetcode 49 first. 

Code review link is here on stackexchange.com. She needs to walk away little bitter since the discussion is hot out there for a while (12:05pm February 5, 2017). 

One blog a time

Feb. 2, 2017

Introduction
Julia came cross the quora article, and then she found a lot of blogs to read.

One blog a time

John L Miller, one blog a time.

28 posts are here.

Actionable Items:

After a few days of study with the author's post, Julia decides to write posts on quora as well. The platform on quora gave better user friendly things like upvote, and also stay with a lot of other people more closely.

Julia has worked on her English writing on blogger over 18 months, it should be ok to write posts on quora. Google blogger shows better in google search than quora.

Julia also needs to learn and discuss things about relationship. How to help the younger generation to go through the highly competitive world? she also needs to learn to build good relationship as an aunt, sister, and other roles in her life.

Udacity - Design of Computer Programs, Programming Principles

Feb. 1, 2017

Plan to study the course: 

Udacity: Design of Computer Programs, Programming Principles

Udacity - algorithm - social network analysis

Feb. 1, 2017

Plan to take the course, 15 minutes a time. Test how good I can to follow the lecture. 

Udacity

intro to algorithms

Social network analysis

Course overview is here. 

Lesson 7: Spy Control Setup - game of Nim 

Julia also worked on Hackerank - game of Nim recently. Here is the blog. 


Feb. 12, 2017

Duncan Watts - Microsoft principal researcher. 

Lili Cheng - The sociable researcher in Microsoft. 

Keynote: Building a Social-Search Engine From Scratch, one hour video.