He Tasks Me

Khan

Fans of Star Trek no doubt recognize the iconic picture of Khan from the movie "Star Trek: The Wrath of Khan". In the movie, Khan sets himself what ultimately ends up being an impossible task, defeating his old adversary, the great Captain Kirk.

Recently, I learned of an excellent site for practicing computer programming problems - "tasks", if you will, TestDome.com. Their problems take about 15 or 20 minutes, and vary in difficulty from easy to difficult. The idea is, supposedly, companies can use these problems to measure a job candidates skills, and likewise, a candidate can use the tests to practice.

I would like to solve one of their sample, public problems, and then make some observations.

As the problem I will solve is in fact public, posting a solution should be fair game. The way the site works is you write your solution in the browser, press run, in real time your code is compiled and ran against various tests. You know immediately if your solution is "correct", or if you need to fix it. You can run and fix as many times as needed within the time constraint allotted for the problem.

TESTDOME FOLDERS PROBLEM

Your task:
Implement a method FolderNames, which accepts a string containing an XML file that specifies folder structure and returns all folder names that start with startingLetter. The XML format is given in the example below.For example, for the letter 'u' and XML file:

<?xml version="1.0" encoding="UTF-8" ?>
<folder name="c">
    <folder name="program files">
   <folder name="uninstall information" />
   </folder>
<folder name="users" />
</folder>

the function should return "uninstall information" and "users" (in any order). Below is a screen capture of the actual problem:

So the task is to implement the method:

public static IEnumerable <string> FolderNames(string xml, char startingLetter)
{
throw new NotImplementedException("Waiting to be implemented");
}

I produced a solution in three statements, plus a return statement. This should not be categorized as hard. The first two statements read/parse the XML string. The the third statement creates an IEnumerable<string>. Finally, we return that IEnumerable.

So, on line one of our method, we need to read the XML string:
XDocument doc = XDocument.Parse(xml);

On the second line, we create an IEnumerable of XElements, which we will query against:

var folders = doc.Descendants("folder");

On the third line, finally, we create the LINQ to XML query. How does one know to use a LINQ query? This comes from experience, and realizing LINQ queries return IEnumerable<T>. If you were in the unfortunate situation of not being aware of that fact, then you will most likely implement using a more complicated and error prone API. So here is the LINQ query, our third line:

      var query = from f in folders
      where  f.Attribute("name").Value.StartsWith(startingLetter.ToString())
      select f.Attribute("name").Value;

And that's it. Add the using statements for LINQ:


using System.Linq;
using System.Xml.Linq;

and you're good to go. Copy and paste the following method body into TestDome, along with adding the two using statements to the top, and you get a 100% pass. To recap:

The Solution

using System.Linq;
using System.Xml.Linq;

  public static IEnumerable<string> FolderNames(string xml, char startingLetter)
  {
   XDocument doc = XDocument.Parse(xml);

   var folders = doc.Descendants("folder");

    var query = from f in folders
    where  f.Attribute("name").Value.StartsWith(startingLetter.ToString())
    select f.Attribute("name").Value;

    return query;
  }

Observations

This problem is categorized as "hard". What is a difficult or easy problem is rather subjective. I suggest most programmers could in fact solve the problem, given more than 20 minutes. i.e., in a real-world scenario.
Caution: The solution I provided one could argue is not optimal. Maybe even flawed. Yet it passed. 100%.
To make the solution better, one really should check for a System.NullReference exception on the first f.Attribute call. To see why, either remove the "name" attribute from one of the XML elements, or change it to something else. In other words, there is no requirement that the XML has in fact a "name" attribute for a folder. Attributes can be optional. Thus, if in the XML, you change the "name" attribute to, say, "nickname", run the accepted 100% solution again, it will fail. Hmmm.
So, we have to fix the 100% solution. To do so, lets add a check for null to the query:

var query = from f in folders
where f.Attribute("name") != null && f.Attribute("name").Value.StartsWith(startingLetter.ToString())
select f.Attribute("name").Value;

Using that for the query will produce a working solution that handles the optional name attribute case.
The null check in (4) works because we are using the C# short-ciruit AND operator, &&. If f.Attribute("name") is null, the rest of the line does not execute, so no System.NullReference exception occurs.
Checking for null on XML attributes is standard-fair...

So that's it. Testing sites are interesting tools to practice on. However, their use as an accurate, valid tool to measure the actual skill and knowledge of a candidate is more questionable.

Alternate Syntax

LINQ offers two syntaxes: 1) The query syntax (so named because it resembles SQL), which I already demonstrated, and 2) The method syntax (so named because it uses the LINQ extension methods, of course).
The solution using the method syntax would be as follows:


 var query = folders
            .Where(f => f.Attribute("name") != null &&
            f.Attribute("name").Value.StartsWith(startingLetter.ToString()))
            .Select(f => f.Attribute("name").Value);

  return query;