Leetcode 41: First missing positive

Nov. 1, 2017

Plan to look into Leetcode and find the similar algorithm called get smallest nonnegative number.

Get smallest nonnegative number, do not change the array.

My C# practice code is here on Nov. 1, 2017

Also, I spent almost 50 minutes to interview the peer on Nov. 2, 2017 and had some discussion about the algorithm. I like the peer to go over the base cases to show very good reasoning.

[],   0
[0], 1
[1], 0
[0, 2, 3]  1
[3, 0 , 2] 1
[0, 1, 2, 10000]

Leetcode 41: First missing positive 

It is the hard level algorithm. Time complexity is O(n), space is O(1).

Maximum Disjoint Subtree Product - World codesprint 10 (II)

May 3, 2017

Introduction

The algorithm is one of hard level in the hackerrank world codesprint 10. Julia put together a C# code after she chose to study one of C# submissions in the contest. She likes to ask code review on stackexchange.com.

The algorithm is a depth first search algorithm, after over a few hours study, the algorithm becomes easy to understand.

Here is the C# code almost ready for code review.

Code review 

Code review link is here.

Toll Cost Digits - World CodeSprint 9

April 27, 2017

Introduction

Problem statement is here.

Hard problem, time complexity O(N+E), required knowledge: graph, BFS/ DFS.

Plan to work on the algorithm 30 minutes a time.

Hackerrank week code 28 - Choosing White Balls

January 14, 2017

Choose white balls - problem statement

Introduction
What is the feeling about sitting on the bench while the match is going on? That is something Julia went through in the contest. She tried to do some reach, make 10 - 15 points if possible. One of practice here is to study player's discussion board, and see how top-players are doing when they need to communicate and have some discussion. It is not bad at all to see all over the world, people came together and exchange ideas for the same algorithm.

In the contest 

Hard algorithm, maximum score 54 

Study the khan summation algorithm - read discussion and found some one gave out this tip.

The discussion here is very helpful, at least it is helpful to understand the problem. Work on the example first.

Julia spent 10 minutes to work on the example here:

WBWBW

Analysis with a fault: 

The analysis with some issues:

step 1: 1, 3, 5 are white and 2, 4 black -> 3/5

step 2: 3 possible new sequence

BWBW -> 1 WBWB -> 1 WBBW -> 2/4 -> 1/3 * (1 + 1 + 2/4) = 5/6

total = 3/5 + 5/6 = 1.4333333

Analysis with corrections:

You do not choose xi, they are chosen randomly. You only choose either left or right for given xi. Therefore in step 1, if xi was 2 or 4, you end up with sequences WWBW or WBWW in step 2, you need to count these in your expectation. 

Then you get 3/5 + 1/5 ( 1 + 1 + 2/4 + 1 + 1) = 1.5

Hours of reading - Discussion

BWBWW

Set up a test case for BWBWW - the answer should be
Discussion is here.

BWBBBW

January 14, 2017

Choose white balls - problem statement

Study the khan summation algorithm - read discussion and found some one gave out this tip.

The discussion here is very helpful, at least it is helpful to understand the problem. Work on the example first.

Julia spent 10 minutes to work on the example here:

WBWBW

Analysis with a fault: 

The analysis with some issues:

step 1: 1, 3, 5 are white and 2, 4 black -> 3/5

step 2: 3 possible new sequence

BWBW -> 1 WBWB -> 1 WBBW -> 2/4 -> 1/3 * (1 + 1 + 2/4) = 5/6

total = 3/5 + 5/6 = 1.4333333

Analysis with corrections:

You do not choose xi, they are chosen randomly. You only choose either left or right for given xi. Therefore in step 1, if xi was 2 or 4, you end up with sequences WWBW or WBWW in step 2, you need to count these in your expectation. 

Then you get 3/5 + 1/5 ( 1 + 1 + 2/4 + 1 + 1) = 1.5

Hours of reading - Discussion

BWBWW

Set up a test case for BWBWW - the answer should be
Discussion is here.

BWBBBW

Discussion is here. 

Summary of Contest Activities

In the contest, spent hours to read the problem statement, discussion, did some research. No code, did not make any points.

HackerRank - matrix rotation (Series 4 of 5)

Nov. 8, 2016

Plan to work on unfinished HackerRank algorithm related to array, try to score full score this time to celebrate new year 2017.

http://juliachencoding.blogspot.ca/2016/04/hackerrank-matrix-rotation-ii.html

Rotate array - HackerRank

problem statement:
https://www.hackerrank.com/challenges/matrix-rotation-algo

Write C# solution:

Review April, 2016 practice: 

another practice: (more than 1 hour, still having bugs, score 8.89/ wrong answer)
https://gist.github.com/jianminchen/57572227dafe939060f7cc81b193cd9b

Will come back very soon with the solution, hopefully score a hard algorithm perfectly. 

Dec. 6, 2016
Fix the bug on line 114, declare a new variable on line 114 actualSteps
C# solution - pass all test cases:
https://gist.github.com/jianminchen/6fabef7436097552e35633a549b0268a

There are over 100 C# solutions, Julia, let us have some fun; code review as many solutions as possible. 
Post C# solution here:

HackerRank NCR codesprint - Game of Numbers

Nov. 7, 2016

Problem statement:

https://www.hackerrank.com/contests/ncr-codesprint/challenges/game-of-numbers


Her first submission:  score 15 of 50
https://gist.github.com/jianminchen/ef96b59d7279f1b80473519434ab959f

In the 48 hour contest, second day evening around 9:00pm, she could not believe that she could make 15 of 50 so easy so quick.

Celebrated her work by showing her workout sheet.

Editorial Notes:

Julia did not know how she is so close to perfect solution; she only need to minimize the module size to 11 for her test case, start left = 1, end right = 11, instead of 21 she figured out in her workout sheet.

She did not notice that her work needs to be examined carefully. Hard problem can be completed in 10 - 30 minutes, Julia spent over 4 years to study applied mathematics in SJTU, she just did not practice a lot at all in last 6 years. She is very comfortable with discrete mathematics.