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.

Saturday, April 23, 2016

HackerRank: Even Tree (V) C# solution - use queue to help counting spanning tree's node

April 23, 2016

Problem statement:

https://www.hackerrank.com/challenges/even-tree

C# solutions to study:

Code to study:

written by an engineer in Microsoft
https://gist.github.com/jianminchen/5c6b6cb4de9c4a2faf6237b7ac331a41

Julia modified the C# code to use DFS, spanning tree's node count, but still got the run time error/ wrong answer.

https://gist.github.com/jianminchen/fe4da18247e4ad712c8e0bcb846983eb

Later, find out what is wrong. ( Probably, here is the reason:
The edge is directed.
Do not duplicate the edge.
For example, 2 1, just 2->1, do not add 1->2;
but
vertex[1].add(2),
vertex[2].add(1),
edge just add Tuple(2,1) )

Now, write exactly same code using study code, and see what I can learn.

The following code passes all the test cases.
https://gist.github.com/jianminchen/0e40bb76011e60f8aaf4683ed9c9c3d6

Julia's comment:

The edge is directed. Do not duplicate the edge and save two copy of the edge. But, vertex list is added for both vertexes of one edge.

Follow up - on April 24, 2016 8:40pm
Read Graph Toplogical Sorting:
http://www.geeksforgeeks.org/topological-sorting/

Follow up - on April 30, 2016 11:52pm
Read graph reprenstation
Use Adjacency Matrices
Use Adjacency Lists
https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

Notes from the blog:
How much space do adjacency lists take? We have $|V|$ lists, and although each list could have as many as $|V|-1$ vertices, in total the adjacency lists for an undirected graph contain $2|E|$ elements. Why $2|E|$ ? Each edge $(i,j)$ appears exactly twice in the adjacency lists, once in $i$ 's list and once in $j$ 's list, and there are $|E|$ edges. For a directed graph, the adjacency lists contain a total of $|E|$ elements, one element per directed edge.

HackerRank: Even Tree - C# solutions to study (III)

April 23, 2016

Problem statement:

https://www.hackerrank.com/challenges/even-tree

C# solutions to study:

https://www.hackerrank.com/challenges/even-tree/leaderboard/filter/language=csharp

https://gist.github.com/jianminchen/1858f0b4994efc65c99701290fb951ec

2. written by an engineer in Microsoft
https://gist.github.com/jianminchen/5c6b6cb4de9c4a2faf6237b7ac331a41

3.
https://gist.github.com/jianminchen/3722227eb8c3df4085c10e34779763bf

4. By an engineer in Amazon

https://gist.github.com/jianminchen/8359a5d4f2567db387c0dd80a0f70513

Julia, practice the above 4 solutions. Write it by yourself one by one, and count the time. Work on speed.

HackerRank: Even Tree - Graph Problem (II) - Coding first try

April 23, 2016

Problem statement:

https://www.hackerrank.com/challenges/even-tree

Time spent:
over 1 hour,

score 10 out of 50

pass two basic cases, but with run time error after submission on other test cases

https://gist.github.com/jianminchen/455978d2fd4b1ebafb3a5aa7d4761fed

HackerRank: Even Tree - Graph Problem (I) - Just thinking

April 23, 2016

Problem statement:

https://www.hackerrank.com/challenges/even-tree

Motivation to work on graph problem:
1. There are over 10,000 submission on this problem, definitely, Julia likes to give it a try.

Statistics:
1:20 - 2:30pm more than 1 hour wild thinking.

Think about the graph problem, before Julia writes any code, she think about how the problem is developed:

1. Have to remove as many edges from the tree as possible; <- kind of greedy algorithm
2. Each connected component of the forest should contain an even number of vertices.
<- Otherwise, odd number, 1 node itself, cannot be called forest; at least, 3.
3. Think about the how to remove one edge:
both ends should be ok; if one end only has one edge, then, no for removing the edge.
so, the node checks its edge count:
= 0 <- not possible - > "even number of vertices"
= 1 <- impossible
= 2 <- possible, can keep one, remove one

But think about forest with even number 2, 4,
for number 2, only one case: 3 connects to 4 in the test case
for number 4, only one case: one node in the center, all other 3 are connected to the same one.
for number 6, only one case: one node in the center, all other 5 are connected to the same one;
otherwise, one node connects to other 4 nodes, the 6th one will connect to the one of the node (other 4 nodes), then, it can be break into 2 and 4.

So, it should be two checking:
1. if the node only has one edge, keep it; do nothing;
2. if the node has more than one edge, remove all edges with more than 1 count.

Add comment on 10:00pm on April 23, 2016
1. Julia, you took distributed system in Florida Atlantic University around 2001, talking about spanning tree, ad hoc routing protocol; one thing is about spanning tree. Use DFS, and then, discuss spanning tree; if the root node's child has a tree with even length, then, edge can be removed.

Friday, April 22, 2016

Find if a Directed Acyclic Graph has a cycle.

April 22, 2016

Find if a Directed Acyclic Graph has a cycle. Use DFS with coloring to find if cycle exists.

Given a directed graph of 10 cities, each of which may or may not be connected to each other, represented by an adjacency list, write an algorithm to find if there is a write from a city that eventually cycles back to the same city. What is the time complexity of your algorithm? You may use reasonable extra storage, or modify the structure of the graph node class.

Question and Answers:

Julia, read a few blogs, and then quickly go over first time. 30 minutes:
1. https://www.quora.com/How-can-DFS-and-BFS-be-used-to-find-out-if-there-are-cycles-in-a-graph

2. http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
Take notes here:
Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS.

In other words, Julia, using DFS, to detect the cycle;

DFS for a connected graph produces a tree; So, from graph -> DFS -> Tree;

Then, work on Tree, to see if there is a back edge present in the tree;

What is back edge? How to track? ancestor node in a stack - using array.

Question and Answer:

Walk through the code, and add the comment:

https://gist.github.com/jianminchen/2eea7cc7cca69f296fc105c3fc3faafa

Read another blog:
http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

Read another blog from HackerRank:
https://www.hackerrank.com/topics/topological-sorting

Actionable item:

Work on HackerRank graph problem today:
https://www.hackerrank.com/challenges/even-tree

And then, study as many as possible solution about this graph problem. Get ideas how people are talented on graph problem solving.

Find the lowest common ancestor of two nodes in a Binary Tree.

April 22, 2016

Find the lowest common ancestor of two nodes in a Binary Tree. The tree does not have a parent pointer. Your algorithm should run in linear time, without any extra space.

Bottom-up approach.

http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

HackerRank problem:

https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor

https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/

Review blog:
http://juliachencoding.blogspot.ca/2015/07/leetcode-lowest-common-ancestor-in.html

Tortoise-hare algorithm

April 22, 2016

Find if a linked list has a cycle. Expectation O(n) time; O(1) space.

http://codingfreak.blogspot.com/2012/09/detecting-loop-in-singly-linked-list_22.html

https://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work

Fisher-Yates algorithm

April 22, 2016

A deck of cards is represented by an integer array of size 52, with possible value of 1 - 13 for each position. Design an algorithm to shuffle the deck of cards in linear time, in-place.

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

April 26, 2016
http://www.geeksforgeeks.org/shuffle-a-given-array/

“shuffle a deck of cards” or “randomize a given array”

Question and answer:

1. Understand the naive approach, extra space - an array, and also time O(n^2).

2. Came cross this blog <- So, use Fisher-Yates algorithm

大概就是取一个array里的任意n个不同的值,得到一个随机的组合，不能取同一个index的数，但是可以取数值相同的不同index的数

给一个array：[5,1,3,3],
再给一个数字n：2，
求这个array里的任意num个数：比如可以得到[5,1] or [5,3] or [1,3] or [3,3] ，但是不能得到[5,5]

再比如[5,1,3,3], 1 ===> [5] or [1] or [3]

就是先判断如果n>array.length或者n<=0或者array是空,返回一个空array
否则就是一个loop，每一次生成一个random的index数字，还用了一个hashset来存之前访问过的index，如果生成的random index之前已经get了，就再继续生成一个random index。
loop n次，每次取到的值放进新的结果array里。
然后说了说也可以用一个boolean array存每个值有没有已经取到。。
写完后再写了写unit test什么的，还有问道怎么检测得到的结果比如[5,1]确实是[5,1,3,3]里的
Julia's comment:
3 issues:
1. In place - no extra array
2. Hashset is also extra memory
3. Work on array index - random number selection using % operator, not on value in the array.

3. Let us walk through the code and then add comments - make it fun memory:

// A function to generate a random permutation of arr[]

void randomize ( int arr[], int n )  

{

    // Use a different seed value so that we don't get same

    // result each time we run this program

    srand ( time(NULL) );    // Julia, Good to know, C++, look up srand API

    // Start from the last element and swap one by one. We don't

    // need to run for the first element that's why i > 0

    for (int i = n-1; i > 0; i--)

{

        // Pick a random index from 0 to i

        int j = rand() % (i+1);  // Julia: random number -> Range (0, i) using module 

        // Swap arr[i] with the element at random index

        swap(&arr[i], &arr[j]);  // swap two nodes 

}

}

Read C++ API:

http://www.cplusplus.com/reference/cstdlib/srand/

http://www.cplusplus.com/reference/cstdlib/rand/