C# string class - API study

August 28, 2016

Previous blog about string class study for C#, Java, JavaScript, C++:

http://juliachencoding.blogspot.ca/2016/07/c-c-javascript-java-string.html

Go over all APIs in string class - C# programming language:

https://msdn.microsoft.com/en-us/library/system.string_methods(v=vs.110).aspx

40 APIs - Go over it 30 minutes a time - start to memorize them: function signature etc.

Clone
Compare
CompareTo
Concat
Contains
Copy
CopyTo
EndsWith
Equals
Format

GetEnumerator
GetHashCode
GetType
GetTypeCode
IndexOf -        (8 overloaded version)
IndexOfAny    (3 overloaded version)
Insert
Intern
IsInterned
IsInterned

IsNormalized
IsNullOrWhiteSpace
Join (5 overload)
LastIndexOf (8 overloaded version)
Normalize
PadLeft
PadRight
Remove
Replace
Split (6 overloaded version)

StartsWith (3 version)
Substring
ToCharArray
ToLower
ToLowerInvariant
ToString
ToUpper
ToUpperInvariant
Trim
TrimEnd

TrimStart

HackerRank: string algorithm - Reverse Shuffle Merge - Stack, backtracking techniques

May 26, 2016

Reverse Shuffle Merge - Problem statement:

https://www.hackerrank.com/challenges/reverse-shuffle-merge

Algorithm analysis:

Use test case: "abcacb" to explain the solution: 

int[] add = new int[26], 

int[] skip = new int[26]

a - 0, b - 1, c -2 

add[0] = 1, add[1] = 1, add[2] = 1, 

skip[0] = 1, skip[1] = 1, skip[1] =1, 

Find smallest lexical string. 

reverse input char one by one:

push b into stack, 

'c' > ''b', then, push c into stack

stack:

c

b

Now, a is scanned, 'a' < stack.peek() = 'c', skip[2] = 1 > 0, 

backtracking, pop c out of stack, skip[2] = 0

Now, 'a' < stack.peek() = 'b', skip[1] = 1 > 0, 

backtracking, pop b out of stack, then adjust skip[1] = 0

add[0] >  0, push a into stack, add[0] = 0, 

next, c is scanned, cannot skip, push into stack, 

next, b is scanned, cannot skip, push into stack, 

next, a is scanned, skip a. 

stack.ToArray(), keep stack iterator order, "bca", 

Array.Reverse(stack.ToArray()) -> "acb"

Lexical smallest string. 

previous blog: 

http://juliachencoding.blogspot.ca/2016/04/april-3-2016-httpsgist.html

warmup practice:

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

Second practice:

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

so many bugs in second practice:

1. confused on skip, add array --, ++; line 71, line 80 did the opposite.

2. string reverse, char[], string, Array.Reverse etc. lookup

3. add one more test case: "abcacb",

    b in stack, c in stack, then, run into a, pop up c, and pop up b, let 'a' in the stack. Two in row pop up in stack. While loop is tested on line 64 - 67.

4. while statement from line 64 - 67, fix compile error.

   both are ok to compile:

(char)stack.Peek() > runner)

(char)stack.Peek() - runner > 0)

Third practice:
The code passes HackerRank online test cases as well.

A few good changes:
1. add comment from line 67 - line 72, test case: "abcacb", 
use test case, stack top -'c' is removed, help to ensure the code is correct.
2. line 73, avoid bug to overwrite the variable runner, create a new variable called backTracked.

https://gist.github.com/jianminchen/8e2c28262dd3d13c4db856feaed5603e

Fourth practice:

1. create a new function getIndex - on line 100 - 103
2. after reading through the code, still missed a bug in writing - on line 55; debug the code and find
the result of first test case "abcacb" should be "acb", but it was "bca".

Julia examined line by line, but still missed the bug on line 55.

https://gist.github.com/jianminchen/7572e92ea48211d3d05c557d97601dbf

Read C# string constructor char[]: spend 10 - 20 minutes to read all constructors of string in C#.
https://msdn.microsoft.com/en-us/library/aa331865(v=vs.71).aspx

HackerRank: String Calculate function (III) - LCP array

April 13, 2016

Still work on the problem:

Problem statement:

https://www.hackerrank.com/challenges/string-function-calcula


Put together 2-3 hours on LCP array study first, and then, work out a solution for this advanced algorithm.


The LCP-LR array helps improve this to O(m+logN)O(m+logN), in the following way


LCP array reading
https://www.hackerrank.com/challenges/pseudo-isomorphic-substrings/topics/lcp-array

https://en.wikipedia.org/wiki/LCP_array

Question and Answer:

Before you write LCP implementation, tell me what you learn about LCP, give me an example you work on? 

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: string algorithm - Anagram

March 13, 2016

Anagram

Julia's C# implementation:
https://gist.github.com/jianminchen/f3c48ed9f3b16e8c5928

Julia made a few tries before she noticed that she needs to figure out the formula:

for (int i = 0; i < SIZE; i++)

            {

                if (sumA[i] > 0)

                    // add count of chars in array sumA but not in sumB

                    // axxbbbxx, 

                    // axxb -> bbxx, change a to b, that is it!

                    // axxb  a 1, b 1, x 2

                    // bbxx, a 0, b 2, x 2

                    // formula -> 

                    count += (sumA[i] >= sumB[i]) ? (sumA[i] - sumB[i]) : 0;   

            }

Another approach is to add all the differences, and then, divided by 2

C# submission code to study:

1. String class contains, Split functions etc. 
Split function - return array length to get the count of any char in the string. 
https://gist.github.com/jianminchen/adbfc2d809fb5b2bac78

2. add all the difference between two strings, and then divide it by 2
https://gist.github.com/jianminchen/7bbe86bbb83787d6b98b

3. Using Dictionary, KeyValuePair class
https://gist.github.com/jianminchen/78346475b6a7ce5d1681

4. Read more Lambda expression code in C#
https://gist.github.com/jianminchen/9d121bd95266db41dfa8

5. using StringBuilder, C# code
https://gist.github.com/jianminchen/d972656068fa8088ae70

6. use string.Remove function
https://gist.github.com/jianminchen/65687cefd2b107ec5e23


Java Code:
1. https://gist.github.com/jianminchen/794ffee7726df6062a1f

2. Maybe not smart idea, but it works - declare a string
String alph = "abcdefghijklmnopqrstuvwxyz";

https://gist.github.com/jianminchen/0cfa60bac880f2bba10f

Julia likes to read code, any language in submission. She could 
not stop reading, she has read more than 50 solutions, totally opened to so many creative ideas. 

HackerRank: string algorithm - Make it anagram

March 13, 2016


Make it anagram

Julia's practice:
C# language

https://gist.github.com/jianminchen/050b64f483c9a251d472

Read other's submission:

1. C#, using Dictionary, HashSet - Speically helpful, when you are not sure what Latin chars are. You just declare in general Dictionary, HashSet.

https://gist.github.com/jianminchen/5c6f6a70a1be4f71a98a

2. C#, using List class, remove method:

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

3. C#, kind of functional programming, new style to Julia - like JavaScript programming style

https://gist.github.com/jianminchen/2909916d9435f69c036b

4. using one array, first string each char - add to the array, second string each char - take away from the array, sum of abs value of each item.
https://gist.github.com/jianminchen/fbf8e9049d3a1539ee87

5. Using IList interface, distinct method, and functional programming - Lambda Expression <- Julia, you should try this code by yourself. It should be quickly picked up.

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

read this webpage to refresh Lambda expression:
https://msdn.microsoft.com/en-CA/library/bb397687.aspx

6. Sort two strings first, and then, using two pointers - sliding forward

https://gist.github.com/jianminchen/41e6cbd30228e9ba7204

7. using string operation, remove a char from a string - for any char in both two strings
https://gist.github.com/jianminchen/0138e2425592638dcf7a

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

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

Algorithm: Count the number of palindromes in a string

Count the number of palindromes in  a string

January 28, 2016

    Write down ideas:
    1. First of all, do not count duplicate.
    2. Brute force solution:
 any substring of O(N^2) substrings to see if it is a palindrome;
 Add the substring of palindrome to a hashset if it is not in the hashset.
  And return the length of hashset
    3. Use recursive solution - using subproblem to solve. Cannot filter out duplicate - not good
    4. Better solution - use center point of string - 2n + 1, and then, go over each one, add all palindromes substring.

  Requirement: write a C# code in 10 minutes for the solution, using brute force one.

  https://github.com/jianminchen/AlgorithmsPractice/blob/master/NumberOfDistinctPalindromes.cs

String functions review

August 23, 2015

1. stringDemo.cpp

Including

atoi 5 versions of implementation

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

2. Scramble string:

https://github.com/jianminchen/scramble-string

3. strstr

Boyer-Moore algorithm

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

Read the string function website and get ideas:

http://www-igm.univ-mlv.fr/~lecroq/string/

http://algs4.cs.princeton.edu/53substring/

http://zjalgorithm.blogspot.ca/2014/12/leetcode-in-java-implement-strstr.html

Need a test case to help me figure out Boyer-Moore algorithm again on August 23, 2015.
Here is a short one for me to memorize the idea:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/boyerMoore.htm

read the article quickly in 20 minutes on August 23, 2015
http://web.cs.ucdavis.edu/~gusfield/cs224f11/bnotes.pdf

Dec. 12, 2015 video watch:
https://www.youtube.com/watch?v=fHNmRkzxHWs
one of examples the presenter gave in his Cpp conference video.
Know that there is a definitely better algorithm than O(n^2), but also, need to know what the ideas are to beat the naive solution. 

Dec. 11, 2015
Need to work on a small test case, therefore, the algorithm can be easily recalled, and ideas of algorithms can be demoed clearly in the example. Go to find my favorite string, substring. (January 5, 2015, read the wiki page, https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm, read 'The bad character rule' and 'The good suffix rule' )

4. longest palindromic string

5. Look up standard string function implementation, quick review and learn:

January 5, 2016
Read the Java code on the following website:
http://algs4.cs.princeton.edu/53substring/BoyerMoore.java.html

Write a C# version, and check in github, and see if it will help to memorize the algorithm. 

Read the webpage: (well written! now Julia knows two rules: bad character rule, the good suffix rule)
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

http://www.cs.tufts.edu/comp/150GEN/classpages/BoyerMoore.html

Leetcode: string function atoi

June 18, 2015

Figure out how people are smart to get organized. The following blog is well organized.

http://pisxw.com/tag/#blog

atoi function blog:

http://blog.csdn.net/ljiabin/article/details/40508889

http://blog.csdn.net/ithomer/article/details/8800530

http://blog.csdn.net/column/details/leetcode-solutions.html

interesting stuff:

http://hihocoder.com/services/campus-recruitment

Share C# practice:

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

Leetcode 5: longest palindromic substring

Problem statement:

Given a string S, find the longest palindromic substring in S.

June 15, 2015

Websites to read:

http://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/

https://yanbxice.wordpress.com/2015/05/31/leetcode-longest-palindromic-substring/

题目分析很透彻, 很有帮助! 

https://leetcodenotes.wordpress.com/tag/palindrome/

C# code on github:

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

https://github.com/jianminchen/Leetcode_C-/blob/master/5LongestPalindromicSubstring.cs
https://github.com/jianminchen/Leetcode_C-/blob/master/5LongestPalindromic_B.cs

January 2, 2016

Review the algorithm. 

Leetcode question: 5. Longest Palindromic Substring

https://github.com/jianminchen/Leetcode_C-/blob/master/5LongestPalindromicSubstring.cs

January 13, 2016

Read the blog: 

http://blog.csdn.net/linhuanmars/article/details/20888595
http://blog.csdn.net/linhuanmars/article/details/22777711

Please read 5-6 solution about this leetcode question, and then, collect all the wisdom. Try to have nice memory about the solution, some fun experience; therefore, it will be a quick and fun time to solve the similar problems in the future.

Do not rush to finish more leetcode questions. Try to focus on simple problems.

There are 5 solutions discussed in the following blog, most important is to give overview of 5 analysis, what is brute force solution - time, space complexity.

One way to make review more fun is to read more than 10 - 20 solutions, and know all the ideas out there, and then, write some code; Reading is most important to help understand algorithms, through a simple problem, common interview question.

http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-i.html

4 solutions in the above blog

one optimal solution - linear time solution in the following blog:
http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

This blog is in Chinese. Excellent! Try to summary a few tips to come out linear time optimal solution! Do something to get more involved.

http://www.felix021.com/blog/read.php?2040

spent 10 minutes to read the article,
https://www.akalin.com/longest-palindrome-linear-time

Read the blog:
http://www.acmerblog.com/leetcode-longest-palindromic-substring-5356.html

6th solution, a suffix tree solution:
http://www.allisons.org/ll/AlgDS/Tree/Suffix/

January 7, 2017
3 code reviews:
Longest palindrome string - best review - no raw loop.