Code Review: Sherlock and Anagrams

January 8, 2016

Introduction

Julia worked on the code review by one user third time, she plans to review all submissions from the same user. 

Workout

First algorithm review -

Sherlock and Anagrams

Julia worked on the algorithm, here are her previous blogs about the algorithm:

Practice I

Practice II

Practice III

Practice IV

Practice V

Practice VI: Warmup after 3 months

Spent some time to go over code:

Read editorial notes, and also have some practice using C# on January 8, 2016.

Another practice using C#.

January 22, 2017 

Another practice, C# code is here.
study code review done by mdfst13, review is here.

Code review by User (III)

January 8, 2016

Introduction
Julia woke up in the middle of the sleep, and then she checked her two posts on code review, she was amazed that in her 3 hours sleep she got 3 up-votes. Actually she went bed around 2:00am, she posted 2 algorithms for code review. What a bad unhealthy life style - let internet ruin the good sleep.

She knows that she has to learn how to play a good game about reputations, and do not let reputation take over her strong analytical mind she is trying to build up. At 9:48am the morning, her reputation is up to 189, 20 more reputation compared to 2:00am, January 8, 2017 when she went to sleep.

One of algorithms is about simple function. Link is here. She got 2 up-votes, each brings 5 reputation.
Another one is about "Find kth largest element in the union of two sorted array". Link is here. She also got 2 up-votes.

She taught herself to be very patient in Saturday, spent over 4 hours to work on Hackerearth simple function again, and learn whatever she has to do. She got feedback from her post - the code is hard to follow, where code is rewritten from her study other player's C++ code. One algorithm a time (This algorithm Julia worked on more than 2 * 10 hours). So, she likes to avoid complicated code, and work with high reputation talent (For me that solution is hard for follow – Paparazzi Jan 2 at 15:12 about Julia's post) better, she said goodbye to her old post and all her concerns to work on the follow-up post.

So, most of important is to have some sportsmanship, check other people's post, and give out an up-vote as well. Think about others, give out some encouragement as well. The small sportsmanship leads her to do a study on a post by this user.

Workout

Julia experienced the excitement from reputation going up 20 from 169 to 189, after she worked on algorithm more than 8 hours in Saturday, January 7, 2016. Now she is imaging that how much work she has to complete in order to make this reputation go up to the user - CodeYogi 1683, top 8% overall. 

100 algorithm, have some time to study peers. 

First algorithm review -

Sherlock and Anagrams

Julia worked on the algorithm, here are her previous blogs about the algorithm:

Practice I

Practice II

Practice III

Practice IV

Practice V

Practice VI: Warmup after 3 months

HackerRank: Sherlock and anagram - warmup practice after 3 months

June 12, 2016

Introduction 

First, software coding -> tennis sports -> gardening - a small talk 

Julia likes blossom of flowers, she enjoyed but does not have time to do any gardening work. She spends a lot of hours on tennis court to keep her physical fit, cheer her up, play social games to build up very good team sports spirit through her workout. 

She observes neighborhood gardeners watering the flower, grass every day in summer time, in the city of Vancouver,  it takes a lot of hard work. She enjoys the neighborhood gardening. 

So, to show some talent in software coding, she likes to learn from a patient gardener, watering, taking away weeds. In other words, read her own coding blog, learn to educate herself better through the short period of time.  

Today, she likes to bring back her favorite practice 3 months ago, an algorithm - "Sherlock and anagram", and then review them, write more practice. 

3 months is not long time, but those past 3 months, Julia found out that she is street-smart again. She starts to get more organized, more time-savvy, and know the importance to push herself to write her own words about experience. It does help. 

One example, she stops to check in C# file using github, she just uses gist to quickly create a link. She did create almost 300 gists, each gist saves 5 minutes compared to check in files using github, she saved 1500 minutes, close to 25 hours time. 

Another example, she tries to focus on reasoning and analysis, writing things to help her solve problem. One problem a time. So, she works on one problem, using more than 5 solutions - BFS, DFS, using Queue, using Stack, phone number problem, therefore, she can apply the problem solving to all other similar problems. 

Workout 

Now, work on the coding:

1. HackerRank: Sherlock and anagram - 7 blogs with practices
Practice on HackerRank is like to play tennis sports, you have to experience various hitting partners, good workout!

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

No. 2
http://juliachencoding.blogspot.ca/2016/03/hackerrank-sherlock-and-anagrams-ii.html

No. 3

http://juliachencoding.blogspot.ca/2016/03/hackerrank-sherlocks-and-anagram-ii.html

No. 4 Study 6 solutions - Julia chose from over 200 solutions
http://juliachencoding.blogspot.ca/2016/03/hackerrank-sherlock-and-anagrams-iv.html

Julia, work on this code, and put test case in, write your own C# practice:
study the code, order by values,  not by key, try it!
https://gist.github.com/jianminchen/ffcca0582b5f0d1d6a9b

study the blog: Dictionary OrderByDescending
https://goo.gl/6ZbTPz
baby step to learn C# Dictionary class API - Order by and distinct
https://gist.github.com/jianminchen/eff03bea08a95061deb4185af74fea18

No. 5
http://juliachencoding.blogspot.ca/2016/03/hackerrank-sherlock-and-anagrams-iv_27.html

No. 6
http://juliachencoding.blogspot.ca/2016/03/hackerrank-sherlock-and-anagram-vii.html

Warm up 12 solutions - "Sherlock and anagram" one by one. Each one for a blog. Focus on speed, correctness.

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

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.

Solution 2:
use Dictionary class, string key for anagram string, use getHashCode() call to turn key as Int.

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

Read about getHashCode() webpage:
https://msdn.microsoft.com/en-us/library/system.object.gethashcode(v=vs.110).aspx

Solution 3:
https://gist.github.com/jianminchen/8f6bd4631f0b5f0bdee7


Solution 4.
use Dictionary class, sort the key string, then anagram strings will be the same.

https://gist.github.com/jianminchen/59e326cbd1d8910c01c7

solution 5:
Excellent code, written by a programmer in salesforce.com
https://www.hackerrank.com/rest/contests/w13/challenges/sherlock-and-anagrams/hackers/rosharyg/download_solution
Julia likes the code:

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

Solution 6:   <-  simple and quick, it can be written in less than 20 minutes. But not time efficient! O(n^2 * string length)

Use brute force, 3 loops, and then define anagramChecking function, just basic array, simple and quick.

https://gist.github.com/jianminchen/9f381875942d468ccb00

HackerRank: Sherlocks and Anagram (III)

March 27, 2016

Problem statement:

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

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.

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

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 

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.