March 27, 2016
Problem statement:
Difficulty: Moderate
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:
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.
The anagram string
function is composed to the design of key in the Dictionary.
Julia added some comment above the hash function
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
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.
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,
// 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
{
// 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;
}
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;
}
Come back to visit the blog, and then spent 10 - 20 minutes to work on layout, fixed grammar errors.
