Interviewing programmers: coding test example explained • Hacker News Board

Re: Interviewing programmers: coding test example explained

#111

Post by Daniel_Newby » Thu, Jun 03, 2010, 6:13 PM UTC

loup-vaillant wrote: post #69

cperciva wrote: post #52

Earlier quoted context omitted.

Optimizing for performance, sure. But I was trying to optimize for character count. :-)

Yes, but in doing so, you traded a memory write for a branch. And memory accesses are linear, so that's likely faster than the cannon. So surely we could go further? That's how I got the idea.

Many compilers will implement

      d += *d != c;

with a branch, and depending on the data pattern the branch predictor will be bamboozled. The branchless version would involve a pair of subtractions and some bit banging.

Re: Interviewing programmers: coding test example explained

#112

Post by anatoly » Thu, Jun 03, 2010, 6:15 PM UTC

dkersten wrote: post #110

anatoly wrote: post #91

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…

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_…

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

#113

Post by nickelplate » Thu, Jun 03, 2010, 6:19 PM UTC

angrycoder wrote: post #73

nickelplate wrote: post #51

Earlier quoted context omitted.

I personally would count that against any candidate during an interview. I wouldn't necessarily reject them, but I would definitely count that against them. I work in Toronto, Ontario. English is not my native language, but I always do my best to ensure that my code or documentation is as close to crystal clear as possible. This starts with using correct spelling. Code is written first for humans to read, and to me m…

The counterpoint to this is that if you are they type of boss who would nit pick a candidate over something like this, he probably wouldn't want to work for you anyway. Especially when you take a quirky/cute spelling and try to expand it into inferring all sorts of other traits. It reminds me of people who say they would never hire a developer who doesn't write comments. Really? Writing comments is a precious skill t…

Except this is not a standards issue. It is a problem that can be solved in one sentence only if the programmer groks code construction to begin with. A lot of otherwise smart programmers - some of them very experienced - do not understand this stuff and do not develop good programming habits of the Code Complete kind. I probably exaggerated a little in my previous comment. Still, I always test for code construction "instincts" when I am interviewing a candidate. I may give the candidate a take home assignment - nothing difficult, as I really only want to see what the code looks like. Or I may ask the candidate to bring a sample of great code, and ask him why he thinks it is great. But I will always test for good habits, as they are too often taken for granted.

Re: Interviewing programmers: coding test example explained

#114

Post by ydant » Thu, Jun 03, 2010, 6:21 PM UTC

zb wrote: post #85

petercooper wrote: post #61

Turns out his solution is almost the same as mine except I skip the termination stage and instead read one character more in the loop which catches the \0 from the original end of the string automatically. As I'm not really a C programmer, was I doing something bad/unrecommended? It seemed to work.. :-)

What happens if you pass '\0' as the character to remove?

Like the grandparent, I do the same. I have the copy routine also copy over the final 0.

If you pass in 0 as the character to remove, it still works fine. Nothing is shifted, so the final 0 is copied and the string remains null terminated. Technically this could be undesirable behavior (it's contrary to the spec), but I don't think the behavior if you do pass in a 0 to remove could be easily defined. What does it copy into the place where the null was? How does it know where to stop? Easier to just assume it's remove any non-null character and asking to remove null means remove nothing.

Re: Interviewing programmers: coding test example explained

#115

Post by dkersten » Thu, Jun 03, 2010, 6:21 PM UTC

anatoly wrote: post #112

dkersten wrote: post #110

Earlier quoted context omitted.

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_…

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'.

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

#116

Post by nickelplate » Thu, Jun 03, 2010, 6:25 PM UTC

dkersten wrote: post #109

jemfinch wrote: post #55

Earlier quoted context omitted.

In that case, I'd suggest `p_rd` (well, IMO, just `rd` would suffice) and `p_wr`. Then they're both fairly unambiguous abbreviations.

I think p_wt is better than p_wr. Honestly though, aligning the length of variable names is, in my humble opinion, retarded - he should have went for p_read and p_write.

"aligning the length of variable names is, in my humble opinion, retarded"

I feel the same way.

Re: Interviewing programmers: coding test example explained

#117

Post by bkz » Thu, Jun 03, 2010, 6:31 PM UTC

Funny how readable Python is:

def condense(s, remove): return "".join([c for c in s if c != remove])

Cheating (2.6+): s.translate(None, remove)

Re: Interviewing programmers: coding test example explained

#118

Post by bnoordhuis » Thu, Jun 03, 2010, 6:38 PM UTC

Xurinos wrote: post #40

pvdm wrote: post #27

'\0' is null-terminated NOT zero-terminated, no ? By definition, a string in C is always null-terminated.

As it happens, '\0' translates to 0. Since they are composed of characters, C programmers tend to do the c == '\0' check instead of the shorted c == 0 check, just to make sure everyone knows we are still treating the char like a character in a string; it is just style. char c = 65 is equivalent to and just as legal as char c = 'A' So yes, C strings ARE zero-terminated. In fact, it is a bit weird to say they are null-…

Sorry, but I can't help to nitpick: 65 is not an 'A' on systems that use EBCDIC, like z/OS and OS/400. It's not even a valid character as such, I think.

Re: Interviewing programmers: coding test example explained

#119

Post by Vocalspace » Thu, Jun 03, 2010, 6:47 PM UTC

Sadly, the code YOU wrote is suboptimal. It doesn't check for bad pointers, has no comments, doesn't take memory corruption into consideration, and assumes the replacement character is not '\0'.

You would get a C- if I graded your test.

Now you'll argue that it's just a test, but the fact is your best work should not come only when under unexpected scrutiny, as it does with impromptu tests, it should be a mental process that is not bypassed for any reason.

In this case you've thought about it for weeks and still botched it.

Kudos for trying. We'll call you if we are interested.

Re: Interviewing programmers: coding test example explained

#120

Post by ori_b » Thu, Jun 03, 2010, 6:48 PM UTC

jemfinch wrote: post #55

ComSubVie wrote: post #12

Earlier quoted context omitted.

I think he used p_rite so that the variable names length is identical to p_read, which can make the code look more pretty.

In that case, I'd suggest `p_rd` (well, IMO, just `rd` would suffice) and `p_wr`. Then they're both fairly unambiguous abbreviations.

I'd probably go with just 'r' and 'w', or 'src' and 'dst'