Group anagrams - mock interview 1/24 2018 11:00 PM

GroupAnagrams_mockInterview.cs

using System;

// To execute C#, please define "static void Main" on a class
// named Solution.

class Solution
{
    static void Main(string[] args)
    {
        for (var i = 0; i < 5; i++)
        {
            Console.WriteLine("Hello, World");
        }
    }
    
    // case sensitive, 
    // remove duplicate
    // Maximum 256 - define key
    // hashset to look up to remove duplicate
    public static IList<string>[] groupAnagram(string[] words)
    {
        if(words == null || words.Length == 0)
        {
            return List<string>(); 
        }
        
        var length = words.Length;         
        
        var anagrams = new Dictionary<string, HashSet<string>>();                        
        
        foreach(ver word in words)
        {
            var key = getAnagramKey(word);         
            
            if(!anagrams.ContainsKey(key))
            {
                anagrams.Add(key, new HashSet<string>());
            }
            
            // if it is 
            var hashSet = anagrams[key]; 
                
            var isExisting = hashSet.Contains(word); 
            if(!isExisting)
            {
              anagrams[key].Add(word); 
            }                                        
        }
        
        // convert the output to IList<string>
    }
    
    public static string getAnagramKey(word)
    {
        var charCount = new int[256]; 
        
        foreach(var symbol in word)
        {
            // convert to 
            charCount[symbol - '?']++;
        }
        
        return String.Join("+", charCount); 
    }
}
/*
run-time complexity: length of char operation for each word  O(n), 
n is all chars in the string of words
space comlpexity: dictionary Key size,  at most length of words, 
                             value size, maximum -> length of word
        O(n) , n is length of words
*/        
// frontendmaster.com
// react framework, webpack 
// algorithm/ data structure/ 
// http://juliachencoding.blogspot.ca/
// jianminchen.fl@gmail.com  

/* 
Your previous Plain Text content is preserved below:

INPUT
anagrams(['xxy', 'cab', 'bca', 'cab', 'bac', 'dash', 'shad'])

OUTPUT
[
  ['xxy'],
  ['cab', 'bca’, 'bac'],
  ['dash', 'shad']
]

Group strings that are anagram of each other into a list without duplicate.

‘cab’ is an example duplicates removed. There are 2 ‘cab’ in the input and 
only 1 ‘cab’ in the output.
You can think of anagram as two words that have the same count per letter. 
You should treat upper and lower case differently.
'xxy’ is by itself because it doesn’t have any other strings that are anagram with ’xxy’

Abc and abc are NOT anagrams
abcc and abc are NOT anagrams
abc and cab are anagrams because each of them has 1 a, 1 b, and 1 c

You can assume it’s 256 ASCII

You don’t need to compile the code, let me know when you’re done implementing 
the code. If you’re unsure about the syntax, just make it up. 

Julia wrote down the keywords for the algorithm first:

Keywords:

anagrams - permuate chars in the word, cab has anagram 3 * 2 * 1 = 6 , abc, bac, ...

Group strings -> 
remove duplicate -> how to check it exisitng uing O(1) in the array? extra space -> hashset

You can think of anagram as two words that have the same count per letter. -> abc, bac 
case sensitive -> abc -> Abc 

tip: 256 ASCII include lower/ upper case

Brute force solution
int[256]  - integer -> 'x' -> ascii - 0 - 255, 'x' - 'a' a - z -> 0 - 26 , 'x' - 'a' -> ascii start -> 0 -> ? ''

Keep silent for two minutes, really think about the problem.
12:19 pm - 12: 21 pm 

int[0]+ ' ' + int[1] +... +int[255] -> keyString 

hashset line 32 () <- 

anagram -> hash function 
prime number -> 256
Optimal solution, it is hard to come out the hash function right away. 
 */