I’ve recently had occasion to write LINQ versions of two functions I’d written some time back. It proved instructive.

Random numbers that sum to N

Doing some testing, I needed an array of 100 random floating point numbers that sum to 1.0. That is, given an array a, (a[0] + a[1] + a[2] ... + a[99]) = 1. The easiest way I know of to do that is to generate an array of 100 random values, sum them, and then divide each number by the sum.

    const int ArraySize = 100;
    Random rnd = new Random();
    double[] a = new double[ArraySize];
    double sum = 0;
    // generate the values
    for (int i = 0; i < a.Length; ++i)
    {
        a[i] = rnd.NextDouble();
        sum += a[i];
    }

    // now divide each item by the sum
    for (int i = 0; i < a.Length; ++i)
    {
        a[i] /= sum;
    }

The math behind this is pretty simple. What you end up with is (a[0]/sum + a[1]/sum + a[2]/sum ... + a[99]/sum), which works out to sum/sum, which is 1.

Somebody asked me for a LINQ version.

    var temp = (from d in Enumerable.Range(0, ArraySize)
                select rnd.NextDouble()).ToArray();
    var sum = temp.Sum();
    var a = temp.Select(d => d/sum).ToArray();

An obvious extension to this is generating an array of N values that sum to some arbitrary value. The first part of the algorithm is the same: generate N numbers, and sum them. Then, rather than dividing each number by the sum, divide by (sum/desired_value). Or, you can multiply by (desired_value/sum). So the final LINQ expression becomes:

    var a = temp.Select(d => d*(desiredValue/sum)).ToArray();

And don’t worry about the division in the inner loop there. The compiler (either the C# compiler, or the JIT compiler) will move it out of the loop.

Finding palindromes

At a previous job, one part of the interview process for entry-level programmers was having them solve some simple programming puzzles on the white board. I called it The White Board Inquisition. A common exercise was to write a function that determines if an input string is a palindrome. We’d keep it simple and have them look for an exact match. So “amanaplanacanalpanama” would be a palindrome, but “A man, a plan, a canal, Panama!” would not be. Stripping out the non-alphabetic characters and doing case-insensitive matching is a simple refinement, but we wanted to see how the candidate approached the primary problem.

The simplest way, of course, is to reverse the string and do a comparison, but we wouldn’t allow them to call a reverse method. If they wanted to reverse the string, they’d have to do it themselves. Many did. Another common approach is to push the characters onto a stack and then pop them, comparing the popped values with the string characters, in order.

Few candidates tripped to the in-place method of comparing the characters starting from the outside and moving in, like this.

    private bool IsPalindrome(string input)
    {
        int i = 0;
        int j = input.Length - 1;
        while (i < j)
        {
            if (input[i++] != input[j--])
                return false;
        }
        return true;
    }

Somebody recently asked me for a LINQ version of a palindrome finder. The obvious solution is to employ the Reverse extension method and then compare the sequences. But it’s easy enough to duplicate the above algorithm.

    private bool IsPalindrome(string input)
    {
        return
            Enumerable.Range(0, input.Length / 2)
                        .Select(i => input[i] == input[input.Length - i - 1])
                        .All(b => b);
    }

A common misconception is that the LINQ code will do those three operations in sequence: generate a list of indexes, then generate a list of results, and then compare the results. That most definitely is not how the generated code works. If you enable runtime library source stepping, you’ll see that the sequence of operations follows the looping construct very closely. The LINQ solution is slower, of course, because it’s working with iterators and such, but it isn’t stupid.

The more I work with LINQ, the more impressed I am by what I can do with it. It’s not always the fastest executing solution, but for most of what I do that doesn’t matter. I find that the expressiveness leads to much shorter, more easily understood, and more reliable code than writing large looping constructs. I imagine that interviewers these days expect candidates to demonstrate a thorough understanding of LINQ. I know that I certainly would.