Code review: Hackerrank - count string

March 26, 2017

 Introduction 

Julia checked the blog stats and then she found out that last week there are over 70 60 views of the blog about Hackerrank: count string. So, she reviewed the 5 blogs related to the study of the algorithm, she quickly reformatted the blogs, and also plans to review the algorithm, and then post a question for code review.

Julia likes to learn something from Google, data driven. So, she makes decision what to review by blogger stats. She reviewed all five blogs related to count string algorithm quickly today, but she needs to reserve some time for a good review on algorithm itself.

Julia wrote 5 blogs in April 2016, this is the first blog. Julia failed to fix the issue to find those 5 blogs using search feature of blog, she worked on labels of those five blogs, somehow, it does not work.

Code review

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

April 9, 2016

 Problem statement

 Solution to study:

Julia's C# practice with bugs


 The code has time out issue, wrong answer, and it only scores 3 out of 80.

code source:

https://www.hackerrank.com/casaro

Statistics:

Time spent:  1:00pm - 3:00pm
Go through test cases

C# code to study, also show C# source code here.



April 10, 2016

Action items:

Need to think about in computer theory, NFA, DFA, and argue that the above solution in theory has flaws.

Follow up after 12 months

Julia checked the blog statistics, and the blog has a lot of views recently. So, she reformatted the blog style and she will review the algorithm very soon, and also post a question on code review.

HackerRank: Count strings (II)

April 9, 2016

Julia likes to have some adventure and just get into other people's solution, and quickly learn something in next 20 - 30 minutes.

Problem statement:


Statistics: time spent:  11:22am - 1:00pm

Here is the solution from a programmer working in Apple:

Code to study by Apple engineer


Comments after reading:

1. This problem is about DFA, NDFA, those content learning in Formal Language, how to build a compiler.

Friendly remind - great time to study formal language, first time for computer science master degree, score C in the course, and then in 2001 to prepare Ph.D. qualification example, Julia spent a lot of time to read the textbook again.
 

2. The string parsing is more complicate, '(', ')' should be treated as operator, and then, you can build up something.

3. Read the wiki webpage to quickly refresh knowledge
https://en.wikipedia.org/wiki/Deterministic_finite_automaton

4. Play with Visual studio and also the code - debug and run through the test case 20-30 minutes:
(ab)|(ba)  2
((a|b)*)  5

5. And put some diagram on the paper, take picture, post here and see if you can draw the state diagram for this machine.  ( 20 - 30 minutes)

Julia likes to read the code, and also debug the code;

Some facts:

1. she learned Formal language in 2001 to prepare Ph.D. qualification exam, but she never did spend time to work on an concrete example, debug the code to see how it is designed.

2. the code is well designed, and also beautiful code to read;

It is hard to figure out how to construct the Ndfa, but reading the code, Julia, you should figure out the design:

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.