Interviewing programmers: coding test example explained (solipsys.co.uk)

  1) In TFA, s/cersion/version/,
     but that's an amusing typo.
     :-)

See also: http://en.wikipedia.org/wiki/Muphrys_Law

This is the source of the notorious "fgets" bug/hack/exploit.

This is not the time or place for a tutorial on C strings and memory management, but suffice to say that some people find it horrible, some people find it easy and obvious. It stems from C being a sort of macro-assembler with a simplistic type system glued on top of it.

ADDED IN EDIT: I don't know why you got down-voted - it's a reasonable question from someone who hasn't done C. I've up-voted you to get you back to "1".

Memory management is between you, malloc() and free().

Assuming this were malloc()d memory, if you wanted to free up the unused bytes, you'd probably:

  char *condensed = strdup(z_terminated);
  if (condensed)
    free(z_terminated);
  else
    // out of memory

Because the resulting string will only be shorter (never longer), this works. You simply keep track of where you're copying to and where you're copying from, and move character by character until you reach the end. The resulting string may have extra stuff at the end, but since it's null terminated the standard C string functions will not see that cruft as they will stop at the first null.

Some people allocated memory, copied out the input, then put back the bits they wanted to keep. That is not "in place".

But z_terminated is a pointer to a lump of memory that contains bytes. In that context "in-place" means that you move things around in the lump of memory you are given (the one pointed to by z_terminated) rather than allocating some more memory and using that.

If I'm right, your misconception is by no means unique, but it's a dangerous one that shows that you don't understand what's going on in C with regards pointers, memory and strings.

If I'm wrong then I apologise.

This is also why quicksort is considered to take up log(n) space: it calls itself recursively, and thus uses up a bit of the stack for each recursive call.

Also, C strings are NUL-terminated, not NULL-terminated. (char)(0) is the NUL character; (void * )(0) is the NULL pointer (usually).

  char c = 65

  char c = 'A'

For some reason, I vaguely remember some security hack in one OS where NULL went to a special place in memory that was marked as invalid (1, 63, or something), so in that case, NULL was not defined as 0. Since the memory is vague, though, don't quote me on it.

  void condense_by_removing(char* s, char c)
  {
    char* d = s;
    while (*d = *s++)
      d += *d != c;
  }

Now, I wonder if we could further optimize it. For instance by accessing memory several bytes at a time, in a fashion similar to strcmp().

    >hello|goodbye
    >| 
    >>Result is 'hello|goodbye'

    >That's a nice dog you have there.
    >.
    >>Result is ''

    my $pattern = '\\'.substr($in,0,1);
    $in =~ s/$pattern//g;

Whenever you see a `for` loop, it tells you something that a `while` loop doesn't. It tells you the kind of loop you're about to do.

A `for` (usually) means you're going to be looping over an array, with a specific length, with a specific "step" (usually one). This is information you immediately get by seeing a `for`.

Moreover, you get all the information about how the loop looks (what you're looping over, size of the array, other actions you intend to perform in the loop) all in one place. This especially helps when you're looking at a large piece of code, in which case your example of "while (cond) {...;inc;}" would have a lot of lines between the condition and the increment.

  void condense_by_removing(char* z_terminated, char char_to_remove) {
    int index;
    int write = 0;
    for (index = 0; z_terminated[index]; ++index) {
      if (z_terminated[index + write] == char_to_remove) {
        ++write;
      }
      if (write > 0) {
        z_terminated[index] = z_terminated[index + write];
      }
    }
  }

  void condense_by_removing(char* z_terminated, char char_to_remove) {
    int write = 0;
    for (; *z_terminated; ++z_terminated) {
      if (*(z_terminated + write) == char_to_remove) {
        ++write;
      }
      if (write > 0) {
        *z_terminated = *(z_terminated + write);
      }
    }
  }

My test harness isn't perfect, but with "gcc -O3" on a Core i7, I get something like 20000 cycles to 'condense' a 4096 character random string with the suggested loop, versus 26000 with your more complex approach.

With a 4096 character string set up to never contain char_to_remove, I get a practically identical 19500 cycles with both approaches.

Thus there seems to be no benefit to the greater complexity.

The problem is that the hiring process is necessarily ineffective. You have a very short period of time to come to a sweeping conclusion about the entirety of someone's capabilities. Dev interviewers do a notoriously crappy job at this.

The specific problem "FizzBuzz" tests solve is this: candidates who can talk about development (including people who know that the difference between otherwise equivalent for() and while() statements is whether the increment runs when you hit a "continue"), but who, when asked to sit down and code something, fumble horribly.

These people, all of whom are smart and extremely knowledgeable about software development, have not developed the real world programming survival skill of being able to sit down and just code when they need to. Most development shops want to avoid these people. Hence: a test that isolates specifically your ability to just start coding, apart from any domain knowledge or computer science.

Believe it. A friend of mine once got a job as a Cobol programmer (he didn't know Cobol but said he did). He managed to bluff his way through the job until the company went bankrupt 6 months later!

Also, when you're hiring, you're getting a skewed picture of the overall programming population. Suppose (to make the math easy) that there are 100,000 programmers in the world, 90% of which are employed. So that leaves 10,000 programmers in the candidate pool. Most of the top 20% of those will be able to get a job from a referral and not go through a "normal" hiring process, so if you're screening resumes you're now down to the next 80%. But that's the bottom 80% of the 10% that's looking for a job. Of those, some are competent people between jobs or looking for a change, but a lot of them are just in the bottom 10% of the overall skill level, are basically unhirable, and are semi-permanently on the job market because of that.

To make another simplification, if you and I both screen 100 resumes in the same area, there's a reasonable chance that the 10 best candidates we see are different since they go off the market so quickly, but that the 10 worst candidates we see are the same, since they stay on the market. And unfortunately, some of those totally unhirable people have good-looking resumes.

The pythonic version would be s.replace(c, '')

However, I wonder if you've actually taken on board either the point of the exercise, or the fact that it isn't yet finished.

However, questions such as those you raise are, of course, of great interest in production code, and would be raised in the discussion this code is intended to start. If someone started to write correct code that took these things into consideration the test would be stopped - it would've served its purpose already.

I'd be interested to know:

* Do you think every routine, every piece of code should have comments?

* Do you think every routine should test its input parameters? Every time?

* Do you think every routine should be checking for memory corruption? All the time?

* How do you cope with memory corruption in the program code itself?

* Do you think the routine fails if the char to remove is '\0'? Are you sure? You seem to claim it does.

* Do you believe that all code should always be written to the same standard?

Having written code in an environment where any given memory location has a MTC (Mean Time to Corruption) of 12 hours, I have considered these issues. I'd be interested to hear your experiences in these matters.

I notice also that you created your username specifically to reply to this item.

Welcome to Hacker News.

C is a foot-shooting language. Its basic library functions are expected to do what you tell them to do, even when it's a really bad idea. Checking for bad pointers (and how exactly you define "bad" is a rather interesting question) is clearly out of scope.

has no comments

True, but I'm not convinced there's much point on such a trivial piece of code.

doesn't take memory corruption into consideration

Given that there is no redundant information available, this is an impossible challenge.

and assumes the replacement character is not '\0'.

Try re-reading the code a bit more closely.

Does the copious prose not count?

Care to elaborate on how you would've prepared a similar test?