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.)

• user50581: I used for loops instead of foreach loops because from my experience with high performance games (several million passes * 60 per second) can take additional time to retrieve the Length or Count of an array. Not sure if it was a problem in my design that time, but since then I prefer to explicitly get that length once and then reuse the returned value.
• mjolka: Enumerable.Range(0, w.Length - 3) should be Enumerable.Range(0, w.Length - 2).
• svick: @mjolka You're right, fixed.
• svick: @user7744 I really doubt that's actually true. Anyway, this doesn't look like performance critical code, so don't micro-optimize prematurely.
• CodesInChaos: @user7744 With arrays extracting the length into a variable can actually decrease performance. At least some versions of the jitter can only omit the bounds checks on a[i] if the loop is for(int i = 0; i < a.Length; i++) and not if you you use a variable instead of a.Length in the condition. | Still I agree with svick that this is probably premature optimization.

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;

• Snowbody: I got ninja'd by svick!

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

• svick: "Inconsistent use of the var keyword." Why do you think that is an issue and what would you consider be a consistent use? var is a weird thing that makes the code more readable and less readable at the same time, so I think deciding whether to use it line by line makes sense.
• svick: Also, I certainly wouldn't hold not using full sentences in comments against anyone. I wouldn't call that "lack of attention to detail", I would call that "focusing on what's important". (Style is important, but I think this is going too far.)
• mjolka: @svick I've changed "not full sentences" to "not following commenting conventions" (with relevant link). Just trying to guard OP against any overly-critical interviewers :)
• mjolka: @user7744 "missing" might not have been the right word; yes, I meant the single-line if, for, and else where you've omitted braces. Google, Roslyn, and StyleCop all recommend against it. Obligatory #gotofail link.
• user50581: Thankfully, using code autoformatting, which I happen to use all the time, allows to visually spot such mistakes very easily. But I understand the problem this may potentially cause. Thanks for the references.

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.

• user50581: Pointers? I have never coded anything using pointers myself, so I'll probably have a hard time defending my choice during the interview. Also they are not anti-C#, the job is junior C# app dev, so I suppose they would expect me to solve this using a typical C# approach (not that I know everything it implies :p)
• vnp: There is a dirty trick to avoid pointers. Have an array of 4-byte integers. They are wide enough to host a triplet. Doesn't scale well though.
• svick: Pointers in C# are only for very special cases (mostly interop), they certainly should not be used in normal code.
• mjolka: @vnp chars in .NET are 16 bits, so a triplet would not fit in four bytes.
• vnp: @mjolka Does .net has a 64 bit integer type?

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.
}

• user50581: You could use "string".ToLowerInvariant() to get rid of uppercase letters in the whole input string. I think it might be faster than checking each char separately. Also, the code will be checked for performance efficiency, yes. That's why I tried using Hashset, but it turned out it's not necessary.
• Snowbody: Also, even if you don't know about ToLowerInvariant(), I'm pretty sure it's actually slower to check each char with Char.IsUpper() than to just unconditionally call Char.ToLower().
• Razor: The reason I check each character is to place a burden on the CPU rather than memory. If it's a huge string (which yours is), you want to avoid unnecessary allocations. Again, it depends on the responsibility this code will play in the grand scheme of things. If you're going to talk about something being "slower", what exactly is slow? 10 nanoseconds as opposed to 20 nanoseconds? Are you building a mission critical section of code in a real time system?