News for hackers. Stuff that matters.
Re:Interviewing programmers: coding test example explained by anatoly on Thursday June 03, 2010 @12:52PM (#1401804)
Interesting. I didn't try to do the assignment when I read the first part, but just tried it now before looking at the second part. When I started to write the main loop, I felt uneasy when I realized I'd be doing unnecessary copying in the common case when char_to_remove is never found. My code ended up a tad more complex than yours due to desire to avoid that:

  void condense_by_removing(char *z_terminated, char char_to_remove) {
    char *p = z_terminated;
    for (; *z_terminated != 0; ++z_terminated) {
      if (*z_terminated != char_to_remove) {
        if (z_terminated != p) *p = *z_terminated;
        p++;
      }
     }
     if (*p != 0) *p = 0;
  }
Re:Interviewing programmers: coding test example explained by dkersten on Thursday June 03, 2010 @02:05PM (#1401992)
This is what I came up with, but I'm not a C programmer.

  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];
      }
    }
  }
Or, getting rid of index:

  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);
      }
    }
  }
Re:Interviewing programmers: coding test example explained by anatoly on Thursday June 03, 2010 @02:15PM (#1402024)
I see what you're trying to do, but it won't work this way. Since your termination condition is z_terminated[index], you must never look beyond index, yet you access [index+write]. This alone means the code's buggy. The second version is similarly flawed.

Note that your code instantly becomes much easier to understand if you rename the variable 'write' to 'gap'.

Re:Interviewing programmers: coding test example explained by dkersten on Thursday June 03, 2010 @02:21PM (#1402040)
Ehh, good point. :-/

The second version is identical to the first, except that it ises the z_terminated pointer instead of a separate index.

  void condense_by_removing(char* z_terminated, char char_to_remove) {
    int gap = 0;
    for (; *(z_terminated + gap); ++z_terminated) {
      if (*(z_terminated + gap) == char_to_remove) {
        ++gap;
      }
      if (gap > 0) {
        *z_terminated = *(z_terminated + gap);
      }
    }
    *z_terminated = 0;
  }
Interestingly enough, if I try to remove the common *(z_terminated + gap) expression (which a good compiler should do for me..), I end up with a two pointer version similar to yours.
Re:Interviewing programmers: coding test example explained by dkersten on Thursday June 03, 2010 @04:52PM (#1402507)
Replacing the 3 additions of gapin the loop with a single subtraction (and an increment):

  void condense_by_removing(char* z_terminated, char char_to_remove) {
    int offset = 0;
    for (; *z_terminated; ++z_terminated) {
      if (*z_terminated == char_to_remove) {
            ++offset;
            ++z_terminated;
      }
      if (offset > 0) *(z_terminated - offset) = *z_terminated;
    }
    *(z_terminated - offset) = 0;
  }
Re:Interviewing programmers: coding test example explained by RiderOfGiraffes on Thursday June 03, 2010 @03:13PM (#1402206)
Have you sent it in? You should ...
Re:Interviewing programmers: coding test example explained by dkersten on Thursday June 03, 2010 @04:19PM (#1402408)
I missed your post the first time around and only did that today, so I assumed it was too late to send in.
Re:Interviewing programmers: coding test example explained by nkurz on Friday June 04, 2010 @12:14AM (#1403468)
This might be a case where one should benchmark before making changes that make the code more complex. I just threw your code your code into a thrown together cycle counter, and on my system it performs significantly worse than the straightforward solution.

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.

Re:Interviewing programmers: coding test example explained by RiderOfGiraffes on Thursday June 03, 2010 @03:12PM (#1402199)
Have you sent that in? You should ...