Julia's coding blog - Practice makes perfect

From January 2015, she started to practice leetcode questions; she trains herself to stay focus, develops "muscle" memory when she practices those questions one by one. 2015年初, Julia开始参与做Leetcode, 开通自己第一个博客. 刷Leet code的题目, 她看了很多的代码, 每个人那学一点, 也开通Github, 发表自己的代码, 尝试写自己的一些体会. She learns from her favorite sports – tennis, 10,000 serves practice builds up good memory for a great serve. Just keep going. Hard work beats talent when talent fails to work hard.

Showing posts with label bit manipulation. Show all posts

Wednesday, October 9, 2019

How to write an excellent post?

Oct. 9, 2019

Introduction

It is the first time I learn that I can write a post and then get 4 upvotes, ranking top 7 in one of hard level algorithm on Leetcode.com.

Crafting skills

I think that it is not difficult to write an excellent post. The algorithm I studied is so easy to understand, since I put together some comment to make it so straightforward.

And also I did spend time to save a graph from weekly contest lead board, and then wrote down my observation.

It is so important for me to learn how to document good learning process for other players.

Being a good mentor, helper, or player, I strive to document my practice, my learning, and then I have chance to meet more people in the world. I do believe that it takes so much time for me to learn and master one algorithm. I also certainly like to see people advance skills quickly, since they learn from my experience through my post or blog. I always like to be one of players, share and learn, learn and then share.

Here is the link.

Case study: hard level algorithm my post ranks top 7

Oct. 9, 2019

Introduction

It is the time for me to review my achievements. I did not get really big progress in terms of problem solving in 2019. I did get back into stock market, and put my 401 K and IRA back into stock market this April, and I went to onsite interview from Fortinet in May, and then prepared onsite for Amazon and Facebook in August, I had phone screen from Docusign in September. I learn slowly to adapt the challenge to advance myself. Today I like to talk about something new, my post ranks top 7 - a hard level algorithm.

Case study

I did not notice that I wrote a post, since I did not add it to my github repository Leetcode page six month ago.

Here is the image to show my ranking.

Here is the link.

How to write an excellent post?

I think that it is not difficult to write an excellent post. The algorithm I studied is so easy to understand, since I put together some comment to make it so straightforward.

And also I did spend time to save a graph from weekly contest lead board, and then wrote down my observation.

It is so important for me to learn how to document good learning process for other players.

Being a good mentor, helper, or player, I strive to document my practice, my learning, and then I have chance to meet more people in the world. I do believe that it takes so much time for me to learn and master one algorithm. I also certainly like to see people advance skills quickly. I always like to be one of players, share and learn, learn and then share.

Wednesday, December 6, 2017

Leetcode 393: UTF-8 Validation

Dec. 6, 2017

Introduction

The algorithm is to determine if the integer array has specified format with one to 4 byte data. I found out that best way to deal with nervousness is to read the problem statement again and again, more than four times. And then usually I understand the algorithm and bring back my confidence about bit manipulation problem solving. The problem statement is here.

Code review

It is time for me to review my practice of bit manipulation by looking up the blog using keyword: bit manipulation. The search result is here.

Review some basics from one of blogs.

Top coder - fun with bits, the article link is here.

Take some notes:
Use bits of an integer to represent a set. Not only does it produce an order-of-magnitude improvement in both speed and size, it can often simplify code at the same time.

Go over the most popular set manipulations in the following:

Set union
A | B

Set intersection
A & B

Set subtraction
A & ~B

Set negation
ALL_BITS ^ A

Set bit
A |= 1 << bit

Clear bit
A &= ~(1 << bit)

Test bit
(A & 1 << bit) != 0

Extracting every last bit

Counting out the bits

It is time for Julia to learn bit manipulation again. What Julia likes to do is to read the article word by word and then spend 10 - 20 minutes to go over the terms and warm up the idea how to solve the problem to use integer to represent a set.

It is not so often Julia uses this technique at work, but it is easy to review again and get the idea.

Follow up

Dec.16, 2017

I asked my mock interview partner to work on this algorithm together, and then we had some discussion. Here are the notes.

The input from the peer:

32 - Each integer has 32 bits

%256 - how to extract rightmost 8 bits?
/256 - move to next 8 bits
>>=8 - or right shift 8 bits

int = int[4] - one integer uses 4 integer

0****** < 128 - check the range
110**** >= 11000000 < 111000000
1110**** >= 11100000 < 11110000
11110*** >- 11110000 < 11111000
10****** >= 10000000 < 11000000

Julia's input:

- integer - bit mask
set 8 bit - use an integer to represent a set, each integer 8 bits express different numbers

Set bit
A |= 1 << bit

Clear bit
A &= ~(1 << bit)

Test bit
(A & 1 << bit) != 0

Extracting every last bit

Counting out the bits

Apply the bit technique to current case:

test case 1 : (arr[i] & 1 << 7) == 0 - 0xxxxxxx - figure out the leftmost bit is 0.

test case 2: arr[i] >> 5 ^ 6 = 0, judge 110xxxxx 10xxxxxx, there are four operations:
AND, OR, negative, XOR ->
The peer came out the idea to shift the first 8 bits to left 5 bits, and then XOR 110, it should be 0.

Reference:

Top coder article about bit manipulation. The link is here.

Editorial notes:

I worked with a peer with strong math and engineering background, the peer works hard; if I share some tips, the peer will come out the solution in less than 5 minutes.

Saturday, May 6, 2017

Max Score - RookieRank 3

May 6, 2017

Plan to work on the algorithm: Max Score in next 1 - 2 hours. Time is 5/6/2017, 12:53 pm.

Follow up

May 7, 2017 9:20am

C# code in the contest is here, scored 3.5 out of 35.

Follow up

Study the discussion about the solution, the link is here.

1. The following implementation uses memoization, backtracking, and backward processing:

C# practice code is here which passes all test cases.

2. Continue to work on my code submission, change the key of memoization, relax to the sum instead of the string concatenated by various array's element.
Score 14 out of 30, timeout test cases 7 - 10.
C# practice code is here.

3. Bit mask - pass all test cases
C# practice code is here.

Bit manipulation 4 things to review

1. Get integer 2ⁱ:
//use left shift i times,
bitToCheck = 1 << i

2. Check ith bit is 1:
// int bitmask
bitmask & bitToCheck

3. Get ith bit:
bitmask |= bitToCheck,

4. Unmask the ith bit:
// backtracking
bitmask &= ~bitToCheck

4. Bit mask - replace the integer using int[], size of array is 20.
May 11, 2017
Timeout on test cases from 6 to 10. Score 10.50 out of 30.
C# practice code is here.
string.Join(",", bitmask) takes too much time.

Julia learned the lesson. Take some time to write bit manipulation instead of using int[]. Bit manipulation expedites the process, use int instead of int[].

5. Continued to work on code written in the contest,
May 12, 2017 11:11 pm
C# practice code is here. Score 10.50, pass test case 0 - 5, and timeout on test case 6 - 10.

Learn when to do memorization, it should be out-of-for-loop, memo on the used HashSet<int>, actually encode all used indexes of the array to a string. Move the memoization from inside for-loop to outside for-loop.

Algorithm analysis

It is most important to come out the recurrence formula for the algorithm. Try to work backwards instead of starting from the first number and forward.

The maximum score of k problem can be solved by choosing any number as the last kth number, and then work on the maximum score of k - 1 problem. Use bitmask as key to do memoization.

Actionable Items

Review previous practice, and find some cases to use bitmask.

Top coder - fun with bits, the article link is here.

Take some notes:
Use bits of an integer to represent a set. Not only does it produce an order-of-magnitude improvement in both speed and size, it can often simplify code at the same time.

Go over the most popular set manipulations in the following:

Set union
A | B

Set intersection
A & B

Set subtraction
A & ~B

Set negation
ALL_BITS ^ A

Set bit
A |= 1 << bit

Clear bit
A &= ~(1 << bit)

Test bit
(A & 1 << bit) != 0

Extracting every last bit

Counting out the bits

2. Hackerearth.com dynamic programming and bit masking, article link is here.

Saturday, July 16, 2016

Reverse unsigned 32 bit integer - facebook code lab - 5th practice - C++, swap bits

July 16, 2016

First, study the solution provided by lab, great idea:

Reversing bits could be done by swapping the n/2 least significant bits with its most significant bits.

The trick is to implement a function called swapBits(i, j), which swaps the ‘i’th bit with the ‘j’th bit.

If you still remember how XOR operation works:

here

0 ^ 0 == 0, 
1 ^ 1 == 0, 
0 ^ 1 == 1, and 
1 ^ 0 == 1.

We only need to perform the swap when the ‘i’th bit and the ‘j’th bit are different.

To test if two bits are different, we could use the XOR operation. Then, we need to toggle both ‘i’th and ‘j’th bits.

We could apply the XOR operation again.

By XOR-ing the ‘i’th and ‘j’th bit with 1, both bits are toggled.

Bonus approach (The divide and conquer approach):

Remember how merge sort works? Let us use an example of n == 8 (one byte) to see how this works:


              01101001

             /        \

           0110       1001

          /   \       /   \

         01    10    10    01

        /\     /\    /\     /\

       0  1   1  0  1  0   0  1

The first step is to swap all odd and even bits. After that swap consecutive pairs of bits, and so on …

Therefore, only a total of log(n) operations are necessary.

study the code in C++:
https://gist.github.com/jianminchen/3526dd68e72ae97563cdd61580052016

Monday, June 27, 2016

A small research on HackerRank world sprint #4

June 27, 2016

On Sunday June 26, Julia spent 3 hours to do some research, evaluate where she is in the competition, and what kind of target she can set, how to reach the target next time. Actually she went through current leadboard, and study who are best players, top-performance programmers.

Statistics:
Time spent on HackeRank world sprint #4: 4+ hours on June 25, 2016
Score: 40, around 2276 rank in over 5000 people.

Target:
She needs to score another 50 - 100 in order to be competitive, where she found out that some Google, Facebook employee score' range (above 100, some above 140).

Top 16 - full score (420), there are a lot of world champions over there. So, the problems have some pattern, people can get trained to be good at them.

Here is the link of HackerRank world sprint #4.

https://www.hackerrank.com/contests/june-world-codesprint/challenges

She completed first two easy algorithms in first 2+ hours. Get 40 points.

Gamble the luck is not a good strategy. Set low target is also not a good strategy. 4 hours can be spent on more meaningful learning experience.

Why?
Julia spent most of time to work on one problem, AorB, try to score another 50 points. She enjoyed coding and found one problem after another, but it is time-consuming, not efficient approach.

In first hour, she needs to write down every small function she should solve first, and then, design well-defined small function to be helpers, understand possible test cases. Simple problems are easy to work on, save time.

Some problems were discovered after she worked on the problem almost 4+ hours. Julia, you have to learn to be a good thinker first, force yourself think hard on first 30 minutes. Write down things to consider in design of function.

1. What is the problem she found out after 3+ hours?
The solution has problem, Hexadecimal should be reversed first, then, first char is least significant bit, much easy to iterate, compare among A, B, C. Mistakes like A, B, C to compare different bit, not align properly.

2. What is the problem she found out after 4+ hours?
how to make A as small possible?
Provided with extra allowed bits, Give up 1 from A (1->0), by the order of most significant bit first, and then, set B's bit to 1 if need.

3. What is the problem she found after 8+ hours?
A|B = C, so C's length as string should be longest one. C's length = Math.Max(A.Length, B.Length). This helps the design and also testing.

From 12:00pm - 12:00am, she spent a lot of hours to play with code, until midnight, she gave up AorB, scored 0 with many hours passion/ learning experience/ lesson learned.

Lesson learned:
Passion does not work, good workout; but not practical.
Break the problem into 5 - 6 well defined small functions;
First 30 minutes, be a good thinkers. Find all possible problems, assertions, read problem statement again and again. (make sense? :-))

Write a few small functions to warmup, fully test with test cases. 2 - 3 hours.
For example, work on this small well-defined function first,
http://juliachencoding.blogspot.ca/2016/06/hexadecimal-or-calculation.html
https://gist.github.com/jianminchen/5442cb579b13ffc203ce89b3e54e8a36

And then, spend 1 hour to put together for solution AorB.

The best performer in the world (172minutes/7 algorithms), average less than 30 minutes/ algorithm.

Good about the practice:
Practice code on problem solving:
1. reverse a string in C# -> ToCharArray() -> IEnumerable first
2. check least significant bit using And 1 (bit manipulation)
3. check most significant bit using And 1 - define value array {8,4,2,1}
3B: leftshift >>1 in C# practice
4. Hexadecimal char <-> binary format string <-> integer value expression
5. int, long, bigInteger(?) cannot handle big number 10^5000, force me to work on string manipulation
6. Look into C# const keyword, how to separate variables - using existing variable, set new value, less code.
7. StringBuilder class needs System.Text package
8. break statement - be careful when the function is not well-defined small function, causing bugs.
9. A|B = C, what we can tell the length relationship among A, B, C.

Actionable items:

Choose 10 people's code to read.
Learn to be a good thinker - work on first 30 minutes, thinking, reading, define well-defined small functions.

Blog to read:
https://www.linkedin.com/pulse/why-best-designers-problem-solvers-katy-tsai?trk=hp-feed-article-title-like

I’ve tasted success and I’m hungry for more. I’ll prove I’ve got what it takes to win. #CreateYourMark pic.twitter.com/jansdjv9pG
— Lucas Pouille (@la_pouille) May 20, 2016

Saturday, March 12, 2016

HackerRank - strings - GemStones

March 12, 2016
GemStones:
Problem statement:
https://www.hackerrank.com/challenges/gem-stones

First practice:
Julia's C# solution:
https://gist.github.com/jianminchen/aa85318f91fbcdc8f74d

More practices:

Julia, you do not need to use jagged array to store all the string, you can use one array, and then, keep adding to the array the count.

So good to learn from other submission - Julia likes HackerRank, quickly get updated with more ideas/ implementation / more informed.

1. Improvement 1:
Here is other person's implementation - less space, beat your solution!
https://gist.github.com/jianminchen/cb0886705d99423a321f

So, Julia, write another one - short one -

not: int[][] countA = new int[len][];

int[] sumA = new int[26];

space improvement, code is much short.

Julia wrote second implementation using one dimension int[26] instead of int[len][]
https://gist.github.com/jianminchen/10ece1c63d85e6ae3e12

2. Improvement 2:
Here is one of solution using bit manipulation - Great idea - try to use it as well!
Java
https://gist.github.com/jianminchen/c3d56eedcb794b0fa496

Julia uses C# to implement the bit manipulation:
https://gist.github.com/jianminchen/aba5bad049353738a520

one comment on line 39:
int x = -1; // julia, debug the code, and learn the idea to use bit manipulation

why x = -1?
recall -1 is FFFF in bit expression; since 1+1 = 0, so
FFFF
1
---------
0000

3 solutions - space complexity using jagged array to one dimension array to one integer.

Nov. 30, 2016
Review stackexchange code review post:
http://codereview.stackexchange.com/questions/61248/diamond-in-the-rough-finding-gems-in-the-rocks

Saturday, February 27, 2016

HackerEarth: first algorithm practice - Milly Chocolate

Feb. 26, 2016

Spent more than 1 hour to work on an algorithm problem on HackerEarth.

Problem statement:
https://www.hackerearth.com/druva-sdet-hiring-challenge/algorithm/milly-and-chocolates-4/

Milly loves to eat chocolates. She buys only those food items which contain some amount or percentage of chocolate in it. She has purchased N such food items and now she is planning to make a new food item by her own. She will take equal proportions of all of these N food items and mix them. Now she is confused about the percentage of chocolate that this new food item will have. Since she is busy in eating the chocolates so you have to help her in this task.

Input

First line of the input will contain T (no. of test cases). Every test case will contain two lines. First line will contain N (no. of food items) and the second line will contain N space separated P_i values denoting the percentage of chocolate in i^th food item.

Output

For every test case, print the percentage of chocolate that will be present in the new food item.

Note : Your answer should be exactly up to 8 decimal places which means that if your answer is 2.357 then you have to print 2.35700000 or if your answer is 2.66666666 .... then you have to print 2.66666667

Constraints

1 <= T <= 5
1 <= N <= 5*10⁵
0 <= P_i <= 100

SAMPLE INPUT

1
3
80 30 90

SAMPLE OUTPUT

66.66666667

Time Limit: 1 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB

Marking Scheme: Marks are awarded if any testcase passes.

Allowed Languages: C, CPP, CLOJURE, CSHARP, GO, HASKELL, JAVA, JAVASCRIPT, JAVASCRIPT_NODE, LISP, OBJECTIVEC, PASCAL, PERL, PHP, PYTHON, RUBY, R, RUST, SCALA

Julia's practice:
1 second for each file, but, the time is over 1 second. Need to work on speed! (Julia likes the challenge! )

https://github.com/jianminchen/hackerEarth/blob/master/MillyandChocolates/MillyAndChocolate.cs

Julia read editorial of algorithm, and know the better solution:

https://www.hackerearth.com/problem/algorithm/milly-and-chocolates-4/editorial/
(will try her own version as well later. Definitely, the code will take less time to write! Good learning tool - Thanks, hackerEarth!)

So, to fix TLE error ( more than 1 second for each file), Julia wrote a bug free version:
https://github.com/jianminchen/hackerEarth/blob/master/MillyandChocolates/MillyAndChocolate_BugFix.cs

Read this web page:

https://www.hackerearth.com/@pranjuldb/activity/hackerearth/

Julia's hackerEarth profile:

https://www.hackerearth.com/@jianminchen.fl

Monday, February 8, 2016

Algorithm: Write a function to detect if the string has the unique character

February 8, 2016

So excited to have chance to write code for a new algorithm.

Write a function to detect if the string has the unique character.

Read the blog:

http://stackoverflow.com/questions/19484406/detecting-if-a-string-has-unique-characters-comparing-my-solution-to-cracking

this blog provides good answers for the question of unique character:

Notice that this method doesn't allocate an array of booleans. Instead, it opts for a clever trick. Since there are only 26 different characters possible and there are 32 bits in an int, the solution creates an int variable where each bit of the variable corresponds to one of the characters in the string. Instead of reading and writing an array, the solution reads and writes the bits of the number.

Julia's comment: first blog about bit manipulation - surprising, after the reading, it is much easy to understand the code:
Two bit operation:
1<< val
|=

It is always helpful to write a few of small function:

int toInt(char c)
{
return c-'a';
}

int OneShiftLeftNbits(int val)
{
return 1 << val;
}

int checkNthBit(int val)
{
// ...
}

public static boolean isUniqueChars(String str) {
    if (str.length() > 256) { // NOTE: Are you sure this isn't 26?
        return false;
    }
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0) return false;
        checker |= (1 << val);
    }
    return true;
}

http://javahungry.blogspot.com/2014/11/string-has-all-unique-characters-java-example.html

To be continued.

Sunday, February 7, 2016

Leetcode 318: Maximum Product of Word Length

February 7, 2016

There are a several of stages to go through on Leetcode 318 problem solving today.

10 minutes to read question and think about solution, confused about requirement(以为包括子字符串) ->
20 minutes to read blogs to understand solutions ->
10 minutes to know the detail to implement (1) ->
20 minutes to implement without bugs (2) ->
10 minutes to implement with more clear code with bugs (3) ->
10 minutes debug to read code again, debugging to pinpoint bug ->
60 minutes to work on a better idea - optimal idea (5) ->
work on exceeded time issues (20 minutes, instead of 60+ minutes) (6)

Action items:
1. Always work on coding, using Visual Studio. Try to improve coding.

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()

Julia's practice:

https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength.cs

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。

Here is julia's practice:
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_B.cs

Read the webpage about precedence and order of evaluation:
https://msdn.microsoft.com/en-us/library/2bxt6kc4.aspx

Solution 3:
Just for fun, write another version of bit manipulation implementation, but Julia created 3 bugs in the row before she writes a correct version.
Instead of using two words do not contain same char,
if ((s1 & s2) == 0) return true;

she tried to write a version to check any char from a to z, one by one check version:
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_C.cs

Design takes practice. She thought about and then wrote, and then failed 3 times!

Wednesday, January 20, 2016

Algorithm night (2): 10 questions to read

January 20, 2016

Plan to spend 2 hours (9pm - 12pm) to read 10 blogs about algorithms, each blog 10 minutes.

1. Leetcode: Coin Change
http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
Think about recursive function solution first, and then DP solution to remove redundant calculation

http://blog.csdn.net/kenden23/article/details/17636599
http://buttercola.blogspot.ca/2016/01/leetcode-coin-change.html

2. Leetcode: Maximum product of word lengths

https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/

http://buttercola.blogspot.ca/2016/01/leetcode-maximum-product-of-word-lengths.html

Brute force analysis, bit manipulation - encode string using integer, and then, optimize the algorithm - instead of two strings' comparison, using two integer bit manipulation - And operator - clever solution.

3. Leetcode questions: Power of 2 / Power of 3

http://www.cnblogs.com/grandyang/p/4623394.html
Power of 3
http://my.oschina.net/Tsybius2014/blog/601048

http://buttercola.blogspot.ca/2016/01/leetcode-power-of-three.html

4. Leetcode 325: Maximum size subarray sum to K (Level: easy)

https://asanchina.wordpress.com/2016/01/05/325-maximum-size-subarray-sum-equals-k/

http://buttercola.blogspot.ca/2016/01/leetcode-maximum-size-subarray-sum.html

January 21, 2016

5. BFS - algorithm
http://www.geeksforgeeks.org/find-number-of-islands/
Read the blog, understand the algorithm. Rate: 10

http://www.jiuzhang.com/solutions/find-the-connected-component-in-the-undirected-graph/

http://algobox.org/number-of-connected-components-in-an-undirected-graph/

http://buttercola.blogspot.ca/2016/01/leetcode-number-of-connected-components.html

6. Sparse Matrix Multiplication

http://www.cs.cmu.edu/~scandal/cacm/node9.html
https://leetcode.com/discuss/71912/easiest-java-solution

http://buttercola.blogspot.ca/2016/01/leetcode-sparse-matrix-multiplication.html

7. Leetcode 310: Minimum Height Trees