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.