Entries Tagged 'coding' ↓

We do initial phone screens where I work as part of our hiring process. It’s a great way of checking whether a candidate’s CV is fact or fiction before inviting them in for a full interview.

I never used to ask coding questions in my phone screen, on the basis that they’re difficult to administer over the phone and we’d be testing coding skills at an interview proper anyway. So instead I’d ask a range of theory questions: what’s the difference between a class and an object, what’s the efficiency of retrieval in a balanced binary search tree, that sort of thing.

That led to lots of candidates sailing through the phone screen only to fail miserably on the coding test in their full interview. It’s fascinating that many people with perfectly good CS theory and a long background in software development can’t actually write good code. So eventually, I added a coding question to my phone screen script.

Here’s the question I’m currently using:

Write a function that takes a single integer as input and returns a string that is the binary representation of that integer. For example, if the input is 20, the output is “10100″. You should complete the exercise in C/C++, Java or Perl. You may not use printf or similar functions.

I give them five minutes to complete the task then they have to read their code back to me over the phone.

This is a simple task - in Perl it’s a one-liner, even without sprintf - and it answers a range of questions including:

• Can the candidate understand and follow a simple spec?
• Do they understand binary?
• Can they use bitwise operators?
• Can they write good functional code?
• Can they write generalised code? (For example, do they make assumptions about the size of an integer.)

I look for answers where the syntax is perfect, although I’m more forgiving on semantic errors, provided the candidate can solve them when they’re pointed out. (A common error on the first implementation is to return a reversed string, for example.)

The test also reveals how well the candidate knows their language of choice. For example, candidates answering the question in C typically use a char* to store the result, but often forget to leave room for the trailing null byte; a pretty elemental requirement.

If you have five minutes and you’re up to the challenge, give this one a whirl and let me know how you got on.

At work we have a standard coding test that we give all of our prospective software developers to complete during their interview day. The coding test revolves around a simple card game, and one of the things candidates have to do is shuffle a deck of cards.

Shuffling a deck of cards, or more generally randomising the order of an array, is a pretty simple task and almost every candidate does it the same way. Here’s my (very simple) version, in Perl:

sub shuffle {
    my @array = @_;
    my $length = scalar(@array);

    for (my $i = 0; $i < $length; $i++) {
        my $r = int(rand() * $length);
        @array[$i, $r] = @array[$r, $i];
    }

    return @array;
}

That’s pretty much the algorithm that every candidate writes, including me when I sat the test. We call it the Knuth shuffle, because it was described by Donald Knuth in his book The Art of Computer Programming Vol 2: Seminumerical Algorithms.

So, everyone writes it like that. And everyone gets it wrong.

The first clue that the above implementation is flawed is in the numbers. Generating a random number between 1 and N and repeating that N times gives N^N possible execution paths, but there are only N! ways you can order the numbers 1 to N. This is a great example of where intuition can be confusing: it feels right that “every card gets the chance to be swapped with every other card”, but the numbers don’t back up the gut feeling.

I prefer to think of it another way; instead of thinking of a magician shuffling a deck of cards, think of lottery balls coming out of a lottery machine. You start with N balls. One is selected at random (N possible outcomes), then another (N-1), then another (N-2), and so on. If you continue until all the balls are selected you have this many possible outcomes:

N * (N-1) * (N-2) * … * 1

Or to put it another way:

1 * 2 * … * N = N!

Hurrah, N! outcomes!

In other words, for each element in the array, choose a random number between that element’s index and the last index in the deck, and swap the cards at those two indices. An easier way to do this in code is to iterate backwards from the last index to zero and generate a random number between zero and the current index, then swap those two indices:

sub shuffle {
    my @array = @_;
    my $length = scalar(@array);

    for (my $i = $length - 1; $i > 0; $i--) {
        my $r = int(rand() * $i);
        @array[$i, $r] = @array[$r, $i];
    }

    return @array;
}

And that’s the correct Knuth shuffle, exactly as he describes it himself:

Algorithm P (Shuffling). Let X₁, X₂, …, X_t be a set of t numbers to be shuffed.

P1. [Initialize.] Set j ← t.
P2. [Generate U.] Generate a random number U, uniformly distributed between zero and one.
P3. [Exchange.] Set k ← [jU] + 1. (Now k is a random integer, between 1 and j. Exchange X_k and X_j.
P4. [Decrease j.] Decrease j by 1. If j > 1, return to step P2.

The Art of Computer Programming, Volume 2: Seminumerical Algorithms, p145. Third Edition. DE Knuth.

Perl allows you to do all kinds of weird things to the semantics of the language. One such weird thing is the facility to override the default die handler in perl with something of your own design. The way it works is like so:

function some_func {
    local $SIG{__DIE__} = sub {
        my $error = shift;
        # do weird and wonderful stuff with $error here
    };
    # your code here
    die("there's nothing to live for");
}

Pretty cool, huh? Well, yes, but there are a couple of quirks to self-rolled die handlers that can cause you no end of pain.

Firstly, the keyword local should already have brought you out in a cold sweat. local gives a variable dynamic scope, which means that the variable holds until the block that contains it is popped back off the call stack. And that can really hurt if your code block calls other functions.

Consider a simple scenario: func1 defines a local die handler, then calls func2…

sub func1 {
    local $SIG{__DIE__} = sub {
        print STDERR $_[0]; exit(1)
    };

    # do something that might die here

    func2();
}

The die handler doesn’t just affect the stuff you do in func1, it affects anything that happens in func2, too. And if func2 calls functions itself, the die handler will apply while those functions are running as well, and the functions they call, and the functions they call…

Well that’s OK, you might think - I want my die handler to be called if anything dies. That’s why I wrote it! But that brings us to the second quirk.

You may have come across the use of eval blocks in perl as a means of emulating the try/catch blocks seen in some other languages, such as Java. Here’s a simple example:

eval {
    # do something that might die
};
if ($@) {
    # this is your catch block
    print STDERR "Something horrible happened: $@";
}

Using an eval block, then testing the value of $@ afterwards, lets you catch instances of die and handle them gracefully. Your code continues to run, unless you specifically state that it doesn’t inside the “catch” block. It’s a nifty trick, and it’s used a lot. For example, the XML::Simple CPAN module uses it to decide which XML parser to use:

eval { require XML::SAX; };      # We didn't need it until now
if($@) {                         # No XML::SAX - fall back to XML::Parser
  if($preferred_parser) {        # unless a SAX parser was expressly requested
    croak "XMLin() could not load XML::SAX";
  }
  return($self->build_tree_xml_parser($filename, $string));
}

Very cool.

Until, that is, you mix eval try/catch blocks with custom die handlers.

Why? Because custom die handlers run even if the die happened within an eval block. The perlvar perldoc calls this “an implementation glitch”. Yeah. What this means is that if you use a custom die handler in your code, and it contains a die or exit, you’ll trample all over any attempt to use eval for try/catch semantics anywhere else downstream of the block that declares the die handler! (I found this out the hard way - after an hour in the perl debugger trying to figure out why XML::Simple was crashing my code.)

Fortunately there is a workaround, albeit not a very elegant one: the variable $^S indicates whether code was called from within an eval block or not. So if you write a custom die handler, you should always check $^S, and die again if it’s set. (You can die within a die handler - the die handler doesn’t get called recursively.)

local $SIG{__DIE__} = sub {
    die @_ if $^S;
    # rest of the die handler goes here
}

Better still, don’t define your own die handlers! They’re rarely needed, you should use an eval block wherever possible to trap errors when they surface, rather than trying to affect the way they surface.