5
\$\begingroup\$

The requirements:

The following was an interview test for a junior position.

You’ve been asked to write a program that will take a dictionary file (csv list of words) and output the number of words containing the same letters grouped by the length in a separate txt file.

Eg west and stew are both 4 letter words containing the same letters and as such count a match.

My understanding on the requirements was to read the .CSV file and find anagrams of the words, in the file.


My Solution:

First off you can find the entire solution on GitHub, but here's the code:

Program.cs (CLI application to start the program)

namespace Syzygy.App
{
    class Program
    {
        static void Main(string[] args)
        {
            // Read file
            CSVReader reader = new CSVReader("../../../CsvTest.csv");
            var words = reader.Read();

            // Create a list of dictionaries (length:list<string>)
            // Makes the string comparisson a lot quicker as we don't have to
            // iterate over the entire list multiple times.
            var dictionaryList = new List<WordDictionary>();
            CreateDictionaries(words, ref dictionaryList);

            var wordHandler = new WordHandler();
            List<string> anagrams = wordHandler.FindAnagrams(dictionaryList);

            ShowAndWrite(anagrams);

        } 

        /// <summary>
        /// Prints and writes to file.
        /// </summary>
        /// <param name="Anagrams"></param>
        private static void ShowAndWrite(List<string> Anagrams)
        {
            Console.WriteLine("Amount of anagrams: " + Anagrams.Count + "\n");
            foreach (var word in Anagrams)
            {
                Console.WriteLine($"{word.Length}:{word}");
            }
            var fw = new FileWriter(Anagrams);
        }

        /// <summary>
        /// Uses the CSV-parsed words to create a list of dictionaries
        /// where each dictionary holds an integer (length) and a list of words.
        /// </summary>
        /// <param name="words"></param>            The words from our CSV-file
        /// <param name="dictionaryList"></param>   A reference to the memory-address of the list of dictionaries.
        private static void CreateDictionaries(IEnumerable<string> words, ref List<WordDictionary> dictionaryList)
        {
            var dictionary = new WordDictionary(1);
            foreach (var word in words.OrderBy(w => w.Length))
            {
                if (word.Length != dictionary.Length)
                {
                    dictionaryList.Add(dictionary);
                    dictionary = new WordDictionary(word.Length);
                }
                dictionary.AddWord(word);
            }
        } 
    }
}

CSVReader.cs

namespace Syzygy.BL
{
    public class CSVReader
    {
        public string Path { get; set; }
        public CSVReader(string path)
        {
            Path = @""+path;
        }

        public IEnumerable<string> Read()
        {
            return File.ReadAllLines(Path)
                            .SelectMany(w => w.Split(',')).Where(w => !String.IsNullOrEmpty(w));  
        }
    }
}

WordHandler.cs

namespace Syzygy.BL
{
    public class WordHandler
    {
        /// <summary>
        /// Simply iterates over the list of words looking for
        /// any occurrences of the scrambled word-parameter.
        /// Since each dictionary will at least hold ONE 
        /// word it will match with (itself) we need a count
        /// variable to ensure that we only return matches 
        /// on other words.
        /// </summary>
        /// <param name="word"></param>
        /// <param name="words"></param>
        /// <returns></returns>
        public bool CompareWords (string word, List<string> words)
        {
            int count = 0;
            foreach(var dictionaryWord in words)
            {
                var sortedDictionaryWord = String.Concat(dictionaryWord.ToLower()
                                                         .OrderBy(c => c));
                var sortedWord = String.Concat(word.ToLower()
                                                .OrderBy(c => c));
                if (sortedDictionaryWord == sortedWord)
                {
                    if(count > 0)
                    {
                        return true;
                    }
                    count++;
                }
            }
            return false;
        }

        public List<string> FindAnagrams(List<WordDictionary> dictionaryList)
        {
            var Anagrams = new List<string>(); 
            foreach (var dictionary in dictionaryList)
            {
                foreach (var word in dictionary.Words)
                {
                    if (CompareWords(word, dictionary.Words))
                    {
                        Anagrams.Add(word);
                    }
                }
            }

            return Anagrams;
        }

    }
}

WordDictionary.cs

namespace Syzygy.BL
{
    public class WordDictionary
    {
        public int Length { get; set; }
        public List<string> Words { get; set; }

        public WordDictionary(int length)
        {
            Length = length;
            Words = new List<string>();
        }

        public void AddWord(string word)
        {
            Words.Add(word);
        }
    }
}

FileWriter.cs

namespace Syzygy.BL
{
    public class FileWriter
    {
        public FileWriter(List<string> listToWrite)
        {
            using (StreamWriter writeText = new StreamWriter("Anagrams.txt"))
            {
                writeText.WriteLine($"Anagram Count:{listToWrite.Count}");
                listToWrite.ForEach(w => 
                                    writeText.WriteLine($"{w.Length}:{w}"));
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ @""+path does the empty string has any purpose? It's a rather strange operation. \$\endgroup\$ – t3chb0t Jun 27 '17 at 17:56
  • \$\begingroup\$ If I'm correct the @ concatenation creates an absolute path? \$\endgroup\$ – geostocker Jun 27 '17 at 18:03
  • \$\begingroup\$ This is new to me but I'm pretty sure it doesn't. Didn't you test it? How would the compiler know which drive letter to use? \$\endgroup\$ – t3chb0t Jun 27 '17 at 18:05
  • \$\begingroup\$ The @ symbol prevents backslash escaping. For instance, "\path\to\file" will try to escape the p, t, and f characters. @"\path\to\file" will treat it as a complete literal. If path is already a string, concatenating with a string literal isn't going to do anything. \$\endgroup\$ – Siegen Jun 27 '17 at 18:10
  • \$\begingroup\$ You are correct. That was an incorrect assumption made by me. The program runs fine and reason to use a @ is simply to set it to a verbatim string which may look syntatically nicer to look at since you won't require multiple backslashes, but in all honesty it does absolutely shit to help my solution. Obviously a huge mistake by me. The way it works atm. is that it looks at where the output folder is and steps back into the folder in which the solution lies in (and where the .csv file exists). \$\endgroup\$ – geostocker Jun 27 '17 at 18:10
3
\$\begingroup\$

Your code is easy to read but I think there's quite a bit of room for improvement. If I were screening your code, I'd be looking for:

  • Good structure
  • Good and consistent naming
  • Knowledge of BCL and appropriate use of built in libraries

I'd want to see a solution that was reasonably performant but my criteria would be something like "runs successfully in the time it takes for me to get a coffee". If you were applying for a job that required regularly writing high perf code that would be different of course.

Now, I think I can pull out one method to talk about in terms of what I'm looking for:

private static void ShowAndWrite(List<string> Anagrams)
{
    Console.WriteLine("Amount of anagrams: " + Anagrams.Count + "\n");
    foreach (var word in Anagrams)
    {
        Console.WriteLine($"{word.Length}:{word}");
    }
    var fw = new FileWriter(Anagrams);
}

Excellent, let's start with the signature:

static void ShowAndWrite(List<string> Anagrams)

The naming convention for parameters in C#, which you used extensively, is camelCase.

Now, on to the first line:

Console.WriteLine("Amount of anagrams: " + Anagrams.Count + "\n");

I'd think to myself, does this person know about the overload of WriteLine that mirrors string.Format? Do they know that line endings can be different on different operating systems? I'd much prefer to see Environment.Newline here or another Console.WriteLine() call.

Cool, let's move on to the next line:

foreach (var word in Anagrams)

It's like saying foreach (var apple in oranges). You should have called word an anagram.

The body of the foreach is great :)

var fw = new FileWriter(Anagrams);

Now, this is the most troubling line. Constructors should not do non-trivial work. When I first read the code I thought: that variable is unused, it's probably there by mistake. Do you know about File.WriteAllLines?

There's another place where you're reinventing the wheel:

w.Split(',')).Where(w => !String.IsNullOrEmpty(w)

You need a different overload of string.Split where you can specify StringSplitOptions.RemoveEmptyEntries.


There are lots of other places where you could look to improve. E.g.

var dictionaryList = new List<WordDictionary>();
CreateDictionaries(words, ref dictionaryList);

Why not just return a new list in CreateDictionaries?

This class:

public class WordDictionary
{
    public int Length { get; set; }
    public List<string> Words { get; set; }

    public WordDictionary(int length)
    {
        Length = length;
        Words = new List<string>();
    }

    public void AddWord(string word)
    {
        Words.Add(word);
    }
}
  • Why is Length publically settable?
  • Why doesn't AddWord validate that the word is the right length?

e.g.

public void AddWord(string word)
{
    if (word.Length != Length)
    {
        throw new ArgumentException();
    }
    Words.Add(word);
}

That would show me that you're thinking about how your classes might be (mis)used in the future.

I'd probably give you a F2F assuming your code ran correctly but we'd have a lot of talking points from this (a good thing!) As a mental exercise, can you justify why you've created the classes that you have?

\$\endgroup\$
  • \$\begingroup\$ All really good questions. As for the classes I simply thought it would be relevant to separate my concerns, I also thought it would make the code more verbose, if that makes sense? It seemed more readable that way. In regards to your questions about how I'm handling newline, I do know of both - but didn't realize it was a code smell to use \n in the string. In regards to FileIO - it's nothing I use on a regular basis, so I simply checked out a SO thread and implemented a similar solution. Does WriteAllLines work on any IEnumerable collection? \$\endgroup\$ – geostocker Jun 27 '17 at 21:44
  • \$\begingroup\$ Another reason as to why I wanted to separate my concerns was to, obviously, more easily write test cases. Though I sort of got hounded by the recruiter in charge of filling the role, so I didn't really ahve time to refactor anything. That's clearly not a good excuse, but the only one I truly have... :? \$\endgroup\$ – geostocker Jun 27 '17 at 21:45
  • \$\begingroup\$ @geostocker that's fair enough - you want to put in enough effort to get the interview but it's not reasonable to expect you to sink too much time into it. \$\endgroup\$ – RobH Jun 28 '17 at 5:58
2
\$\begingroup\$

One simple point:

Your definition of "csv" may get you in trouble. CSV is a very poorly defined "standard". You've taken the assumption that CSV means only comma separated values. However in practice, many CSV parsers allow text strings to be enclosed in quotes so that commas can be included. I.e. this is valid CSV that has only two columns:

bob,"brown, etc"

However your code would split that into three values:

[ 'bob', '"brown,', ' etc" ]

Moreover, CSV parsers that support this also support the concept of a double quotation mark to escape an actual quotation mark inside a quoted string. So this line:

bob, "brown says, ""hi"""

Should properly parse as:

[ 'bob', 'brown says, "hi"' ]

You can decide for yourself whether or not they intend to test it to this level of detail. Different people have different definitions of what "CSV" means. Since this is for anagram checking you might think that only actual words would be found, but accounting for edge conditions is also an important job for programmers.

\$\endgroup\$
1
\$\begingroup\$

Someone might have more comments about your overall design but I'm going to focus on your performance.

All of the below numbers are for 1000 rounds with the output (ShowAndWrite(anagrams);) turned off.

Your default GitHub code takes an average of 0.0274552673s/round.

One easy optimization is to normalize your strings only once. The problem stated doesn't say they expect to get out the words they put in; only the number of anagrams found. So change your WordDictionary.AddWord() to be

public void AddWord(string word)
{
    string normalizedWord = string.Join("", word.ToLower().OrderBy(c => c));

    Words.Add(normalizedWord);
}

And change WordHandler.CompareWords() to

public bool CompareWords (string word, List<string> words)
{
    int count = 0;
    foreach(var dictionaryWord in words)
    {
        if (dictionaryWord == word)
        {
            if(count > 0)
            {
                return true;
            }
            count++;
        }
    }
    return false;
}

This alone drops the average run time by an order of magnitude, to 0.0010646236.

Then, they don't say they expect to see each permutation of the anagram you found. So don't compare words over and over. Just compare them once, when added, using a HashSet and a counter for each normalized string.

public class WordDictionary
{
    public int Length { get; set; }

    public HashSet<string> Words { get; set; } = new HashSet<string>();

    public Dictionary<string, int> WordCounts { get; set; } = new Dictionary<string, int>();

    public WordDictionary(int length)
    {
        Length = length;
    }

    public void AddWord(string word)
    {
        string normalizedWord = string.Join("", word.ToLower().OrderBy(c => c));

        if(Words.Contains(normalizedWord))
        {
            WordCounts[normalizedWord]++;
        }
        else
        {
            Words.Add(normalizedWord);
            WordCounts.Add(normalizedWord, 1);
        }
    }
}

-

public class WordHandler
{
    public List<string> FindAnagrams(List<WordDictionary> dictionaryList)
    {
        var Anagrams = new List<string>(); 
        foreach (var dictionary in dictionaryList)
        {
            foreach (var word in dictionary.WordCounts.Where(f => f.Value > 1))
            {
                Anagrams.Add(word.Key);
            }
        }

        return Anagrams;
    }
}

That drops you another order of magnitude to 0.0007868567s.


Being able to say stupid things like "This algorithm is two orders of magnitude faster that my first attempt" (regardless of the fact that your first attempt was already quite performant) can probably earn you some points in interviews.

\$\endgroup\$
  • \$\begingroup\$ One question about your solution, wouldn't this only return a single instance of an anagram? Say you first add "on" and then "no", then "no" would be considered an anagram of "on", but "on" wouldn't have been considered an anagram of "no" beforehand - since it wasn't in the list. \$\endgroup\$ – geostocker Jun 27 '17 at 18:58
  • \$\begingroup\$ No, normalizing the strings (the .ToLower() and .OrderBy() calls) make sure that both "no" and "on" would be treated as the exact same string. \$\endgroup\$ – Siegen Jun 27 '17 at 19:02
  • \$\begingroup\$ Right. But what I mean (sorry if I misunderstand your code), is that you are chevking a collection Words for a normalized string and if it exists you increment the fictionary. In the scenario i mentioned, only the second word would be matched as its matching word wouldn't exist in the first comparison. Or am I completely off base here? \$\endgroup\$ – geostocker Jun 27 '17 at 19:14
  • \$\begingroup\$ So, say we encounter "on" first. It'd be normalized to "no". Then the HashSet wouldn't have "no". So we add "no" to the HashSet and add a new pair to the Dictionary with {"no", 1}. That "1" says we've encountered that normalized anagram once. Then we encounter "no". When we normalize it, it'd still be "no". We check the HashSet and it does have it. So we simply increment the Dictionary where the key is our normalized anagram ("no"). Since both "no" and "on" normalize to "no", we'd end up with a count of 2, regardless of the order received. \$\endgroup\$ – Siegen Jun 27 '17 at 19:27
  • \$\begingroup\$ See the priblem I have with that is that the count should be 3. On is an anagram of no, and vice versa. \$\endgroup\$ – geostocker Jun 27 '17 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.