CSV parser for a tech test

Question

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}"));
            }
        }
    }
}

Answer 1

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?

Answer 2

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.

Answer 3

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.