Interviewing programmers: coding test results.
solipsys.co.uk
solipsys.co.uk
If you want to try this you're welcome, but I ask:
* Please no HTML emails - it's easier to extract from plain text
* Please remember the anti-spam measure - more than one person has been caught in the spam trap.
* Please put BEGIN before and END after you code so I can auto-extract it.
I've had 20 submissions in the last few hours, so these will help a lot.
Thanks.
========================================================
EDIT: And another 10 in the last 12 minutes. Thank you to those doing as I ask - it's making things easier. I'm going off to do some work now - I'm a little concerned about what I'll come back to ... although it is interesting. As I said earlier, I'll collect submissions until there's a 48 hour gap, then I'll start processing them.
What antispam measure? Neither this page nor http://www.solipsys.co.uk/Writings/TestsForProgrammers_Part_... says anything about spam (except this note).
I'm one of the HNers that sent in code for the test. The feedback provided by RiderOfGiraffes was useful and the follow up questions were food for thought.
At the time I'd just failed a coding test for a systems programmer role and felt pretty low, which is why I decided to take this on.
In the interview I failed, I fared well in most of the questions, apart from one set involving heavy binary maths — I pretty much forgot basic binary computation from when I did my undergrad course. Following this, it prompted me to buy "Hacker's Delight" by Henry S. Warren. It's a great read if you're into high-performance algorithms http://amzn.com/0201914654
I can't wait to read the next part!
I've done tests like this in the past couple of years for everyone responding to a job ad for all sorts of positions. The job ads usually include the problem(s), so I'm getting the same self-selection you are. Combining our results for a freakonomics style conclusion:
HN readers are an order of magnitude more skilled than job ad readers.
These test aren't for everyone, they are examples of what I specifically do.
We already know that self-selected from HN already means to 0.1%.
And when I get time.
Maybe a bit less trivial challenge next time ?
(though I can see how in an interview setting this would be all you might be able to do).
If it really is trivial then it shouldn't take you long.
If it isn't trivial then you'll learn something.
Care to try it before I publish Part II ??
<grin>
I don't really do much C, but here's x86:
// esi -> asciiz string
// cl = character to remove
// NB cl=0 won't work well ;)
mov edi, esi
cld
loop1:
lodsb // Load the byte from [esi] into al
cmp al, cl
je loop1 // Skip this byte
stosb
or al, al
jnz loop1
edit: condensed code a bit
What am I missing?
Also, eww. It decrements or increments dependent upon a flag. Not nice.
99% of the time the flag is clear... unless it isn't.
So for a seasoned assembly programmer that cld is idiomatic, axod probably typed the instruction reflexively because he knows he can't rely on the state of the direction flag, even if it has nothing to do with the problem per-se.
Does it even really require much thinking? I'm not trying to be arrogant here, but it seems like a good definition of "trivial".
My sentiment exactly.
And by the way, you do have a bug in that code.
assert(str != NULL)
You have not received any specification about the context in which the code operates, therefore the correct course of action is to assume the worse and produce bullet proof code.
If you were operating under constraints in terms of speed that would warrant a more cavalier attitude towards input checking then that would be another thing but since that wasn't specified and there is no context, 'safety first' is the way to approach the issue.
Your assertion would have done the job just fine.
Not all hardware will segfault when writing to NULL, the immutable should segfault and strings that are not null terminated are indeed hard to impossible to check for (pointer wrap..., after a lot of swapping, or a stack overwrite).
IMHO That's not a 'bug'. That's a lack of boring gruntwork error checking.
In this case that wasn't possible, so I assumed the worst, and I think that simply noting that there is a potential problem there would already score you points with the interviewer because they'd realize you spotted that the specification was incomplete, it didn't tell you what to do in case of invalid input.
(I would use some assert()s if a function could cause silent memory corruption; but this particular function either works (valid string), segfaults (NULL) or cannot detect a problem (stray pointer).)
I'm not saying your code is invalid or that it won't work, but 'defensive' programming says:
- assume your input is total garbage
- handle all correct situations correctly
- handle all garbage gracefully or throw an error depending on what the circumstances dictate
I'm also missing the stackframe handling, but as you said, this is the 'meat', that meat needs a bit of scaffolding to work.
How far do you go? Check that the memory isn't mapped as read only? ;) Check that there's actually some memory mapped into that address space?
Obviously you need both skills, but they're pretty related I'd say. If you can solve low level problems you can probably think through any potential issues, invalid inputs, edge cases etc and churn out code to deal with them.
I guess my issue is I don't see what being able to solve this says about someone, apart from "isn't completely terrible at programming".
I did note in my 'answer' that the problem wasn't specified fully.
It correctly tacks a 0 byte on the end if that's what you mean, of course cleaning up the unused space would be outside of the task at hand.
Maybe I'll look like a complete idiot soon if it transpires I've completely missed the 'gotcha' ;)
// esi -> asciiz string
// cl = character to remove
mov edi, esi
cld
loop1:
lodsb // Load the byte from [esi] into al
or al, al
jz alldone
cmp al, cl
je loop1 // Skip this byte, since it's one we want to remove
stosb // Store the byte at [edi] from al
jmp loop1 // Loop around for the next byte
alldone:
xor al, al
stosb // 0 terminate it
Still, likely my memory is at fault.
But your final solution is clearer than mine. While it uses an extra variable (register), it avoids looking up the same thing twice. So... more efficient and clearer.
BTW: TIL char * a = "hello"; doesn't work in C (I think it doesn't allocate memory). I'm actually happy enough that I could solve this at all, not having used C for 20 years ...old
> If you don't find any egregious bugs, I hereby claim it really is trivial.
Still, it may be a nice exercise.
What are you talking about? What's to understand?
My C solution, on the other hand, has a distinct graphical structure which would indicate, even to people for whom C isn't their "native language," a lot of the meaning of the text with merely a glance.
Well well, the other version seemed to work ;-)
And the fizz-buzz problem has two structurally different solutions.
EDIT: although the point is to weed out the idiots, not to provide a challenge.
As code challenges come I don't think I've ever seen a more trivial example.
Maybe this seems harder to people unaccustomed to C. I don't know. It seems like it would make sense to aim just a little higher, though. I recognize that it has to be a small enough that people won't be put off by it, but most people will be willing to invest the fifteen minutes necessary to solve a mildly complicated problem.
I think the issue is that many programmers have never done real programming. They just chain library calls together. It's like comparing a furniture maker who starts with a tree, to a furniture maker who buys parts from IKEA and assembles them.
To be a really good programmer, you need to be really really at ease with bits bytes, moving stuff around, and getting your hands dirty with real programming.
Does this mean I'm not a good programmer? If I worked with C and pointers a lot then it might, but I find the attitude that not being able to slip into that mindset immediately equivalent to being an inept programmer arrogant.
Have a source pointer, have a destination pointer. Copy stuff from src that you want, over to dest. Leave out any bytes of value N. Don't forget to copy/make a new 0 at the end.
And that's it. That's being a programmer. Knowing some particular languages syntax isn't. That's the easy/irrelevant bit IMHO.
So it really depends on if that 15 minutes you spent was to arrive at the 'solution' I wrote out in words above, or if it was checking up syntax to write it in C as to wether you're a good programmer or not.
Just my 2c.
I agree that it can be solved essentially the same way in many languages, but the idiomatic Erlang solution will look a lot different than the idiomatic C solution.
Edit: After reading some of the code posted here and linked from here, perhaps I don't have the same sense as others of what the idiomatic C solution is either. This should be interesting to read the followup posts by RoG.
As for my arrogance: http://jacquesmattheij.com/Mistakes+I%27ve+made,+and+what+yo...
From what I recall, I actually sort of enjoyed solving it as my C was bit rusty as I'd mostly been programming in Lisp.
x_cleared = x & (x - 1);
x_cleared = x & ~1;The FizzBuzz problem is at least one order of magnitude easier than this, and still is able to rule out a great part of the candidates (by time limits, according to CodingHorror, not exactly by not being able to code it). The good thing with this test is that you can actually get a glimpse of the ability of the candidate to come up with an efficient solution and identify its complexity.
Also, FizzBuzz is now so common on the web that a simple search would produce numerous solutions for those that can't program, allowing them to get through to an interview. Assuming this is your yard-stick.
How do they expect to do their jobs ?
First thing I'd ask is where is the camera :)
I can see how for a junior coding position this might be an appropriate question, say people fresh out of school, and then 1 to 10 minutes might be acceptable.
But 4 modulo statements (or 3, if you think about the problem a bit longer) and a loop ?
10 minutes ?
That's pretty slow. I understand there is a lot more to programming than coding up a simple solution like this but as problems come it is really a very simple one and if someone would take 10 minutes to put this together I'd be a bit worried about throughput, and probably about experience as well.
Now if they are actually struggling for 10 minutes, that's another matter.
Now suppose the modulo test is really expensive. Suppose we're doing something complicated with large records on disk and we want to do this is that's true, something else if the other is true, etc, etc, just as in FizzBuzz.
How would you restructure your code so it's still obvious to a maintainer what it's doing, but so that it avoids doing more modulo operations than necessary.
You see, all these trivial exercises can be used as starting points for deeper conversations about aspects of coding.
main()
{
int i;
int ncounters = 2;
int counters[2] ;
int presets[2] = { 5, 3};
int n; // number of counters that tripped
int j;
char * strings[2] = { "fizz", "buzz" };
// first time, copy presets to counters
for (j=0;j<ncounters;j++) {
counters[j] = presets[j];
}
for (i=1;i<=100;i++) {
n = 0; // reset number of counters that have zeroed
for (j=0;j<ncounters;j++) {
counters[j] = counters[j] - 1;
// output relevant string when counter trips
if (counters[j] == 0) {
// separate strings by dashes if more than one counter trips
if (n != 0) {
printf("-");
}
n++;
counters[j] = presets[j];
printf("%s",strings[j]);
}
}
// no counter tripped, just output the number
if (n == 0) {
printf("%d",i);
}
printf("\n");
}
}
No modulo operations.
By asking the question that way you'd get solutions that you're not really looking for.
int c3 = 1;
int c5 = 1;
for ( int i = 1; i <= 100; i++, c3++, c5++ ){
if ( c3 == 3 ){ printf( "FIZZ" ); c3 = 0; }
if ( c5 == 5 ){ printf( "BUZZ" ); c5 = 0; }
if ( c3 && c5 ){ printf( "%d", i ); }
}Elegant solution, but fails to meet the problem specification.
I agree it's a good starting point, but surely it's still just getting rid of the ridiculously bad programmers rather than anything else.
Assuming such a group doesn't exist, I'm all for harder problems, harder than the one presented.
But assuming the group exists, and assuming, as I did, that the problem presented tries to weed out its members, I just though something that "hard" wasn't needed.
But of course, the point of an interview is to identify the good, not the bad, so harder problems would do just fine as well in ruling out the bad.
But the whole point of the article was a user's doubt in being able to pass a FizzBuzz kind of problem. For that, something harder than the problem presented may probably not be embarrassing at all to fail at.
Yes, and no. Hard problems, being hard, mean that you don't expect all the good programmers to pass them, but to see how they think around them. And some people are able to talk the talk without walking the walk.
It's better to have an easy problem and a hard one. The easy one weeds awfully bad people, the hard one helps you find the good among the rest.
I actually think there's a distinct best solution to this problem, so it's remarkable to me that there's so much variation between people that I consider to be good programmers.
Added: In the interests of "put up or shut up": http://gist.github.com/415975 - no idea if it's OK by today's standards but hey, it works
I don’t understand why I have to put j in the index there, rather than j-1: after the string-ending null is copied, j is incremented, right?
Maybe it would be clearer if the names of the index variables better described their purpose?
http://gist.github.com/416298 (no peaking if you're submitting!)
I think these names make it clearer that neither "z_terminated[condensed]" nor "z_terminated[condensed - 1]" are reliable ways to find the end of the original string.
But your solution isn't just hard to read, it's also horribly broken. If you cannot figure out why, try printing the value of 'i' inside the loop.
void condense_by_removing (char *z_terminated, char char_to_remove) { int i, index;
for (i = 0, index = 0; i <= strlen(z_terminated); ++i) {
if(z_terminated[i] != char_to_remove) {
z_terminated[index++] = z_terminated[i];
}
}
}
int main ()
{
char dt[] = "Now is the winter of our discount tents";
condense_by_removing (dt, 'u');
printf ("%s\n", dt);
}You do make two passes over the string (one for strlen and one for the copy loop), also you assume the compiler will optimize the caching of the return value of the strlen function, if it doesn't your performance will be horrible.
No points for posting the solution...
Bwhite is not all wrong though, on a non-optimizing compiler you are hitting the string every time in the loop because of the strlen, and then it is O(n^2).
In practice, what assumptions one should make here about optimizing compilers?
It seems like it would take a lot of compiler intelligence to figure out that even though we are modifying the string in place, we are never terminating the string, and thus strlen() remains constant. Thus my instinct would be to never use it in a loop like this.
But maybe current compilers are actually this smart? I just compiled with gcc -O3 and looked at the result with objump -S, but I'm not familiar enough with the assembly to figure out how it's handling things here.
By contrast, my instinct was to do this with in a single pass with two incrementing pointers. I'm not sure if the code is clearer (http://gist.github.com/416170), but at least the assembly turns out simple enough to read!
> It seems like it would take a lot of compiler intelligence to figure out that even though we are modifying the string in place, we are never terminating the string, and thus strlen() remains constant. Thus my instinct would be to never use it in a loop like this.
You're completely right, I just tried it on several gcc settings and it is O(n^2) every time. I thought the 'n' is invariant across the execution of the loop but it might be changed because we're modifying the string and the compiler realizes that and re-runs strlen every time.
> By contrast, my instinct was to do this with in a single pass with two incrementing pointers. I'm not sure if the code is clearer (http://gist.github.com/416170), but at least the assembly turns out simple enough to read!
That's pretty much what I sent in as a solution, and I figure there will be a lot of them isomorphic with yours.
I cut it before posting as I was going for compact code, not efficiency.
Nits have been throughly picked. :)
Count on it, I am always very hesitant to post code on HN, realizing that if I'm not fresh or have tested the code that I'll be mercilessly hacked to little bits. It's fun though, I think my personal record is 5 bugs in 2 lines...
Your mettle has never truly been tested until you have hundreds of developers, from around the world, pointing out your idiocy in an excruciatingly specific manner. After your ego has been throughly decimated, then you can improve.
This is closer to how I would do it in practice.
void condense_by_removing (char *z_terminated, char char_to_remove)
{
char *next = z_terminated;
while (1) {
while (*z_terminated == char_to_remove) ++z_terminated;
if (!(*next++ = *z_terminated++) ) break;
}
}
I have a similar solution farther down the page. Not many people seem to like doing it with pointer manipulation.
EDIT: We should both probably add
if(!char_to_remove) return;
Aye... and that's when you learn. I've worked for a bit for a guy that had learned C in the 70's, best school I've had... also very painful at times.
I think you owe 'bwithe' a beer.
void condense_by_removing (char *z_terminated, char char_to_remove)
{
char *next = z_terminated;
while (1) {
while (*z_terminated == char_to_remove) ++z_terminated;
if (!(*next++ = *z_terminated++) ) break;
}
}void condense_by_removing(char *z_terminated, char char_to_remove) {
int i;
int write_index = 0;
for (i = 0; i < strlen(z_terminated); i++) {
if (z_terminated[i] == char_to_remove) {
continue;
}
z_terminated[write_index] = z_terminated[i];
write_index++;
}
z_terminated[write_index] = '\0';
} char *copy_to = z_terminated;
while(1) {
if(*z_terminated == char_to_remove)
z_terminated++;
else if((*copy_to++ = *z_terminated++) == '\0')
break;
}
for (i = 0; i <= strlen(z_terminated); i++)
if (z_terminated[i] != char_to_remove)
z_terminated[write_index++] = z_terminated[i];
/* Find the first character to remove */
/* This doubles the performance when there are no
remove characters, I assume because it uses a
builtin and because I don't do unneeded writes. */
src = strchr(z_terminated, char_to_remove);
if (src == NULL)
return;
/* src is the position in the old string, with
the possible characters to remove.
dest is the end position of the new string,
where non-removed characters are added */
dest = src++;
for (;;) {
/* Skip additional remove characters */
while (*src == char_to_remove)
src++;
/* Copy (including copying the terminal NUL) */
if (! (*dest++ = *src++)) {
/* copied a NUL - end of string */
break;
}
}Note: I read the entire thread several hours before making this attempt so my results don't represent a good lab environment. Please let me know if I made any major errors.
Thanks.
the pointer to the 0 terminated string could have been to a statically allocated array or memory allocated from the heap using malloc. If you just shorten the string without reallocating the memory, the extra bytes that got condensed are still marked as allocated and are wasted.
For all you know the length of the original string is kept around somewhere for future reference when the buffer is re-used, it's not uncommon for buffers used like this to be limited to some fixed size larger than the maximum expected string length + 1 for the terminating nul char, and to have a string copied in to a buffer for processing.
You're in deep trouble when you try to insert stuff into strings like that though...
The bytes that got condensed and are wasted would be wasted even worse in the way you describe, if you re-allocate the memory then you'll have to free the original one, leaving the larger portion sitting unused, instead of just a few bytes...
Sure, that could be re-used by some other call to the allocator by a different part of the program, but the most important issue here is that that was not what was specified.
Whoever spec'd it needs it like that, so that's what gets built.
My C is beyond rusty, but this is what I came up with; do/while is so underappreciated these days. (HN needs a "spoiler" formatting tag, methinks. :)
void condense_by_removing(char *z_terminated, char char_to_remove) {
char *pos = z_terminated;
do {
if (*z_terminated != char_to_remove)
*pos++ = *z_terminated;
} while (*z_terminated++ != 0);
}