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

151–160 of 178 posts

Re: Interviewing programmers: coding test example explained

#151

Post by cperciva »

avar wrote: post #146
cperciva wrote: post #127

Earlier quoted context omitted.

Whoops, I forgot the point I was trying to make. NULL is (void * )(0), but the code void * p; memset(&p, 0, sizeof(p)); assert(p == NULL); isn't necessarily valid, since the binary representation of NULL isn't necessarily as a sequence of zeroes -- even though everybody writes code which assumes that it is.

Yeah, that's unportable. Although I'm not aware of any system where it doesn't work. For the record, regarding 0 in pointer context the C standard has this to say: An integral constant expression with the value 0, or such an expression cast to type void * , is called a null pointer constant. If a null pointer constant is assigned to or compared for equality to a pointer, the constant is converted to a pointer of that…

Yeah, that's unportable. Although I'm not aware of any system where it doesn't work.

Right. I was considering changing this in FreeBSD last year in order to prevent map-at-NULL kernel exploits, but cooler heads prevailed (and pointed out to me how much code such a change would break).

Re: Interviewing programmers: coding test example explained

#152

Post by JoachimSchipper »

nuxi wrote: post #138
cperciva wrote: post #126

Earlier quoted context omitted.

Huh, you're right. I wonder when they changed that.

They didn't, it's there from at least ANSI C89 (ISO C90): "A byte with all bits set to 0, called the null character, shall exist in the basic execution character set; it is used to terminate a character string literal."

I think the rationale is in EBCDIC support; the C standard didn't want to/couldn't mandate ASCII, and therefore could not use the ASCII NUL character.

I honestly don't know whether POSIX/SUS mandates ASCII.

Re: Interviewing programmers: coding test example explained

#153

Post by RiderOfGiraffes »

Retric wrote: post #86
RiderOfGiraffes wrote: post #57

Earlier quoted context omitted.

The main point is as you quote. Secondary points are to see if the candidate can understand common expressions and idioms, and if not, either to look them up, or to ask. As it says elsewhere, the purpose is to get some code, then use it as a start for the discussion. If someone allocates memory then that's where I start. In that case they clearly they don't understand the usual meaning of the expression "in-place." >…

Some people allocated memory, copied out the input, then put back the bits they wanted to keep. That is not "in place". "Some people" implies more than one. I would have done it in place because that was the simplest approach and not doing so would have been silly. However, just because it seems that way to us does not mean everyone knew you required more than just output in that fashion. Anyway, I was more commentin…

A few things.

Firstly, thanks for being constructive. Your points are noted, although I don't necessarily agree with all of them.

To me, "some people" does not imply strictly more than one. That's possibly a mathematician thing.

But the point about mixing implementation detail and interface requirements, this is normal in much of the coding I do. I'm often working in a constrained environment, and performance requirements are very much a part of the specification. Stating that something must happen "in place" is a common requirement for me, and goes beyond saying "must not malloc" or whatever. More, it's having someone being able to cope with the mix that I was, in part, looking for.

I'm also well aware that many of the people here on HN do big machine programming, or web programming, and aren't accustomed to constrained programming. That's partly why I chose this particular question. My next challenge won't have that sort of constraint, and will be more in line with your comments. (Yes, sucker that I am, I'm planning another small exercise by way of comparison/contrast).

And again, these are the sorts of questions that I would expect to discuss during the de-brief. The very fact that you bring them up at all means you are in the top 0.01% of programmers (for some value of 0.01).

Re: Interviewing programmers: coding test example explained

#154

Post by philwelch »

rlpb wrote: post #90
djb_hackernews wrote: post #11

hmm, is it normal to assume all strings in C are \0 terminated? What are the memory usage implications for that? I won't pretend to know C but suppose you have a string that is 'ab{100}\0' and you wanted to remove all of the bs, you'd end up with 'a\0b{99}\0' in memory correct?

It's convention for C strings to be \0 terminated, and the standard library expects this just about everywhere (along with the kernel and just about everything else you might want to interface with). If you wanted to store a string as a (length, data) pair you could do that too, but you'd have to write most of your own string manipulation functions.

Interestingly, if you did store your string as (length, data) pairs, strlen would be an O(1) rather than an O(n), which would also impact strcat. Also, strtok could possibly become non-destructive.

The length value of the pair could be an 8 bit character value at the beginning of the array (which is how Pascal did it). That limits you to strings of length 255. If you represented strings as a struct containing an integer length and a char * pointing to the head of the array, the size limit of a string would in fact be no less than the limit of the length of any addressable array anyway. (Assuming that the head of the array is at memory address 1, the farthest it could possibly stretch is to the highest addressable memory value for an n-bit pointer. So an n-bit integer for the length value would clearly suffice.)

Re: Interviewing programmers: coding test example explained

#155

Post by philwelch »

aplusbi wrote: post #9
grogers wrote: post #6

Interesting, when I solved the problem originally on my own, I got to the exact same solution just with different variable names and braces. I suspect that this is probably the most common way to solve it.

Yeah, I had almost exactly the same code. I'm sure most people did too. The only other "obvious" algorithm is the n^2 one.

You can use an inner loop to skip over removable chars in the source string but I didn't think that was n^2. (Code below for reference.) Am I wrong that my solution is n, or is there another obvious n^2 algorithm?

  void condense_by_removing( char *z_terminated , char char_to_remove)
  {
    char * sp;
    char * dp;
    sp = dp = z_terminated;
    while (*sp != '\0') {
      while (*sp == char_to_remove){
        sp++;
      }
      *dp = *sp;
      dp++;
      sp++;
    } 
    *dp = *sp;
  }

Re: Interviewing programmers: coding test example explained

#156

Post by baddox »

tptacek wrote: post #104
rottencupcakes wrote: post #92

So, I've never been involved in hiring, so I have no perspective on the state of the job market. However, I have trouble believing that anyone who would be willing to rep themselves as a "C Developer" couldn't write this particular piece of code in a manner similar to the author's solution in a matter of minutes. Do these FizzBuzz articles keep getting promoted to the front page to boost everyone's collective egos, o…

The problem isn't the job market --- although it is pitiful, and it is dreadfully hard to hire talented developers, particularly in C. 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 t…

This seems a little silly, or perhaps just overly optimistic. If I have a lot of real computer science knowledge and understanding, I should be able to get an entry-level software development job (assuming there are enough or close to enough to go around). I don't think this particular problem is too unrealistic to expect a CS graduate with zero experience to get right, but I think it's unrealistic for an employer to expect entry-level applicants to know a whole lot about how enterprise development works. That's why they have training (fairly well-structured and comprehensive training, from what I've read) for new hirees.

Re: Interviewing programmers: coding test example explained

#157

Post by tptacek »

baddox wrote: post #156
tptacek wrote: post #104

Earlier quoted context omitted.

The problem isn't the job market --- although it is pitiful, and it is dreadfully hard to hire talented developers, particularly in C. 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 t…

This seems a little silly, or perhaps just overly optimistic. If I have a lot of real computer science knowledge and understanding, I should be able to get an entry-level software development job (assuming there are enough or close to enough to go around). I don't think this particular problem is too unrealistic to expect a CS graduate with zero experience to get right, but I think it's unrealistic for an employer to…

The exercise has very little to do with experience or knowledge. Think of it as a sort of personality test. It isn't, but it helps to think of it that way.

Re: Interviewing programmers: coding test example explained

#158

Post by nkurz »

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

#159

Post by nuxi »

Vocalspace wrote: post #119

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

But none of the things you mention were part of the requirement. Furthermore, I'd be interested to know how one checks for "bad pointers" and what exactly _you_ mean by that - just NULL, pointers to read-only memory/string literals, or something else (as far as C is concerned, there are no "bad pointers", the system underneath may disagree though).

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

Re: Interviewing programmers: coding test example explained

#160

Post by nuxi »

JoachimSchipper wrote: post #152
nuxi wrote: post #138

Earlier quoted context omitted.

They didn't, it's there from at least ANSI C89 (ISO C90): "A byte with all bits set to 0, called the null character, shall exist in the basic execution character set; it is used to terminate a character string literal."

I think the rationale is in EBCDIC support; the C standard didn't want to/couldn't mandate ASCII, and therefore could not use the ASCII NUL character. I honestly don't know whether POSIX/SUS mandates ASCII.

As far as I understand, no: http://www.opengroup.org/onlinepubs/000095399/xrat/xbd_chap0...
Post reply on HN