Interviewing programmers: coding test example explained
solipsys.co.uk
solipsys.co.uk
In the industry I work in --- computer software --- it is ludicrously hard to find people competant in C programming, and I'm inclined to ignore idiosyncratic spelling in source code.
Take this scenario: You have a single position you are interviewing people for. You've got two candidates with entirely even qualifications. The only perceivable difference between them is that one of them writes interview code with variable names spelled like in the original post. The other guy spells things the way you would expect. I'm willing to bet you'd end up hiring the second guy. Sounds like an "autoding" to me. Or would you argue that you would not do that?
My point was, spelling in variable names is only a very minor factor when deciding on hiring or not hiring a candidate. If his reasoning and experience and work ethic etc. are all ok, spelling wouldn't make those factors irrelevant.
When a factor is automatically excluding, that means that no matter how good in other respects the candidate is, I still wouldn't hire him (for example someone with a swastika tattooed on his face applying for a customer-facing job). I never suggested any such a thing anywhere (and I don't think you're claiming I am). So I don't see how you're coming to the conclusion that I think that making spelling mistakes automatically excludes a candidate.
In reality, you never have two candidates who are absolutely equivalent except for spelling ability. The interview process is extremely high-error, brutally timeboxed, and infamously ineffective. The most important capability you need to assess is "ability to code". You know a priori you're going to do a crappy job assessing that capability.
Whether or not he thinks you should be wasting time on trivialities like variable name spelling (I myself would dodge this problem by using names like "x" and "cp" for utterly trivial, well-known example problems like this), I don't know. My bias is pretty clear.
Under that definition, I don't see any way to construe my earlier remarks as meaning that I would such a high importance on spelling of variable names.
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 that takes years to develop? You just tell someone, if you work here, you need to write comments. Problem solved in one sentence. Same with variable names. Its a standards issue, nothing more, nothing less.
The relevant chapters in Code Complete may help you understand how much more complicated the subject is than that. (It may also fix your apparent belief that comments are necessarily a good thing.)
In any case I don't care whether people can quote from Code Complete. What I care about is that they have good enough instincts that they can wind up writing reasonable code that I'd like to maintain. If you don't understand why people would want function names that describe what a function actually does, I don't want to maintain your code. Nor, in the long run, are you likely to be productive.
But it is a bar to meet, not a standard to judge by. Once you've met that bar, I don't care about the difference between OK, and best in the world. I'm on to caring about other things. Like productivity. Code quality and productivity isn't either/or. It is an and. (I've had to clean up enough after the super-productive producer of crap, and don't want to do it again.)
I feel the same way.
See also: http://en.wikipedia.org/wiki/Muphrys_Law
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, or is the job market really this pitiful? Can someone who has been involved in hiring recently comment with some anecdotal evidence as to what they've seen?
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.
Often because they've had PLENTY of time to work on their resume and plenty of feedback on what works and doesn't (for small values of "works")
I've never quite understood C programmers' love of the `for` loop. It's just a `while` loop with the different parts stuck in different places (`init; while (cond) { ...; inc; }` is the same as `for(init; cond; inc) { ...; }`) and it doesn't (at least for me) result in any greater clarity or ease in reasoning.
EDIT: K&R says (page 60 in my second edition):
""" The for statement
for (expr1; expr2; expr3)
statement
expr1;
while (expr2) {
statement
expr3;
}
So apparently the trivia is the behavior of `continue`, which I think most C programmers (including myself) would know implicitly, even if we couldn't answer the question itself.
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.
I won't disagree with that in theory, but I don't really think the "for" loop is the solution. The real solution, I think, is a "foreach" construct (whether it's a loop built into the language (á la Java/C#) or a higher-order function (á la C++'s std::for_each), I don't really care) for iterating over arrays and other collections.
In practice, I think the for loop is too often abused for too little gain, and I think C would be a better language without it.
As an aside, I wonder if anyone has provided a suitable Hoare triple for C's for loop. I have an idea of what it would look like, but would love to see someone else's efforts to verify my own internalized one.
By the way, I don't know what a Hoare triple is, and reading a little on Wikipedia didn't enlighten me. Any chance for an explanation?
Basically, the (relevant) state of the computation is represented as a set of logical propositions which are true before a statement, and a set of logical propositions which are true after the statement. For each kind of statement the language supports (`if` statements, `while` statements, etc.) there are natural ways to reason about those triples.
Do you understand the "While rule" on the link above? I can explain it in natural language, but I'd rather not expend the effort if it's not something you've already seen.
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 }
inits;
while (cond) { body; steps }
Oh, all right, here's how you do it. Suppose you have the following three Hoare triples.
{P & Q0 & !cond}
body; steps
{P & body never invoked break or continue}
{P & Q1 & !cond}
body
{P & body invoked continue}
{P & Q2 & !cond}
body
{R & body invoked break}
{P0}
inits;
{P}
{P0}
for (inits; cond; steps) body
{R | (P & !cond)}
for (char * rd=str; *rd; ++rd) {
if (*rd != remove) *str++ = *rd;
}
*str = '\0';
P0: str points to a zero-terminated string. P: so does rd, rd and str point to tails of the original string, rd >= str, and what's between original_str and str consists of an appropriately crunched version of what was originally between original_str and rd. Q0,Q1,Q2: true,false,false. R: not needed.
We deduce that at the end of the for loop, rd points to a tail of the original string (P), it also points to a zero character (!cond), hence it points to the end of the original string. Hence what's between original_str and str consists of an appropriately crunched version of the entire original string. Hence all we need do is put on the final zero character, and we're finished.
#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);}
void condense_by_removing(char*A,char B){for(char*J=A;*J=*A++;J+=*J!=B);} 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().
d += *d != c;
However, code like this:
if (x == 14) {
y = 10;
} else {
y = 20;
}
Here's the code I tested. I think it works, but I barely checked it. I'm sure there are better ways to calculate 'increment'. Not sure if these would be enough to close the gap, though.
void condense_by_removing_branchless(char *z_terminated, char char_to_remove) {
char *condensed = z_terminated;
while (*z_terminated) {
*condensed = *z_terminated;
int diff = *condensed - char_to_remove;
int increment = -((diff | -diff) >> ((sizeof(int) * 8) - 1));
condensed += increment;
z_terminated++;
}
*condensed = 0;
}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;
}
If what it copied is not equal then this evaluates as true, which is 1, and hence d is incremented.
(I've not tested this though, I may be wrong.)
As in the article, I started simple and condensed to the version that I actually submitted. In hindsight, I wonder if that is the best approach when answering an interview question via email. In person, there's obvious benefit to walking through optimization (of all sorts, including visual), but if all the other party sees is the final version, they lose out on that demonstration of the process. If you were to receive just the more condensed version from an interviewee, would that be a benefit or detriment to the person? Does it make sense to send an analysis, or is that just risking overwhelming the interviewer?
I've asked for non-specific code samples in interviews before and that did serve to weed out an applicant once, but only because they sent on very easily searched for code (public API example code from a big developer). Asking for any sort of code example or coding example from an interviewer who isn't in the room always introduces the opportunity for cheating. Getting an analysis (I started here and ended up here) would probably help assuage my suspicions.
It does require someone to think like a C programmer: handling buffers directly, in-place modification and using NULL terminators to end strings that may have memory allocated beyond the NULL. I think it's a great question, but I don't know how well it would go over with CS undergrad students coming out with a Java only background.
Should I look for an equivalent simplistic Java question or stick to the guns and require candidates to know C? (I know the answer for my own team, but curious on others thoughts)
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?
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 memoryThe 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.)
Edit: Correction... I also copy the '\0' character before exiting instead of making that a separate step. It has to do with the order of things. Here is the code:
char* read_ptr = s;
do {
if (*read_ptr != c) {
*s++ = *read_ptr;
}
} while (*read_ptr++ != '\0'); 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;
}#!/usr/bin/perl
$in = <STDIN>;
$remove = <STDIN>;
chomp ($remove);
chomp ($in);
$in =~ s/$remove//g;
>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;
$in =~ s/\Q$remove\E//g;
perl -pe'BEGIN { $x = quotemeta(shift) } s/$x//g;'
I was hoping to be able to use tr///, since it seems like it was built for this, but it creates its conversion tables at compile time, so there's no chance to interpolate the argument without some nasty nasty eval'ing.
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.
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;
} 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);
}
}
}Note that your code instantly becomes much easier to understand if you rename the variable 'write' to 'gap'.
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;
}
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;
}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.
void condense_by_removing(
char *z_terminated ,
char char_to_remove
) {
char *rptr = z_terminated; // read ptr
char *wptr = z_terminated; // write ptr
for(;*rptr; rptr++) {
if (*rptr != char_to_remove) {
*wptr++ = *rptr;
}
}
*wptr = 0;
} 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');
}
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?
char *d,*s;
for(d = s = z_terminated;
*s;
s += (char_to_remove== *s)?1:((*d++ = *s++),0))
{;}
*d = *s;
2) Initializing inside the for loop requires C99; is that to be considered idiomatic? I didn't think so. I'll be curious how many submissions were either identical to your suggested idiomatic solution or its K&R equiv:
https://gist.github.com/3f4daf24595788258a01
:-)
1) In TFA, s/cersion/version/,
but that's an amusing typo.
:-)
At least, if I recall correctly.
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".
The main point of the whole exercise is to see if the candidate can write any code - anything after that is a bonus.
Now if the input and output of a function are correct I think you where simply less clear than you may have thought. If you had said "string in place (don't allocate any memory)," I suspect far more people would have given you the output you wanted.
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."
> If you had said "string in place (don't allocate
> any memory)," I suspect far more people would have
> given you the output you wanted.
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 commenting on the style where you mix the requirements for an interface with the requirements for the algorithm. IMO "I need a function / API that does X efficiently" is much better than saying "does X using hash tables". AKA, if you don’t' want someone to use malloc then you can say so, but giving the reasons why you don't want malloc is more useful.
PS: It’s really a minor point and I thank you for doing this bit of research. I was simply trying to help you communicate in a more clear fashion.
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).
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.
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.
Also, C strings are NUL-terminated, not NULL-terminated. (char)(0) is the NUL character; (void * )(0) is the NULL pointer (usually).
If (NULL == 0) isn't true you're not using C.
void * p;
memset(&p, 0, sizeof(p));
assert(p == NULL);
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 type. Such a
pointer, called a null pointer, is guaranteed to compare unequal to a
pointer to any object or function.
-- C89/C90 section 3.2.2.3 Pointers
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).
I honestly don't know whether POSIX/SUS mandates ASCII.
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.
Yeah, it would be. They're NUL-terminated.
http://googlefight.com/index.php?lang=en_GB&word1=%22nul...
I hate all the variations of nothing. undef, null, NULL, NIL, NUL...
The character shorthand is "NUL", but the full name is "null". I still stand by my (silly semantic) point that the use of NULL is overloaded here. NULL is a pointer value, not a character value. The string does not terminate at a pointer; it terminates with a magic character. This has, in fact, bitten me in the past where '\0' was a legitimate member of my string, and I have to write my own accessors.
As for the NULL, it needn't be a pointer value, the standard permits it being "an integral constant expression with the value 0", so in certain implementations it can be the same as '\0'.
def condense(s, remove): return "".join([c for c in s if c != remove])
Cheating (2.6+): s.translate(None, remove)
The pythonic version would be s.replace(c, '')
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.
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?