11 ms·
Interviewing programmers: coding test results.
- scorchin 16y agoThanks for this write-up RiderOfGiraffes. 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 http://amzn.com/0201914654 I can't wait to read the next part!
- jacquesm 16y agoWhat 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).
- RiderOfGiraffes 16y agoIt's not trivial till you've done it. 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>
- jacquesm 16y agoSure, will mail you.
- jacquesm 16y agoOk, mail in your inbox, do I get my cookie now ?
- JoachimSchipper 16y agoYeah, I tried it too. If you don't find any egregious bugs, I hereby claim it really is trivial. EDIT: although the point is to weed out the idiots, not to provide a challenge.
- axod 16y agoIt seems very trivial :/ 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 Did I miss the "gotcha"s? edit: condensed code a bit
- JoachimSchipper 16y agoPlease don't post the solution, people would like to think for themselves.
- axod 16y agoThe worrying thing is that you're suggesting there may be people on hackernews who can't bang this out in a few seconds :/ Does it even really require much thinking? I'm not trying to be arrogant here, but it seems like a good definition of "trivial".
- jacquesm 16y ago> The worrying thing is that you're suggesting there may be people on hackernews who can't bang this out in a few seconds :/ My sentiment exactly. And by the way, you do have a bug in that code.
- scorchin 16y agoLess trivial? It wasn't that difficult, although I wasn't able to complete it in 2 minutes like the colleagues of RiderOfGiraffes did!
- jacquesm 16y agoIt was dead easy and I'm seriously surprised that anybody on HN that's here not for the 'startup' angle would have a problem implementing this quickly and correctly. As code challenges come I don't think I've ever seen a more trivial example.
- djb_hackernews 16y agoare you this arrogant in real life?
- jacquesm 16y agoThat's very well possible, but it is also possible that it really was a simple problem. As for my arrogance: http://jacquesmattheij.com/Mistakes+I%27ve+made,+and+what+you+might+be+able+to+learn+from+them http://jacquesmattheij.com/Mistakes+I%27ve+made,+and+what+yo...
- axod 16y agoIt's not about being arrogant. Unless you have never done any real programming apart from simply calling library functions, the original problem is about as interesting as asking "Write a program to add 47 and 88 together". 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.
- masterj 16y agoI studied applied math instead of computer science, and the exercise took me a good 15 minutes plus some time to adjust to C as I've only worked with C++. Then another 5 to simplify some redundancies. I believe the solution I came up with was elegant, correct, and idiomatic. 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.
- miguelpais 16y agoWasn't the big discussion all about how easy the task was, and how unable were the perfect-CV people to complete it?
- scorchin 16y agoIn RoG's write-up he explains that this is a task candidates would have to pass to gain an interview.
- miguelpais 16y agoExactly. The comment I replied to was asking for something less trivial, while this is probably all you have to do to identify the candidates who can't code. 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.
- scorchin 16y agoIn that case I completely agree that trivial problems would weed out the candidates that can't program, however who says you can't give something harder than FizzBuzz? 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.
- mootothemax 16y agoI always thought that you should use different words to prevent easy googling? The test remains the same, but with, say, BaaLamb or CowTip.
- miguelpais 16y agoTo be honest, I didn't believe in the FizzBuzz situation when I read it. I didn't believe that it was possible to exist such a group of programmers who couldn't do a simple code like that. 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.
- arethuza 16y agoOne thing I had to do years ago as part of an interview was to write a C function to find the first bit set in a block of memory, flip it and return the location of the bit. Doing that at a whiteboard while explaining to the bearded chap interviewing me what I was doing. 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.
- barrkel 16y agoA neat trick for clearing the lowest bit is subtracting one and and'ing that with the original: x_cleared = x & (x - 1); You can get the lowest bit from the difference.
- bnoordhuis 16y agoIsn't this easier and faster, both type- and performance-wise? x_cleared = x & ~1;
- jonsen 16y agoThe intension is to clear the rightmost 1-bit.
- arethuza 16y agoI'm pretty sure that doesn't do what I was asked to do.
- deleted 16y ago[deleted]
- deleted 16y ago[deleted]
- RiderOfGiraffes 16y agoOK - I've had a flood of emails trying the challenge, so I'm going to delay the next post about this to let more people have a go. It's not automated so I'm dealing with it by hand, but feel free to have a go. I'll do the next posting when I've received no submissions for 48 hours. And when I get time.
- ggruschow 16y agoYou're testing whether active participants on HN that volunteer to do a problem are worth talking to? 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.
- RiderOfGiraffes 16y agoI'm not really testing them - I'm providing them with information about the tests I do, why I do them, what I do with them, and the discussions that arise from them. If you don't try it for yourself then you haven't given yourself the chance to think of the issues that I then raise in subsequent discussions. 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%.
- deleted 16y ago[deleted]
- deleted 16y ago[deleted]
- deleted 16y ago[deleted]
- mdg 16y agoI am curious to what the Python solution was, since the C requirement was to do it "in place".
- masterj 16y agoI suppose you could first convert the string to a list of characters and use integers as a replacement for pointers. You could then modify the list in place.
- deleted 16y ago[deleted]
- SMrF 16y agoI submitted the python solution. I changed the problem to accept a list. I was guessing this preserved the integrity of the problem, although I don't really know C so I couldn't be certain. I explained as much when I emailed my solution.
- conover 16y agoI had the same thought. You would have to be passed a list I guess but then that kind of changes the problem.
- mdg 16y agoI worked it out with converting z_terminated to a list inside condense_by_removing, and then returning "".join(z_terminated), but yea it does change the problem
- RiderOfGiraffes 16y agoPlease can I make a request: 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.
- jemfinch 16y ago> * Please remember the anti-spam measure - more than one person has been caught in the spam trap. What antispam measure? Neither this page nor http://www.solipsys.co.uk/Writings/TestsForProgrammers_Part_1.html http://www.solipsys.co.uk/Writings/TestsForProgrammers_Part_... says anything about spam (except this note).
- bdonlan 16y agoNor does http://www.solipsys.co.uk/new/ColinWright.html?Personal http://www.solipsys.co.uk/new/ColinWright.html?Personal - though I'm not sure that Colin Wright even wrote that, given I've yet to find a link to the article from the root, and the article doesn't have the author's name ...
- johkra 16y agoPlease check the profile, it mentions the AntiSpam measure (adding HackerNews to the subject): http://news.ycombinator.com/user?id=RiderOfGiraffes http://news.ycombinator.com/user?id=RiderOfGiraffes
- xenophanes 16y agoRead his HN profile.
- jbarciauskas 16y agoI'm not afraid, or proud, to admit I couldn't get past the n^2 solution until I talked it out with a friend. Guess it's time to go back and read my K&R...
- Maro 16y agoWith standard C style my solution is 12 LOC.
- dpritchett 16y agoI haven't touched C in the better part of a decade but the algorithm seemed straightforward to me. I'll fake it with some pseudo-C: http://pastebin.com/UpLNgxKC http://pastebin.com/UpLNgxKC 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.
- RiderOfGiraffes 16y agoPlease email it using the instructions - I've got too many submissions to go chasing them by hand. Thanks.
- dpritchett 16y agoDone! Thanks for taking the time to read this. My hope in posting the pastebin link was that other commenters might chime in if they saw glaring errors.
- btilly 16y agoIf you're interviewing and are interested in filtering out the idiots with little work on your part, http://www.ziprecruiter.com/ http://www.ziprecruiter.com/ may be useful. (Disclaimer. I know the people who created it. But it still is a useful piece of work reduction.)
- tmountain 16y agoSeems simple enough (formatted a little funny due to comment quirks): 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'; }
- coffeeaddicted 16y agoThe strlen would make this slow. Rather check if z_terminated[i] != 0.
- petercooper 16y agoYou don't need all that logic in there. for (i = 0; i <= strlen(z_terminated); i++) if (z_terminated[i] != char_to_remove) z_terminated[write_index++] = z_terminated[i]; That even removes the need to add the \0 later on.
- dalke 16y agoFor extra performance, use strchr to find the first char_to_remove. /* 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; } }
- deleted 16y ago[deleted]
- what 16y agoHow does that solution compare to something like this? char *copy_to = z_terminated; while(1) { if(*z_terminated == char_to_remove) z_terminated++; else if((*copy_to++ = *z_terminated++) == '\0') break; } Yeah, I know, it will break if char_to_remove is the zero-terminator or z_terminated is NULL.
- petercooper 16y agoThat seems pretty poor. I'm a pretty crappy programmer and haven't written any C in 18 years, but despite tripping over my feet for fifteen minutes, I have a working 4 line function. I despair for what passes as a professional programmer in shops that don't bother to check their people out properly.. Added: In the interests of "put up or shut up": http://gist.github.com/415975 http://gist.github.com/415975 - no idea if it's OK by today's standards but hey, it works
- sethg 16y agoThe program also seems to work if, in the loop header, you replace “i <= strlen(z_terminated)” with “z_terminated[j] != 0”. 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?
- studer 16y agoWell, if you don't understand your own code, it's probably not a good idea to write it that way (for-loops are a lot easier to read & verify if the stop condition depends on the loop variable, for example). 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.
- nkurz 16y agoI don't think 'j' nor 'j-1' would make sense here. 'i' would make sense, if you also terminate the condensed string. Maybe it would be clearer if the names of the index variables better described their purpose? http://gist.github.com/416298 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.
- mcu 16y ago#include <stdio.h> #include <string.h> 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); }
- bwhite 16y agoThis is an example of code that is unnecessarily O(n^2).
- mcu 16y agoNo. It isn't. There is only one iteration. It's O(n).
- jacquesm 16y agoIt's actually O(2n), so that works out to O(n) but it does have a 50% penalty, assuming an optimizing compiler. 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).
- mcu 16y agoMy original snippet contained: "int len = strlen(z_terminated);" I cut it before posting as I was going for compact code, not efficiency. Nits have been throughly picked. :)
- jacquesm 16y ago> 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...
- dusklight 16y agouh, so not a single person has mentioned memory allocation issues yet? 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.
- jacquesm 16y agoThat's pretty obvious, but since that was the requirement that's what you do. 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.
- jemfinch 16y agoI'm really amazed at the variation I'm seeing in the solutions that just my friends are providing. One said his first try would be quadratic, and his second would require allocation; another used a strange mix of indexing and pointer arithmetic. Even those who commit to either indexing or pointer arithmetic have significant variation in their solutions. 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.
- logic 16y agoInteresting that so many solutions posted thus far use strlen(). 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); }