Tests for programmers - Part 2

Read this first: Tests for Programming Interview: Part 1.

In that first posting I talked about the success rate of people asked to perform a simple coding test of the sort I give to job candidates. The test is intended to be simple so it doesn't take long and can be done under stress, and it's not the end point, it's the starting point. It's the start of a conversation about coding in general.

However, before showing and talking about the code I received, here's the code as I would derive it. And I'm not just going to present you with code, I'm going to write it as you watch, with a commentary as I go.

This isn't the only way to write this code, it's the way I write this code.

Firstly, here at right is what we're given as a specification:

So my first thought is - I'm going to walk down the given string with a pointer, and copy out the data I want. That means I'll need two pointers, one for reading and one for writing:

     
  void condense_by_removing(
      char *z_terminated ,
      char char_to_remove
      ) {

    char *p_read;
    char *p_rite;

  }
    
  
 Write a C routine with the
 following prototype:

 void condense_by_removing(
     char *z_terminated ,
     char char_to_remove
     );

 Your routine should modify
 the given zero-terminated
 string in place, removing
 all instances of the given
 char.
 
     

  void condense_by_removing(
      char *z_terminated ,
      char char_to_remove
      ) {

    char *p_read = z_terminated;
    char *p_rite = z_terminated;

  }
     They will both start at the beginning of the given string, so I can initialise them now:

I'll carry on incrementing the read pointer down my string until I reach the end, which is a 0 char: 

  void condense_by_removing(
      char *z_terminated ,
      char char_to_remove
      ) {

    char *p_read = z_terminated;
    char *p_rite = z_terminated;

    while (*p_read) {

        // Do something

        p_read++;
    }

  }

The while test could be coded as (*p_read!='\0') but it's natural and idiomatic in C simply to test as I've written it. In other languages it's more natural to have the specific test rather than the implicit coercion.

    
 
I've noticed that this looks a bit like a while loop, but I'll deal with that later.

Trivia question: What is the difference between these two pieces of code?

  
while (condition)
  {
  // stuff
  i++;
  }
 		  
for (;condition;
      i++)
  {
  // stuff
  }
 

This is not what I would regard as a suitable question for interview. If you know it or don't, what does that tell me? It tells me that you know that small detail in a dusty corner of one specific language. It tells me nothing about your ability to solve problems, write code, or communicate effectively.  

Now for each character I look at, I'll decide if it should be copied to the destination:

There's a duplication there in the dereferencing of p_read, but a sensible compiler will keep it in a register anyway. I could explicitly copy it to a variable, but I won't.

     
  void condense_by_removing(
      char *z_terminated ,
      char char_to_remove
      ) {
    char *p_read = z_terminated;
    char *p_rite = z_terminated;

    while (*p_read) {
        if (*p_read != char_to_remove) {

            // Do the copy
        }
        p_read++;
    }
  }

  void condense_by_removing(
      char *z_terminated ,
      char char_to_remove
      ) {
    char *p_read = z_terminated;
    char *p_rite = z_terminated;

    while (*p_read) {
        if (*p_read != char_to_remove) {
            *p_rite++ = *p_read;
        }
        p_read++;
    }
  }
     If I don't want to copy the character in question I don't have to do anything, but if I do, then I copy it to the destination.

Finally, when I'm done, I need to terminate the destination. The terminating '\0' wasn't copied because that's when my while loop bailed out.

By the method I've used to derive the code I'm pretty sure it's right - the derivation itself is effectively a proof (of sorts) that it's doing what it needs to do, and satisfies the requirements. I have:

  • walked down the original string,
  • left behind anything I don't want,
  • taken everything I do want, and
  • terminated my result.

I could write some invariants and check it "properly," but I'm pretty confident.

     
  void condense_by_removing(
      char *z_terminated ,
      char char_to_remove
      ) {
    char *p_read = z_terminated;
    char *p_rite = z_terminated;

    while (*p_read) {

        if (*p_read != char_to_remove) {
            *p_rite++ = *p_read;
        }
        p_read++;
    }
    *p_rite = '\0';
  }


  void condense_by_removing(
      char *z_terminated ,
      char char_to_remove
      ) {
    char *p_read = z_terminated;
    char *p_rite = z_terminated;

    for (;*p_read;p_read++) {

        if (*p_read != char_to_remove) {
            *p_rite++ = *p_read;
        }
    }
    *p_rite = '\0';
  }
     So far so good. At least at this stage I hope I've proved that I can write code, and reason about it effectively.

Now I can start to mutate the code. Each of the following mutations is unnecessary, but valid for consideration.

Firstly, I notice that every time through the while loop p_read gets incremented. That means we could convert the while into a for and consider myself as looping over the elements of the input string.

We could also put the declaration and initialisation of p_read into the for loop:

Note that in older flavors of C the declaration inside the for loop wasn't possible.

     
  void condense_by_removing(
      char *z_terminated ,
      char char_to_remove
      ) {
    char *p_rite = z_terminated;

    for (char *p_read = z_terminated;*p_read;p_read++) {
        if (*p_read != char_to_remove) {
            *p_rite++ = *p_read;
        }
    }
    *p_rite = '\0';
  }

  void condense_by_removing(
      char *z_terminated ,
      char char_to_remove
      ) {

    for (
      char *p_read = z_terminated;
      *p_read;
      p_read++) {

        if (*p_read != char_to_remove) {
            *z_terminated++ = *p_read;
        }
    }
    *z_terminated = '\0';
  }
     Now I can observe that p_rite gets initialised to z_terminated and then z_terminated never gets referenced again, so we could just use z_terminated instead.

(I'm not going to get into arguments about the specifics of the formatting. Everyone has their own opinions, and there is rarely any common ground. It usually turns out to be less important than people think, and most people can adapt to a style that's at least acceptable to others, even if not preferred.)

As a final tweak, the braces are mostly unnecessary, and could be removed, and the names z_terminated, char_to_remove and p_read can be replaced with something more succinct:

Each of these changes is unnecessary and in some cases damage readability. Further, a good compiler will get most, if not all, of the efficiency for you without making these changes. Having said that, this final version of the for loop is quite idiomatic and natural for the experienced C coder.

Will all your future maintainers be experienced C coders?

     
  void condense_by_removing(
      char *str ,
      char remove
      ) {

    for (char *rd = str;*rd;rd++)
        if (*rd != remove)
            *str++ = *rd;

    *str = '\0';
  }

It is also worth noting, though, that this final version can be read quite simply as:

As a sanity check, being able to read your code like this is really useful. It's not always possible.

Plans for the next articles are:

I hope you found this interesting and plan to visit again.
Update: TestsForProgrammers_Part_3.html