Finding the most frequently used sequence of characters in a comma-delimited input string of words

Question

I'm making a demo program for a job interview and I'd like to know if there is anything I can make work faster in my current solution. It's a C# console application that accepts input in form of a single string with the words delimited by , symbol. The task is to find the most commonly encountered combination of three characters throughout all the words. It's not specified what I should do if there are multiple triplets with the same rate of appearance, so I'm just returning whatever ends up sorted to the first place. Here is my take on this:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        string input = args.Length > 0 ? args[0] : null;

        if (input == null) // demo input
            input = "Lorem,ipsum,etiam,habitasse,conubia,sed,habitasse,tristique,,erat,varius,vitae,nunc,vulputate,etiam,proin,,interdum,malesuada,nam,curabitur,nibh,pharetra,ultricies,elit,elementum,viverra,vehicula,lacinia,vestibulum,dapibus,,bibendum,vestibulum,quisque,potenti,dictum,ad,curabitur,neque,,taciti,consequat,malesuada,quisque,ultrices,scelerisque,in,fermentum,fringilla,per,ad.Tortor,habitasse,auctor,consequat,imperdiet,vel,iaculis,suscipit,torquent,,porta,eget,cubilia,cras,quisque,sociosqu,auctor,neque,,ac,dictum,elit,rhoncus,ornare,augue,cras,quis,tempor,sodales,congue,nulla,dictum,quisque,iaculis,magna,mattis,odio,,elementum,varius,turpis,pretium,consequat,gravida,ut,hendrerit,metus,,pulvinar,scelerisque,eu,et,neque,cubilia,mauris,elementum,porttitor,eleifend,vestibulum,luctus,id,diam,pellentesque,convallis,nisi,libero,ante,aliquam,maecenas,facilisis.Suscipit,posuere,gravida,luctus,cursus,erat,eleifend,,magna,tempor,iaculis,arcu,rutrum,viverra,lorem,,posuere,ipsum,leo,aenean,donec,praesent,mollis,phasellus,sociosqu,orci,magna,potenti,donec,curabitur,feugiat,,ultricies,integer,lacus,mollis,porta,consectetur,fames,dolor,,himenaeos,enim,quisque,dapibus,viverra,maecenas,nam,ac,eget,est,sed,conubia,ad,aliquet,sed,consequat,augue,,quisque,bibendum,luctus,id,tempus,lacinia,facilisis,,fames,eget,ut,taciti,nullam,malesuada,integer.Massa,egestas,enim,urna,magna,ultrices,placerat,at,,adipiscing,taciti,bibendum,sodales,consequat,mollis,tempus,platea,,lorem,nisi,congue,vehicula,lacinia,fusce.Donec,gravida,interdum,malesuada,vel,erat,velit,massa,pulvinar,fringilla,potenti,,habitasse,ullamcorper,varius,vel,lobortis,proin,risus,nulla,senectus,,amet,pharetra,quam,elit,convallis,quis,laoreet,vestibulum,rhoncus,eget,lectus,hendrerit,elementum,etiam,viverra,sit,porttitor,etiam,sollicitudin,porta,nibh,non,,nibh,ipsum,inceptos,pellentesque,placerat,conubia,neque,donec,id,vivamus,sed,eget,suscipit,tristique,orci,id,ipsum,ligula,morbi,aliquam,eros,inceptos,leo,curabitur,vehicula,aliquam,aenean,porta,tempor,cras,aenean,nostra,sapien,,ac,lacus,donec,ut,placerat,bibendum,potenti,pellentesque,cubilia,,nunc,nisi,tristique,nam,tristique,varius,ultrices.Maecenas,bibendum,himenaeos,ut,a,ornare,sociosqu,integer,mi,scelerisque,congue,dolor,suspendisse,mattis,eu,,pulvinar,maecenas,etiam,fermentum,leo,eleifend,quis,semper,hac,cursus,aenean,ornare,at,potenti,class,donec,dapibus,dictum,vitae,id,suspendisse,taciti,,placerat,sem,elementum,id,metus,vehicula,nostra,curae,aliquet,,inceptos,quisque,massa,augue,sollicitudin,porta,cras,senectus.Aliquam,sit,nec,vulputate,mauris,lorem,inceptos,volutpat,hac,quisque,,iaculis,blandit,vel,erat,condimentum,orci,massa,luctus,placerat,,fermentum,facilisis,purus,eget,potenti,sem,nec,hendrerit,tempus,habitant,eros,sit,curabitur,congue,porttitor,curabitur,praesent,tortor,,mattis,donec,vehicula,massa,a,donec,fames,lacinia,,est,sodales,fringilla,aliquam,lacus,class,nisi,hac.Hac,venenatis,himenaeos,volutpat,a,at,semper,aenean,erat,etiam,dapibus,quis,diam,,erat,mi,curabitur,nisl,proin,praesent,suspendisse,bibendum,nibh,erat,mollis,consequat,congue,etiam,feugiat,rhoncus,tempor,libero,pellentesque,duis,id,eu,,mattis,in,integer,lectus,non,sed,sapien,eu,felis,donec,,taciti,purus,vulputate,tellus,massa,malesuada,litora,nisl,feugiat,sollicitudin,accumsan,porta,ligula,lobortis,vitae,suspendisse,varius,,in,lorem,habitant,arcu,pellentesque,blandit,,viverra,nulla,class,molestie,pharetra,duis,ac,eu,tempus,aliquam,eros,tristique,quam,a,tempor,netus,neque,vel,tincidunt.Inceptos,porta,id,nunc,platea,aptent,orci,litora,maecenas,vivamus,,at,consequat,convallis,tempus,pharetra,lorem,enim,est,,ultrices,nunc,velit,urna,gravida,sem,molestie,sem,faucibus,habitasse,feugiat,id,pulvinar,etiam,pretium,,a,donec,eu,sapien,suscipit,pretium,nam,,elit,nam,sagittis,suspendisse,fermentum,bibendum,sed,adipiscing,scelerisque,id,et,faucibus,adipiscing,aenean,nostra,,duis,purus,odio,feugiat,fringilla,eu,primis,donec,,ultrices,lacinia,justo,euismod,nullam,class,litora,est,tempus,tortor,phasellus,massa,praesent,sit,vehicula,eu,consectetur,felis,dapibus,interdum.Class,fringilla,luctus,a,semper,hendrerit,quisque,mattis,,netus,potenti,pellentesque,risus,scelerisque,mi,pulvinar,morbi,,aenean,eros,posuere,rhoncus,semper,aliquam,eget,mi,aliquam,sapien,sem,scelerisque,ornare,ultricies,,sem,tempus,aliquet,potenti,nulla,vel,bibendum,,ornare,accumsan,varius,at,himenaeos,suscipit,netus,nisi,fermentum,habitant.Volutpat,at,iaculis,nam,a,habitasse,dictum,ipsum,hac,quisque,aliquam,vestibulum,gravida,vehicula,arcu,donec,dolor,faucibus,consequat,vivamus,,curabitur,luctus,justo,vivamus,duis,accumsan,tellus,,blandit,commodo,etiam,vivamus,ultricies,fermentum,curabitur,pretium,sociosqu,in,praesent,vulputate,dictumst,aptent,,tempor,porttitor,ligula,duis,nulla,non,platea,consequat,fermentum,,platea,tortor,convallis,feugiat,tincidunt,donec,scelerisque,ultricies,convallis,pulvinar,porta,nam,porttitor,lacus,,aenean,euismod,cubilia,magna,ut,,tortor,dolor,dui,nam,egestas.Dui,eros,nisi,in,habitasse,vulputate,bibendum,pulvinar,fusce,,platea,integer,rutrum,mattis,varius,cras,lorem,,etiam,nisi,lectus,nullam,egestas,consectetur,at,non,eros,nostra,pellentesque,hac,nullam,curabitur,consequat,nunc,,inceptos,lacinia,quisque,donec,porta,placerat,potenti,non,nam,tempor,et,odio,lectus,netus,auctor,,sollicitudin,sodales,erat,etiam,arcu,ligula,faucibus,,aenean,mauris,vel,elementum,duis,mollis,convallis.Suscipit,lobortis,purus,gravida,euismod,duis,luctus,eu,lacus,condimentum,,duis,vitae,leo,lacinia,proin,laoreet,vehicula,sollicitudin,,feugiat,ut,viverra,per,mattis,integer,quisque,erat,semper,scelerisque,inceptos,neque,lacinia,varius,vehicula,ac,,hac,mauris,rutrum,pulvinar,cursus,amet,,eros,ullamcorper,ad,non,facilisis,eu,primis,venenatis,commodo,phasellus,enim,fringilla,maecenas,convallis,eget,duis,ornare,lacinia,id,eros,class,malesuada,aenean,proin,etiam,aliquam,faucibus,tempor,,at,arcu,pretium,luctus,ut,curae,iaculis,varius,,lorem,tempus,a,fermentum,duis,ut,erat,sollicitudin,id,tincidunt,quisque,cursus,sed,imperdiet,volutpat,torquent,mattis,placerat,quis.Lectus,class,vulputate,ut,lacus,litora,,dictum,sollicitudin,sociosqu,platea,vivamus,,fermentum,libero,quam,commodo.Sollicitudin,blandit,urna,quam,egestas,risus,condimentum,varius,semper,,magna,enim,pharetra,molestie,rhoncus,tempus,interdum,,ad,taciti,malesuada,lobortis,felis,class,a,tincidunt,duis,convallis,netus,vitae,per,orci,viverra.Morbi,nibh,tincidunt,aenean,nulla,sapien,volutpat,tellus,interdum,facilisis,potenti,aliquam,ante,mauris,,varius,neque,ultrices,nisl,tempus,est,risus,vehicula,pretium,maecenas,class,sollicitudin,blandit,a,sodales,per,tincidunt,viverra,eros,,torquent,cras,curae,volutpat,torquent,sociosqu,,luctus,nibh,lacus,tincidunt,vulputate.Auctor,sapien,vivamus,sapien,aenean,ligula,cursus,cubilia,vehicula,aliquam,,neque,purus,ultricies,mauris,fringilla,varius,ante,proin,etiam,neque,odio,habitasse,curabitur,id,magna,diam,tincidunt,fringilla,,vulputate,fermentum,taciti,vel,quisque,volutpat,eget,vehicula,per,quisque,eleifend,aenean,risus,torquent,quisque,,risus,netus,torquent,accumsan,netus,,sodales,habitant,malesuada,tempor.Consectetur,lobortis,molestie,senectus,pharetra,rhoncus,,amet,pellentesque,eleifend,proin,porttitor,etiam,,congue,pellentesque,iaculis,nibh,cubilia,velit,leo,per,fringilla,risus,class,augue,netus,,placerat,habitant,integer,mollis,scelerisque,aenean,pulvinar,,molestie,leo,iaculis,posuere,eget,dictum,lobortis,commodo,ac,elementum,ullamcorper,dictumst,dui,lectus,fames,etiam,eleifend,,dolor,interdum,vitae,tortor,taciti,vel,tellus,sagittis,quam,iaculis,,fermentum,phasellus,himenaeos,mauris,aliquet,vehicula,ut,fringilla,tempor,habitant,ligula,viverra,fusce,sapien,euismod,rhoncus,orci,ultrices,,enim,etiam,purus,fringilla,nulla,varius,pulvinar,ac,suspendisse,curabitur,,rutrum,habitant,quis,taciti,pulvinar,aenean,duis,augue,per,primis,diam,ultrices.Ac,eleifend,elementum,sollicitudin.Semper,feugiat,quisque,ut,sociosqu,orci,hendrerit,ad,pulvinar,,curae,aliquam,interdum,condimentum,nulla,duis,sapien,metus,,diam,dictum,porttitor,quisque,id,semper,etiam,augue,cursus,ante,faucibus,metus,interdum,pulvinar,,lectus,sem,maecenas,mattis,leo,,urna,potenti,iaculis,arcu,augue,conubia,congue,dolor,hendrerit,tempor,primis,praesent,pretium,molestie,,pharetra,eros,posuere,aliquam,lacus,maecenas,imperdiet,nec,congue,suspendisse,enim,vulputate,turpis,viverra,himenaeos,dapibus,potenti,egestas,augue,mattis,sem";

        var words = input.Split(',');

        int totalWords = words.Length;
        string[] trimmedWords = new string[totalWords];
        for (int i = 0; i < totalWords; i++)
            trimmedWords[i] = words[i].Trim();

        var hs = new HashSet<string>();
        var dic = new Dictionary<string, int>();

        for (int j = 0; j < totalWords; j++)
        {
            string word = trimmedWords[j];
            int wordLength = word.Length;
            for (int i = 0; i <= wordLength - 3; i++)
            {
                string triplet = word.Substring(i, 3);
                if (!hs.Contains(triplet))
                {
                    hs.Add(triplet);
                    dic[triplet] = 1;
                }
                else
                    dic[triplet]++;
            }
        }
        // there might be a faster way to sort by value
        var sortedList = dic.OrderByDescending(x => x.Value); 
        string output = sortedList.First().ToString();

        // shows 50 most used triplets, just for checking
        //var sortedList = dic.OrderByDescending(x => x.Value).ToList(); 
        //string output = string.Join(Environment.NewLine, sortedList.GetRange(0, sortedList.Count >= 50 ? 50 : sortedList.Count));

        Console.WriteLine(output);
        Console.ReadKey();
    }
}

I'm using HashSet to lookup and add new triplets, because it's the fastest thing I know in C# that can do this.

I am not entirely sure about using a Dictionary<string, int> for storing the number of triplet occurrences. A faint voice in my head says something about arrays, but I can't make out the rest :)

Also just sorting the dictionary and getting the first element with Linq doesn't seem like the best approach, but unfortunately I don't know a better way yet.

How could this application be improved in terms of performance and code quality?

Answer 1

string[] trimmedWords = new string[totalWords];
for (int i = 0; i < totalWords; i++)
    trimmedWords[i] = words[i].Trim();

You should learn about LINQ. (Or maybe just learn more, you're using it elsewhere.) With it, you can write this as (possibly adding ToArray() if you require the result to be an array):

vat trimmedWords = words.Select(w => w.Trim());

---

for (int j = 0; j < totalWords; j++)
{
    string word = trimmedWords[j];

This is the only place in the whole loop where you're using j, so you should have used foreach instead, since it's simpler.

---

if (!hs.Contains(triplet))
{
    hs.Add(triplet);
    dic[triplet] = 1;
}
else
    dic[triplet]++;

I don't see any reason for the HashSet here, Dictionary works just as well for deciding whether it contains something (use its ContainsKey() method).

---

var sortedList = dic.OrderByDescending(x => x.Value); 
string output = sortedList.First().ToString();

If you want just the largest value, then sorting the whole collection is unnecessary. You could use MaxBy() from MoreLINQ to do this (or write one yourself, it's not hard).

---

You could also use LINQ instead of the Dictionary and HashSet, a fully LINQed solution would be:

input.Split(',')
     .Select(w => w.Trim())
     .SelectMany(w => Enumerable.Range(0, w.Length - 2).Select(i => w.Substring(i, 3)))
     .GroupBy(t => t)
     .MaxBy(g => g.Count())
     .Key

(Though I'm not saying writing everything in a single LINQ expression is the best solution here.)

Answer 2

I don't think it's necessary to have both a Dictionary and a HashSet. Just use the Dictionary. It has a ContainsKey() method, or get even simpler code by using TryGetValue():

int countThisTriplet;
dic.TryGetValue(triplet,out countThisTriplet); // sets countThisTriplet to 0 if triplet not found
dic[triplet] = countThisTriplet+1;

Answer 3

There are already some good answers here, but since this is for a job interview I'm going to imagine I'm looking at this as a potential employer.

Stylistically, there are a few things that jump out:

• Inconsistent use of the var keyword.
• Missing braces.
• Poor variable names hs and dict.
• Commented out code.
• Comments do not follow commenting conventions (start with an uppercase letter, end with a period, etc.).

These show a lack of attention to detail. It's a job interview, you want to make the best possible impression.

This comment in particular

// there might be a faster way to sort by value

makes me wonder. Did you look for a faster way? Did you try other ways? Why is that comment there?

If I wanted to be really picky, I would question you about the lack of access modifiers and a namespace. Why did you make these decisions?

A bigger concern is a lack of methods. Use methods to decompose the problem into smaller problems, and reusable code. The only time you can dump everything in Main is in a programming contest.

My biggest concern is that your solution is overly complex, using both a HashSet and a Dictionary. This suggests a lack of familiarity with the standard libraries.

So let's break this down, starting with Main. I would expect it to look like this.

var input = args.Length > 0
    ? args[0]
    : GetDemoInput();
var words = input.Split(',').Select(word => word.Trim());
var trigrams = words.SelectMany(GetTrigrams);
Console.WriteLine(GetMostFrequentlyOccurring(trigrams));

Now let's fill in the blanks. Extracting your code for trigrams, we get

private static IEnumerable<string> GetTrigrams(string word)
{
    for (var i = 0; i <= word.Length - 3; i++)
    {
        yield return word.Substring(i, 3);
    }
}

It might be overkill for this assignment, but you could make it more generic

private static IEnumerable<string> GetTrigrams(string word)
{
    return GetNGrams(word, 3);
}

private static IEnumerable<string> GetNGrams(string word, int n)
{
    for (var i = 0; i <= word.Length - n; i++)
    {
        yield return word.Substring(i, n);
    }
}

Great. One method to go. Finding the most frequently occurring whatever has popped up on Code Review a few times, and you have the basic solution, but I'll add this here for completeness' sake.

private static string GetMostFrequentlyOccurring(IEnumerable<string> words)
{
    var tally = new Dictionary<string, int>();
    var max = 0;
    string result = null;
    foreach (var word in words)
    {
        int count = tally.TryGetValue(word, out count)
            ? count + 1
            : 1;

        tally[word] = count;
        if (count > max)
        {
            max = count;
            result = word;
        }
    }

    return result;
}

Answer 4

A faint voice in my head says something about arrays, but I can't make out the rest

There are at least 2 approaches utilizing just an array (no HashSets, no Dictionaries). I don't know how anti-C# they are; for C++ I'd consider them first.

• Approach 1 (linearithmic time, linear space). Create an array of pointers. Scan input adding pointers to valid triplets (those not containing a comma). Sort the array. Scan it calculating length of runs of identical triplets and keeping record of the best-so-far.

• Approach 2 (linear time, weird space). Notice that there are just 26*26*26 = 17576 possible triplets. Create an array of 17576 integers (initialized to 0). Scan input transforming each valid triplet into an index; increment an array value at this index. Scan array looking for maximum; translate its index back into a triplet.

PS: I do not know C#, so no comments on style etc.

Answer 5

If you're going for a junior role, don't worry. All they want to see is that you can solve the problem. Forget about the code entirely. Code quality will come with time and several code reviews.

Another factor which determines implementation is the use case it serves. How many times will this code be called? Once per day? Several thousand times a second? Those sort of questions will also determine how much effort and (more importantly) how much money you invest in that code.

I had a quick shot at this problem.

char GetCharLower(char c) {
    if (Char.IsUpper(c)) {
        return Char.ToLower(c);
    }
    return c;
}

void Main()
{
    var s = "Lorem,ipsum,etiam,habitasse,conubia,";

    // Preallocate for better performance (depending again, one how this code is used in production)
    var results = new Dictionary<string, int>(s.Length / 3);

    // A buffer to put stuff in an avoid allocating new arrays on each pass.
    var buffer = new char[3];

    for (int i = 0; i < s.Length - 3; i++)
    {
        // Ignore sequences shorter than 3 characters
        if (s[i+2] == ',') {
            i = i + 3;
        }

        buffer[0] = GetCharLower(s[i]);
        buffer[1] = GetCharLower(s[i+1]);
        buffer[2] = GetCharLower(s[i+2]);

        var threeChar = new String(buffer);

        int count;

        if (results.TryGetValue(threeChar, out count)) {
            count++;
        } else {
            count = 1;
        }

        results[threeChar] = count;
    }

    results.OrderByDescending (r => r.Value).Dump(); // Dump() LINQPad method.
}