Joel Spolsky is a BadAss once again

So, this has probably been discussed by thousands of bloggers. But, Joel Spolsky “revealed” one of the questions he asks to potential interns (http://itc.conversationsnetwork.org/shows/detail4359.html). But, I want to take my stab at it; and how to think about it as an interviewer.

Before hand; here’s Joel Spolsky’s description about why he setup this test: “Asking them to code in front of you is a way for you to figure out if they are smart. … We want to see them doing it. Because, we want to hear them think, we want to see them think, we want to see how quickly they are doing it. We want proof they can do it. Because anybody can generate code for a million dollars. To get a job they will somehow find a way. You think they’re not asking their friends for help?” (summarized quote).

The question he asked was:

“Given an array of numbers. And, given a pointer into the middle of the array of numbers. It doesn’t have to be the middle, just an element within that array of number. Like the 37th element. Does all of the numbers summed up to the left of that pointer equal the sum of all the elements to the right of that pointer?”

When I was listening to that podcast my brain immediately sprung into work. Ignoring the rest of Joel’s words, I started trying to figure out how to program a solution to the problem. My initial solution to the problem was really ugly, because I started thinking of the solution as soon as he said “37th”. It was like my brain started to solve an SAT problem without reading the whole question.

So, I jumped on the computer, loaded up VS, and started to write a function that would do the quick and dirty solution:

static bool IsArrayEqual(int[] arr, int splitIndex)
{
    int leftSum = 0, rightSum = 0;

    for (int i = 0; i < arr.Length; i++)
    {
        if (i == splitIndex)
        {
            i++;
            continue;
        }

        if (i < splitIndex)
        {
            leftSum += arr[i];
        }
        else
        {
            rightSum += arr[i];
        }
    }

    return leftSum == rightSum;
}

As you can see the solution featured a straight O(n) algorithm with if statements in between.

It was a  really stupid solution. As soon as I looked over the code the first gut wrenching reaction was to remove the if statements. If statements are always branch statements to the compiler; and if the forward look ahead fails then they are costly. So, I rewrote the function to exclude the if statements.

static bool IsArrayValuesEqual(int[] arr, int splitIndex, out int leftSum, out int rightSum )
{
    leftSum     = SliceSum(arr, 0, splitIndex - 1);
    rightSum    = SliceSum(arr, splitIndex + 1, arr.Length - 1);

    return leftSum == rightSum;
}

static int SliceSum(int[] arr, int startIndex, int endIndex)
{
    int sum = 0;
    for (int i = startIndex; i < endIndex; i++)
        sum += arr[i];
    return sum;
}

At this point I was pretty proud of myself. With no reason to be. Why be proud of a solution to an intern question? Because I was able to figure out an answer in under 5 minutes? Because no entry level programmer could write this code? WTF?? This code is “entry level”. The only reason I know it is because I know of all the .NET design practices that make this code shit. So, I was proud of shit code.

At this point I decided that I was going to going to make something useful out of this wasted time. I hadn’t thought of blogging about this (and, as I am blogging about this; I still don’t think of this as a useful means to my wasted time). But, I did think there must be a better way to look at the problem and find some usage from it.

It hit me immediately, I should make a comparison test. Something like a unit test, but not as useful. I should write a loop which will dynamically populate the integer array and when the elements to the left of the pointer are equal to the elements to the right of the pointer it will be a success:

var rand = new Random(DateTime.Now.Millisecond);
bool isEqual;
do
{
    int[] arr = new int[100];
    for (int i = 0; i < arr.Length; i++)
    {
        arr[i] = rand.Next(100);
    }

    isEqual = IsArrayEqual(arr, 37);
    Console.WriteLine("Are equal: {0}", isEqual);
} while (!isEqual);

The test worked around the 100000th try, but I was confused by the way my computer handled the test. I thought that my computer would eat up all processor time trying to produce a result. But it didn’t. It used 2 processors. And, my comp has 8 procs (Core i7). So, I decided to rewrite the test code to use the Parallel library in .NET 4.0.

That turned into a bit of a research mission. Apparently, I couldn’t use the Parallel library without a For loop. And, my algorithm was using a Do … While loop. What was I to do? After a little looking, I found that .NET 4.0 allowed for multi-threading through lamba expressions and anonymous functions. It wasn’t the same as a Parallel loop, but it allowed for multi-threading.

So, I added a wrapper function around the code and executed multiple threads using anonymous functions:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace FogCreekInternTest
{
    class Program
    {
        static void Main(string[] args)
        {
            
            int j = 0;
            var isEqual = false;
            int leftSum, rightSum;
            var rand = new Random(DateTime.Now.Millisecond);
            var found = false;

            for (int t = 0; t < 5; t++)
            {
                Task.Factory.StartNew<bool>((threadNumber) =>
                {
                    do
                    {
                        int[] arr = new int[100];
                        for (int i = 0; i < arr.Length; i++)
                        {
                            arr[i] = rand.Next(100);
                        }

                        isEqual = IsArrayValuesEqual(arr, 37, out leftSum, out rightSum);
                        Console.WriteLine("[{4}:{0}] Are equal: {1}\tleftSum: {2}, rightSum: {3}", j++, isEqual, leftSum, rightSum, threadNumber);
                    } while (isEqual == found);

                    found = true;
                    return isEqual;
                }, t );
            }

            Console.ReadKey();
        }

        static bool IsArrayValuesEqual(int[] arr, int splitIndex, out int leftSum, out int rightSum )
        {
            leftSum     = SliceSum(arr, 0, splitIndex - 1);
            rightSum    = SliceSum(arr, splitIndex + 1, arr.Length - 1);

            return leftSum == rightSum;
        }

        static int SliceSum(int[] arr, int startIndex, int endIndex)
        {
            int sum = 0;
            for (int i = startIndex; i < endIndex; i++)
                sum += arr[i];
            return sum;
        }
    }
}

With some testing, I discovered: With 1 thread I used 2 processors. With 2 threads I used 4 processors, with 3 threads I used 6, with 4 I used all 8. And with 5 threads I used all 8 to 80%.

In the end, I was able to do some real research; the parallel library in .NET 4.0 is pretty good. You just need to have a good reason to use it.

Now … How to think about it as an interviewer:

1. Giving programmers take home assignments is stupid.
2. Giving a coding test that you have to write out on paper is stupid.
3. Bringing an interviewee into the office without doing a basic “look over the shoulder” programming test is stupid.
4. Phone interviews are antiquated if you have the capability to remote desktop into a developers computer.
5. Asking a developer to solve one problem in front of you is more useful than asking a hundred “do you know about this” questions.
6. If a programmer can demonstrate ability while your looking over their shoulder; then the only question left to ask is “will you fit in with our development team”.
• Sidenote: “How much money do you want?” should be an initial question. Why waste time on a developer who has dreams of a Midas touch?