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:

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:

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: Sherlock and anagrams (II)

March 27, 2016

Problem statement:

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:

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:

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:

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.