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.

Thursday, March 31, 2016

HackerRank: string algorithm - Reverse Shuffle Merge (I) - First step: Failed twice

March 31, 2016

Problem statement is here.

Introduction

The algorithm is in advanced category. 8:17 am - 10:08 am. Document 2 hours work as a hacker, Julia. First time, Julia thinks that hacker is a good name!

Practice Talk

Start from 8:19 am, 9:18, tried twice, passed one test case, failed others with wrong answer; then, need to pay attention to reverse string word.

Spent more than 20 minutes to think, but could not figure out the solution. Have to stop here. Write down the analysis first. Come back later.

The naive solution is to count string in each char in "abc...z", and then, half of count will construct a new string.

For example, if the string counting: a2b2c2
then, the string A is one of strings {abc, bac, cba, bac, aca, cab}

Of course, "abc" is the smallest one in lexicographical order, but the possible string formats:
abc***
*abc**
**abc*
***abc

Or, go through each possible string - find the minimum one, smart way to compare with previous one, keep the smallest one.

Assuming that the string is matching.

Got the idea. Linear solution. From 8:19 am - 8:45 am, more than 20 minutes to come out the idea.

9:00 am -
Two functions - one function is to count the number to determine that count for each char is even. Another step is to go over the string, take substring(i, 3).

20 minutes to write a code, a bug to fix: wrong answer
Need to make sure that substring count matching count first, otherwise, skip it!

9:15 am, bug is not fixed; and then, notice that the string has to be reversed!

10:16 am, still not fixed. Julia, this is a greedy algorithm, why is the greedy part? You missed merge part in the construction merge(reverse(A), shuffle(A)). So, you have to redesign the algorithm.

Conclusion

1. Design algorithm - advanced - know why it is advanced, examine the idea and see if you can make it first; Otherwise, waste time to write code

Two hours, failed two tries! A new hacker is getting her valuable lesson using 2 hours.

Here is the C# code.

Follow up

Blog review on May 3, 2017

Wednesday, March 30, 2016

HackerRank: String algorithm - Palindrome index

March 30, 2016

HackerRank, Easy questions, 1 hours 3 questions. More practice, please! Get some momentum!

Things are looking for:
1. Tips to cut time to write code;
2. Make the problem a simple problem - read the hint !
3. Avoid writing too many lines code in less than 10 minutes.
4. More tips !!!

Problem statement:
https://www.hackerrank.com/challenges/palindrome-index

Julia worked on this solution in 15 minutes, but she only scored 23 out of 25. She tried to figure out how to score 25. She missed the statement: "There will always be a valid solution."

Her C# solution (Time out last test case): Time complexity O(N^2), N is the length of string

Julia's practice using C#, solution is here.

So, Julia goes over those two cases in 25 minutes. It takes time to find great ideas:

Solution 2:

use recursive function, while loop. Time complexity is O(N).

Solution 2

Solution 3:

use iterative solution, once a possible index is found, stop. You do not need to verify that the string is palindrome. Assuming that there is a valid solution. Time complexity is O(N).

solution 3

Solution 4:

solution 4

Follow up after 12 months

April 26, 2017

Sunday, March 27, 2016

Video watching: a guide to object-oriented practice

March 27, 2016

Spent 2 hours to watch the video:

https://mva.microsoft.com/en-us/training-courses/a-guide-to-objectoriented-practices-14329?l=PLMOEi2hB_904668937

Take some notes, and also write down tips helpful.

Look up those terms:

internal
readonly
expression-bodied member
SRP - Single Responsibility Principle
S.O.L.I.D. - OO principles

Read some blogs:
http://stackoverflow.com/questions/28411335/expression-bodied-function-members-efficiency-and-performance-in-c-sharp-6-0

http://yqcmmd.com/2014/06/12/%E6%95%B0%E4%BD%8Ddp%E4%B8%93%E9%A2%98/

HackerRank: Sherlock And Anagram (VI)

March 27, 2016

Julia was surprised to have a workout on this moderate difficult string problem from 9:00am - 4:00pm. She did some code study, and then, read so many codes from Microsoft, box, and saleforce, Amazon, and then, she read linkin profile, and blogs. She is getting connected to all other programmers in the world. HackerRank is young, all the coders are in charge of business this world, right now! No complaint.

Just learn one good code a time. Pay attention to some details. Follow up with a revisit once a while. Julia, you will make your programmer life easy, just relax, and see how people are creative to solve problems. You should do so, just copy the idea. Make sure that think by yourself first, do not be a copycat.

This code is her favorite. She is still learning, never use SortedDictionary before,

code reference:
https://www.hackerrank.com/Relentless

http://anothercasualcoder.blogspot.ca/#!

Julia is too busy to work on coding, so she chooses on easy to moderate questions. She waited until 7 - 10 string questions, and then, finally, she worked on her first moderate question on HackerRank after 1 - 2 months. But, she likes to read other people's code, and then, she just needs ideas to solve problems.

Here is the code gist:

https://gist.github.com/jianminchen/22f8e0de115cf656995e

/*
Julia likes to talk about design of the function, through debugging, she knows a few things:

For string "abba",
First, go over string with length 1,
then, SortedDictionary - key 'a', 'b', values are 2, 2
then, Hashtable htPairs - key: a2, value:

then, go over string with length 2,
then, SortedDictionary - key 'a', value 1; key 'b', value '1'

"abba" go through a loop, to get substring with length 2, in the order:
^ ->
|
"ab",
"bb",
"ba"
1. string "ab", , key "a1b1", htPairs["a1b1"] = 1
2. string "bb", key "b2", htPairs["b2"] = 1
3. string "ba", hashTable contains the key, so the value htPairs["a1b1] = 2
Hashtable key "a1b1", sortedDictionary, value 2

*/
static BigInteger UnorderedAnagrams(string str)
{
Hashtable htPairs = new Hashtable();

for (int len = 1; len <= str.Length; len++)
{
for (int i = 0; i + len <= str.Length; i++)
{
SortedDictionary<char, int> anagram = new SortedDictionary<char, int>();
for (int j = i; j < i + len; j++)
{
if (anagram.ContainsKey(str[j]))
{
anagram[str[j]] = (int)anagram[str[j]] + 1;
}
else
{
anagram.Add(str[j], 1);
}
}

string finalKey = "";
foreach (char key in anagram.Keys)
{
finalKey += key.ToString() + ((int)anagram[key]).ToString();
}

if (!htPairs.ContainsKey(finalKey))
{
htPairs.Add(finalKey, 1);
}
else
{
htPairs[finalKey] = (int)htPairs[finalKey] + 1;
}
}
}

BigInteger finalResult = 0;
foreach (string k in htPairs.Keys)
{
finalResult += Combinatorial((int)htPairs[k], 2);
}

return finalResult;
}
Blogs:
http://juliachencoding.blogspot.ca/2016/03/hackerrank-string-sherlock-and-anagrams.html

HackerRank: Sherlock and anagrams (V)

March 27, 2016

Problem statement:

https://www.hackerrank.com/challenges/sherlock-and-anagrams

Difficulty: Moderate

More C# solution:

Solution 1:
Julia, here is code you should study; more advanced than yours.

a person works for Box Inc.
https://www.hackerrank.com/__run
https://gist.github.com/jianminchen/576ecf2cd127a703cb7a

Learn C# coding: readonly, Equals, override, constructor, use byte instead of int. Take some time off, learn C#, OO design basics:

Here are the code, make some comments to read some articles to catch up:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SherlockAndAnagrams
{
class CharCount
{
protected bool Equals(CharCount other)
{
return Equals(Array, other.Array);
}

/*
Design concern:
hashcode for anagram strings - same

use unchecked function
figure out this design:
a b c ... y z
3 1 1 1
3*(26*13)^25 1*(26*13)^24 1*(26*13) 1
*/
public override int GetHashCode()
{
int hc = Array.Length;
for (int i = 0; i < Array.Length; ++i)
{
hc = unchecked(hc * 13 + Array[i]); // Julia, figure out how this hashcode is working for anagram
}
return hc;
}

public readonly byte[] Array; // Julia, readonly, why to use byte[]

public CharCount()
{
Array = new byte[26];
}

public CharCount(CharCount charCount)
{
Array = new byte[26];
for (int i = 0; i < 26; i++)
{
Array[i] = charCount.Array[i];
}
}

public void AddChar(char ch) //
{
Array[ch - 'a']++;
}

public override bool Equals(object obj) // override Equals function
{
CharCount other = obj as CharCount;
if (obj == null)
{
return false;
}

for (int i = 0; i < 26; i++)
{
int val = Array[i].CompareTo(other.Array[i]); // byte.CompareTo
if (val != 0)
{
return false;
}
}

return true;
}
}
class Program
{
static void Main(string[] args)
{
int t = int.Parse(Console.ReadLine());
for (int i = 0; i < t; i++)
{
HandleTestCase();
}
}

private static void HandleTestCase()
{
IDictionary<CharCount, int> dictionary = new Dictionary<CharCount, int>();
string str = Console.ReadLine();

for (int i = 0; i < str.Length; i++)
{
CharCount charCount = new CharCount();
for (int j = i; j < str.Length; j++)
{
charCount.AddChar(str[j]);
if (!dictionary.ContainsKey(charCount))
{
dictionary.Add(new CharCount(charCount), 1);
}
else
{
dictionary[charCount] = dictionary[charCount] + 1;
}
}
}

Console.WriteLine(dictionary.Values.Sum(value => ((value * (value - 1)) / 2)));
}
}

}

HackerRank: Sherlock and Anagrams IV

March 27, 2016

Problem statement:

https://www.hackerrank.com/challenges/sherlock-and-anagrams

Difficulty: Moderate

HackerRank: Sherlock and anagrams (II)

March 27, 2016

Problem statement:

https://www.hackerrank.com/challenges/sherlock-and-anagrams

Difficulty: Moderate

Summary of practice

This problem solving gets hot. Julia found something she struggled a lot. When Julia spent more than 2 hours on a problem in the Saturday evening, she knew that she is in trouble. She needs to be trained, and she needs a mentor.

Time Spent: March 26, 2016 Saturday evening 9:30 - 11:30

Sunday morning 9:00 - 12:00

Julia's practice is here.

Code Study

Let us get ideas how other people solve the problems, study the code. Julia is training herself thinking in C# using HackerRank:

1. Hash function design

code source is provided by a person 19 Gold, unbelievable smart and quick/ fast / great expressive code.

Code study - code is here.

The anagram string function is composed to the design of key in the Dictionary.

Julia added some comment above the hash function

precondition:

if two string are anagram, then key of these two strings should be the same

"ab" and "ba" are the anagram, key should be the same

"ab" and "bc" are not the anagram, so keys should not be the same.

Julia's comment: 701 is confusing, why it has to be this big number?

int Fun(string s, int l, int r)

{

var ret = new int[26];

for (int i = l; i <= r; i++)

ret[s[i] - 'a']++;

int x = 0; // Julia's comment: should be 1

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

x = x * 701 + ret[i];

return x;

}

Julia goes over the detail to check:

Key is designed using math formula polynomial expression:

string a -> key is integer: 0

string b -> key: 1

string ab -> key: x = 1

x = 1* 701 + 1

string ba -> 11 -> key: x = 1 * 701 + 1

string bc -> 011-> key: x = 0 , count of a is 0

x = 1, count of b is 1

x = 1 * 701 + 1

"ba" and "bc" are not anagram, so the key should be different: both are 1 * 701 + 1

string ad -> 1001 -> key x = 1, count of a is 1

x = 701 + 0 , count of b is 0

x = 701 *701 + 0

key = 701^3 + 1

Math or computer science

Julia found out that the idea can save a lot of time, she likes to work hard. But she is also "lazy" and likes to write less code.

Julia changed the key design, and ran the code in HackerRank, it also passed the test cases. In Julia's opinion, the code has a bug in theory but pass the HackerRank test; so, Julia fixed the code anyway.

Just practice! It is not a science of math, it is computer science.

C# practice code is here.

Further code review on other things

Julia is still interested in writing loops, more expressive. Let us review how the code does:

public object Solve()

{

for (int tt = ReadInt(); tt > 0; tt--) // Julia's comment: put ReadInt() into a loop

{

string s = ReadToken();

int n = s.Length;

int ans = 0;

var count = new Dictionary<int, int>();

// Julia's comment: substring length from 1 to n-1,

for (int i = 1; i < n; i++)
{
// substring start position - j, end position: j+i-1, and check j+i <=n, easy to reason - avoid bug

for (int j = 0; j + i <= n; j++)

{

var key = Fun(s, j, j + i - 1);

if ( !count.ContainsKey(key) )
{

count[key] = 0;
}

count[key]++;

}
}

foreach (var p in count)
{

ans += p.Value * (p.Value - 1) / 2;
}

writer.WriteLine(ans);

}

return null;

}

701 prime number vs 26

One more step, improvement: Failed. Number from 701 to 26, it does not work. It depends on the length of string, which is <=100. Julia tried to figure out some math, algebra, but she is sure that the number should be coefficient, so,

at least >100.

Julia, the key design for anagram string can be modified:

precondition:

if two string are anagram, then key of these two string should be the same

"ab" and "ba" are the anagram, key should be the same

"ab" and "bc" are not the anagram, so key should not be the same.

int keyForAnagramString(string s, int l, int r)

{

var ret = new int[26];

for (int i = l; i <= r; i++)

ret[s[i] - 'a']++;

int x = 1; // Julia's comment: should be 1

for (int i = 0; i < 26; i++)
{

x = x * 26 + ret[i];
}

return x;

}

Julia spent 5 hacko to buy the test case input/ output:

One more try - 101

Because the string length is <=100, so that coefficient is less than 100.

Key design can be changed to a small number 701 to 101, it passes the HackerRank test:

precondition:

if two string are anagram, then key of these two string should be the same

"ab" and "ba" are the anagram, key should be the same

"ab" and "bc" are not the anagram, so key should not be the same.

int keyForAnagramString(string s, int l, int r)

{

var ret = new int[26];

for (int i = l; i <= r; i++)

ret[s[i] - 'a']++;

int x = 1; // Julia's comment: should be 1

for (int i = 0; i < 26; i++)
{

x = x * 101 + ret[i];
}

return x;

}

January 8, 2017

Come back to visit the blog, and then spent 10 - 20 minutes to work on layout, fixed grammar errors.

HackerRank: Sherlocks and Anagram (III)

March 27, 2016

Problem statement:

https://www.hackerrank.com/challenges/sherlock-and-anagrams

Difficulty: Moderate

Solution to study:

https://gist.github.com/jianminchen/68453786a6ea03774a16

Julia, you should warm up with C# Dictionary<string, int>, and also StringBuilder class, AppendFormat function.

Let us review how to design anagram key more efficient, more understandable way:

/*
Think about how smart and easy it is to design this key for anagram string.

Precondition:
if two strings are anagram, the key should be same.
if two strings are not anagram, the key should be different.

Test case:
ab, the key is {0}-1{1}-1
ba, the key is {0}-1{1}-1,
but
bc, the key is {0}-0{1}-1{2}-1

compare to the design of anagram key using integer, this one is much easy to understand and follow.

http://juliachencoding.blogspot.ca/2016/03/hackerrank-string-sherlock-and-anagrams.html
*/

static string GiveKey(int[] arr){
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < 26 ; i++){
            sb.AppendFormat("{0}-",arr[i]);
        }
        return sb.ToString();
    }

HackerRank: String - Sherlock and anagrams (I)

March 27, 2016

Problem statement:

https://www.hackerrank.com/challenges/sherlock-and-anagrams

Difficulty: Moderate

Time Spent: March 26, 2016 Saturday evening 9:30 - 11:30
Sunday morning 9:00 - 12:00

Several mistakes to fix:

1. Julia, improve your analysis on test cases from HackerRank

2. Julia, understand Anagram requirement.

3. loop index issues

Julia's practice:

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

Go over test case again:

1. abba,

Let's say S[i, j] denotes the substring(i, j-i+1)

S[0,1] = "ab",

S[0,2]="abb",

S[1,1] = "b"

S[4,4] = "b"

S[1,2] = "ab"

S[3,4] = "ba"

For S = abba, anagrammatic pairs are:

{S[1,1], S[4,4]}, //

{S[1,2], S[3,4]},

{S{2,2], S{3,3]},

{S[1,3], S[2,4]}

Notice that substring can be selected by first char of string, choice of n-m, n is string length, m is substring length.

substrings can be overlapped, but still are anagrammatic pairs.

S[1,3] and S[2,4] are overlapped, but are the anagrammatic pair.

Sample test case "abba", output should be 4, but Julia got 3. Spent time to fix index error.

2. sample case: ifailuhkqq

should be: 3

Julia got 4

Actually, Julia, you should simplify the test case first.

it is the same as ifailqq,

also it is the same as ifilqq

How many anagramammatic pairs in "ifilqq"

"i","i" - S[1, 1] and S[3,3]

"if","fi" - S[1, 2] and S[2,3] <- warm up anagram definition: same chars with same counts

"q", "q"

but 2 'i' char in the string "ifilq",

1 'i' char in the string "filqq",

Actually, the test case can be simplified using:
"abacdd", the pairs are (a,a), (ab, ba), (d, d). That is very simple and understandable!

"abacd" and "bacdd" are not anagrams, because two 'a' in first string, but 1 a in second string.
so two strings are not anagram.

Julia, what you spent time on:

1. List<int> constructor issue - 10 minutes, List<int>(i)

2. 10 minutes to figure out that you should work on anagrams strings

3. 10 minutes to write, 15 minutes to debug - Wrote a wrong anagram function

"ifilq" is not an anagram of "filqq", sample test case No. 2 should be 3

Julia is not very strong on testing software, she writes the software and puts it on. The software
she writes can be improved tremendously, but she needs to find out what to improve.

To be continued.