HackerRank - count string (V) - C plus plus solution

April 9, 2016

Spend one hour (4:00pm - 5pm) on this C++ solution, talk about the code and implementation:

C++ solution


Julia needs to figure out the design:

For test case:
1
((ab)|(ab)) 2

The design is to construct a graph, NFA, and then, convert it to DFA, and the count how many ways.

It is hard to teach yourself through HackerRank a solution; so, Julia likes to catch up by some reading. Searching the web ...

Read some blogs to get some help:

1. Not very useful


2. Try to read it in 10 minutes

ucsd.edu lecture notes - homework solution

3. Another reading:  

30 minutes reading - excellent content! 

Julia learns better after she invested 8 hours to try to understand a problem, by playing with hackerRank. 

princeton.edu lecture notes - regular expressions


Julia, try to memorize content on the above slides.

Learn quickly from lecture notes, a diagram for NFA:
((ab)|(ba)) 2

HackerRank: count string (IV) - JavaScript

April 9, 2016

 Spend some time later to go over this JavaScript solution, score 80 out of 80.

https://gist.github.com/jianminchen/4d5d2f77d0e23e424a0953aaf4e4276e

HackerRank - String algorithm - Count Strings (I)

April 9, 2016

Problem statement


Category: Difficult problem

Spend 25 minutes to think about problem, and then will get into other people's submission, and see what should be learned.

10:30 am - 10:55 am

Spent 25 minutes to think about the problem.

Try to express the expression using binary tree, like 1 + 2 * 3 problem using a tree.

So, ab can be express as a tree:

operator .
/       \
a       b


 a|b
operator |
/           \
a            b

a*
put * as parent node, and a is left child of operator node *

(a*)5
put 5 as the parent node of operator *

Structure the input as tree structure, and then, define different class - concatOp, orOp, starOp

Read the expression from left to right, and then, put it into data structure like a stack, and then, parse it, store it in the binary tree.

April 10, 2016 2:32 pm 

This is a graph problem, and also, the NFA, DFA problem. Julia, you are lucky to review the problem. Spend some time in the short future to go over code, give yourself a graph coding experience.

Breadth first search algorithm - calculate steps from room to guard using matrix

March 31, 2015 

Question is from careercup:

http://www.careercup.com/question?id=4716965625069568

Given a 2-D matrix represents the room, obstacle and guard like the following (0 is room, B->obstacle, G-> Guard): 
0 0 0 
B G G 
B 0 0 

calculate the steps from a room to nearest Guard and set the matrix, like this 
2 1 1 
B G G 
B 1 1 
Write the algorithm, with optimal solution.

题目：有一个二维矩阵表示的迷宫，其中G表示保安人员，B表示不可穿越的墙，其他位置均为空地。如果每次可以向东南西北四个方向移动一格，请计算出每个空格离最近的保安有多远。题目给出了一个示例。

解法：既然矩阵里可能有多个保安，我的思路是以各个保安为中心，进行广度优先搜索，搜索的过程中随时更新每个空格位置的最短距离，保证全部搜索完之后所有的结果都是最小的。单次BFS的时间代价是O(n^2)级别的。

Read the blog, and understand the solution; and then, implement it using C#

http://www.cnblogs.com/zhuli19901106/p/3710623.html

Try to implement the algorithm, so excited to practice a question used by Google interview. 体验Google面试题. 

Share code written in C# language:

https://github.com/jianminchen/BFS_RoomToGuard/blob/master/Program.cs