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 divide and conquer. Show all posts

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

Wednesday, January 6, 2016

Divide and Conquer: Preorder traversal of ternary tree

January 6, 2016

重温一道关于树遍历的题目, 在新年开始的第一个星期, 鼓励自己, 加油! 多写代码, 多练习.

Be humble, learn from her mistakes in 2015. Julia is learning how to solve "divide and conquer" - write a perfect recursive function - without bug in base case - recursive calls.

Her lessons for recursive function design, divide and conquer solution in 2014, 2015:

1. Do the work for root node, but do not do the work for its children; In other words, a subproblem can be handled by a recursive call.

2. Do not repeat base case 'if' clause - a checking afterwards in the recursive function call. Not necessary, except trying to use less stack.

Julia, recursive function design is like dealing with a family - single parent with children; show the work how to handle root node, that is almost done. Let recursive function to take care of children, do not do the work for children nodes. For example, binary tree, 2 children, call recursive function twice; Ternary tree, 3 children, and then, use 3 recursive calls.

Once again, "Do not do the work for children directly".

Action items:
1. Work on Leetcode questions again and start with simple questions.

Binary Tree Preorder traversal of ternary tree