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

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

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


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?

-
+1 for thinking about arrays –  vnp Aug 5 '14 at 18:19

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

-
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. –  user50581 Aug 5 '14 at 21:28
Enumerable.Range(0, w.Length - 3) should be Enumerable.Range(0, w.Length - 2). –  mjolka Aug 5 '14 at 22:03
@mjolka You're right, fixed. –  svick Aug 5 '14 at 22:19
@user7744 I really doubt that's actually true. Anyway, this doesn't look like performance critical code, so don't micro-optimize prematurely. –  svick Aug 5 '14 at 22:21
@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. –  CodesInChaos Aug 6 '14 at 13:01

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[triplet] = countThisTriplet+1;

-
I got ninja'd by svick! –  Snowbody Aug 6 '14 at 13:56

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.

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

-
“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 Aug 5 '14 at 23:59
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.) –  svick Aug 6 '14 at 0:03
@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 Aug 6 '14 at 0:06
@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. –  mjolka Aug 6 '14 at 5:12
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. –  user50581 Aug 6 '14 at 5:35

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.

-
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) –  user50581 Aug 5 '14 at 19:10
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. –  vnp Aug 5 '14 at 19:33
Pointers in C# are only for very special cases (mostly interop), they certainly should not be used in normal code. –  svick Aug 5 '14 at 20:45
@vnp chars in .NET are 16 bits, so a triplet would not fit in four bytes. –  mjolka Aug 6 '14 at 0:35
@mjolka Does .net has a 64 bit integer type? –  vnp Aug 6 '14 at 6:02

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

-
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. –  user50581 Aug 6 '14 at 11:09
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(). –  Snowbody Aug 6 '14 at 14:02
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? –  Vince Panuccio Aug 6 '14 at 23:11