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
Showing posts with label anagram. Show all posts
Showing posts with label anagram. Show all posts
Sunday, March 27, 2016
HackerRank: Sherlock and anagrams (V)
March 27, 2016
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)));
}
}
}
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
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
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
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.
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!
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.
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.
Sunday, March 13, 2016
HackerRank: string algorithm - Anagram
March 13, 2016
Anagram
Julia's C# implementation:
https://gist.github.com/jianminchen/f3c48ed9f3b16e8c5928
Julia made a few tries before she noticed that she needs to figure out the formula:
Another approach is to add all the differences, and then, divided by 2
C# submission code to study:
1. String class contains, Split functions etc.
Split function - return array length to get the count of any char in the string.
https://gist.github.com/jianminchen/adbfc2d809fb5b2bac78
2. add all the difference between two strings, and then divide it by 2
https://gist.github.com/jianminchen/7bbe86bbb83787d6b98b
3. Using Dictionary, KeyValuePair class
https://gist.github.com/jianminchen/78346475b6a7ce5d1681
4. Read more Lambda expression code in C#
https://gist.github.com/jianminchen/9d121bd95266db41dfa8
5. using StringBuilder, C# code
https://gist.github.com/jianminchen/d972656068fa8088ae70
6. use string.Remove function
https://gist.github.com/jianminchen/65687cefd2b107ec5e23
Java Code:
1. https://gist.github.com/jianminchen/794ffee7726df6062a1f
2. Maybe not smart idea, but it works - declare a string
String alph = "abcdefghijklmnopqrstuvwxyz";
https://gist.github.com/jianminchen/0cfa60bac880f2bba10f
Anagram
Julia's C# implementation:
https://gist.github.com/jianminchen/f3c48ed9f3b16e8c5928
Julia made a few tries before she noticed that she needs to figure out the formula:
for (int i = 0; i < SIZE; i++)
{
if (sumA[i] > 0)
// add count of chars in
array sumA but not in sumB
// axxbbbxx,
// axxb -> bbxx, change a to b, that is it!
// axxb a 1, b 1, x 2
// bbxx, a 0, b 2, x 2
// formula ->
count += (sumA[i] >=
sumB[i]) ? (sumA[i] - sumB[i]) : 0;
}Another approach is to add all the differences, and then, divided by 2
C# submission code to study:
1. String class contains, Split functions etc.
Split function - return array length to get the count of any char in the string.
https://gist.github.com/jianminchen/adbfc2d809fb5b2bac78
2. add all the difference between two strings, and then divide it by 2
https://gist.github.com/jianminchen/7bbe86bbb83787d6b98b
3. Using Dictionary, KeyValuePair class
https://gist.github.com/jianminchen/78346475b6a7ce5d1681
4. Read more Lambda expression code in C#
https://gist.github.com/jianminchen/9d121bd95266db41dfa8
5. using StringBuilder, C# code
https://gist.github.com/jianminchen/d972656068fa8088ae70
6. use string.Remove function
https://gist.github.com/jianminchen/65687cefd2b107ec5e23
Java Code:
1. https://gist.github.com/jianminchen/794ffee7726df6062a1f
2. Maybe not smart idea, but it works - declare a string
String alph = "abcdefghijklmnopqrstuvwxyz";
https://gist.github.com/jianminchen/0cfa60bac880f2bba10f
Julia likes to read code, any language in
submission. She could
not stop reading, she has read more than 50 solutions, totally opened to so many creative ideas.
not stop reading, she has read more than 50 solutions, totally opened to so many creative ideas.
Subscribe to:
Posts (Atom)