What a great thing to do, RoG, really, that's a very useful thing.
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).
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.