Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Interviewing programmers: coding test example explained

solipsys.co.uk

Post reply on HN
Print view View original

171–178 of 178 posts

Re: Interviewing programmers: coding test example explained

#171

Post by RiderOfGiraffes »

gorrepati wrote: post #165
loup-vaillant wrote: post #50

Earlier quoted context omitted.

Here is the same code, without syntactic obfuscation: void condense_by_removing(char* s, char c) { char* d = s; while (*d = *s++) d += *d != c; } I would have sworn I found a bug. There is none. Brilliant. 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().

I get access violation with VC, when trying to see how this works. Works with gcc though. Can somebody throw some light on how this works?

  void condense_by_removing(char* s, char c)
  {
    char* d = s;
    while (*d = *s++)
      d += *d != c;
  }
It always does the copy, then evaluates *d!=c. If what it just copied is equal to the forbidden character this evaluates as false, which in C is 0, and hence d is left unchanged.

If what it copied is not equal then this evaluates as true, which is 1, and hence d is incremented.

Re: Interviewing programmers: coding test example explained

#173

Post by loup-vaillant »

jemfinch wrote: post #58
loup-vaillant wrote: post #20

And I thought my solution was as simple as possible. If only I decoupled my two increments, I may have avoided this unreadable, inefficient crap: void remove_char(char *s ,char c) { int from = -1; int to = -1; do { from++; to++; while (s[from] == c) from ++; s[to] = s[from]; } while (s[from] != '\0'); } Maybe that's why simplicity doesn't actually rule: it's hard to find. Or, people are silly (including myself in thi…

Your code also fails (i.e., reads and writes past the end of the string) if c == '\0' and s is "\0".

I considered the `c=='\0'` case bogus anyway, so I was OK with a partial function. (I wouldn't have been for production code, though.)

Re: Interviewing programmers: coding test example explained

#174

Post by RiderOfGiraffes »

loup-vaillant wrote: post #173
jemfinch wrote: post #58

Earlier quoted context omitted.

Your code also fails (i.e., reads and writes past the end of the string) if c == '\0' and s is "\0".

I considered the `c=='\0'` case bogus anyway, so I was OK with a partial function. (I wouldn't have been for production code, though.)

Are you saying that you actually considered that case, and then wrote code that didn't deal with it?

Re: Interviewing programmers: coding test example explained

#175

Post by loup-vaillant »

RiderOfGiraffes wrote: post #174
loup-vaillant wrote: post #173

Earlier quoted context omitted.

I considered the `c=='\0'` case bogus anyway, so I was OK with a partial function. (I wouldn't have been for production code, though.)

Are you saying that you actually considered that case, and then wrote code that didn't deal with it?

Yes I did, and then yes I did.

I didn't fully investigated that case, but I suspected there could be a problem with `c=='\0'`. I suspected that the `while (s[from] == c) from ++;` line could shoot past the termination '\0' and trigger a buffer overflow.

But I didn't fully investigate, on the grounds that no sane programmer would want to remove a character that's never in a C string. In other words, I considered it was not part of the specification.

In production code, I would have either thrown an exception, or returned early. And I would have asked around to know which I would chose.

Could my attitude have influenced my chances, if I had applied?

Re: Interviewing programmers: coding test example explained

#176

Post by pbiggar »

loup-vaillant wrote: post #50
cperciva wrote: post #37

I'm sure RiderOfGiraffes doesn't want a third entry from me at this point, so I figure I might as well just post it here: #define C char #define F for #define R condense_by_removing #define V void V R(C*A,C B){F(C*J=A;*J=*A++;J+=*J!=B);} or without #defines: void condense_by_removing(char*A,char B){for(char*J=A;*J=*A++;J+=*J!=B);}

Here is the same code, without syntactic obfuscation: void condense_by_removing(char* s, char c) { char* d = s; while (*d = *s++) d += *d != c; } I would have sworn I found a bug. There is none. Brilliant. 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().

I believe there is a bug here. If the first character is an instance of c, then it will still be copied. For example, calling the function as condense_by_removing ("loup-vailiant", 'l'), will return "loup-vaiiant", where it should return "oup-vaiiant".

(I've not tested this though, I may be wrong.)

Re: Interviewing programmers: coding test example explained

#177

Post by chrisbuchino »

I have hired (and fired) a lot of software developers and cannot stress enough the importance of having candidates write code up-front. Having made poor hiring decisions myself by not doing this well and having "inherited" team members who whose coding skills left something to be desired, I would argue that few things are as crippling to an organization as bad programmers. Someone can be the nicest person ever, but if they don't write code well - they will cost you in time, money, and unnecessary technical debt.

I don't agree that FizzBuzz tests are the ways to screen developers though. These types of questions may give insight into IQ but I've seen really bright people be really sloppy coders. The way the problem is solved is just as important as getting the problem right and making it fast. If it isn't readable, you better hope that person does not get hit by a bus because if you need to modify it later, you're in trouble.

Re: Interviewing programmers: coding test example explained

#178

Post by smcl »

RiderOfGiraffes wrote: post #135
gjm11 wrote: post #134

Earlier quoted context omitted.

> I wonder if anyone has provided a suitable Hoare triple for C's for loop. Basically the same as for a while loop, as given e.g. at http://en.wikipedia.org/wiki/Hoare_logic since (apart from the behaviour of continue) for (inits; cond; steps) { body } and inits; while (cond) { body; steps } are equivalent. And if you do want to deal with continue (and presumably also break) the Hoare stuff gets awfully cumbersome; y…

You should write that up as a proper tutorial - I'm pretty sure a few people here would find it interesting.

Should I be concerned that I've never encountered these Hoare Triples before in my life?
Post reply on HN