The Resplendent Developer

Software Development and Software Quality Assurance

A Recent Coding Exercise

Recently, in an interview, I was asked to create a routine to do the following:

Given a lower-case, alphabetic string, determine if the letters can be made into a palindrome. If it was, I should return a 1, and if not, return a 0. I was given about 30 minutes to do this and had a very limited compiler to work with. I chose C# as my language and produced the following code.

using System;

public int isPalindrome( string S )
{
  // A Palindrome can have only 1 character with an odd number of occurrances. 
 //Otherwise, each must appear in a multiple of 2.
  int lessthan2 = 0;

  // Look at each letter of the alphabet
  for(char i=’a’;i<=’z’;i++)
  {

   if(S.Contains(i.ToString()))
   {
    int accum=0;
    for(int j=0;j<S.Length;j++)
    {
     if(S[j]==i)
     {
      accum++;
     }
    }
    if(accum%2==1)
    {
     lessthan2++;
    }
   }
   if(lessthan2 >1)
   {
    return 0;
   }
  }
  return 1;
}

 

While the code fit all the requirements and successfully computed the answer (including for strings up to one million characters in length) and was performant, the code was somewhat inelegant. In fact, the hiring manager specifically commented that I iterated through the alphabet and that was an unacceptable solution. While I believe that given the constraints, this was an unfair conclusion, it’s a fair criticism. He also didn’t point out that my check for “Lessthan2” could have been in the same if structure so that the routine could exit sooner. If I’m going to have multiple return statements, there is no reason I can’t do that. So, the question that comes to mind, is how can I make this more elegant?

After thinking about it and refreshing the syntax of the generics, I came up with this on the second pass:

using System;
using System.Collections.Generic;

public int isPalindrome ( string S )
{
  int lessthan2 = 0;

 HashSet<char> letters = new HashSet<char>(S);

  foreach(char i in letters)
  {
   int accum=0;
   for(int j=0;j<S.Length;j++)
   {
    if(S[j]==i)
    {
     accum++;
    }
   }
   if(accum%2==1)
   {
    lessthan2++;
    if(lessthan2 >1)
    {
     return 0;
    }
   }
  }
  return 1;
}

 

HashSet is a nice little generic introduced in .Net 3.5 that accepts a list of items and only keeps the uniques. In my above example, it would take a string such as “aabbcc” and simply save “abc”. This would let us iterate through a possible subset of the alphabet. We can do a tad less clunky by going all the way back to what .Net 1.0 gave us: Regex!

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
public int isPalindrome ( string S )
{
  int lessthan2 = 0;
  HashSet<char> letters = new HashSet<char>(S);

  foreach (char i in letters)
  {
   int accum = Regex.Matches(S, i.ToString()).Count;

   if (accum % 2 == 1)
   {
    lessthan2++;
    if (lessthan2 > 1)
    {
     return 0;
    }
   }
  }

  return 1;
}

 

I think that is stronger. However, is it the only one? I’m sure I can dig deeper in regular expressions and come up with an even more elegant approach. Still, is this the most efficient solution? If we dig a little deeper into what .Net 3.5 gave us, we can see there is indeed a much more elegant solution: LINQ!

LINQ (Language Integrated Query) lets us apply a rather powerful querying language to almost anything. So, how would we do that in LINQ?

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

public int isPalindrome ( string S )
{
  // Create and populate a collection so Linq can do our
  // heavy lifting.
  List<char> ArrayofS =new List<char>(S);

  // Run a Linq query to return every letter where there are
  // an uneven number of instances. A Palindrome, by definition
  // can only have a maximum of ONE uneven number
  var query = from charlist in ArrayofS
   group charlist by charlist into templist
   let count = templist.Count()
   where count %2 == 1
   select new {Value = templist.Key, Count = count};

  // Not a Palindrome
  if (query.Count() > 1)
  {
   return 0;
  }

  // A Palindrome
  return 1;
}

 

Comments? Thoughts? Criticisms? Leave a comment!

Comments are closed.