Interviewing programmers: coding test results.

http://www.solipsys.co.uk/Writings/TestsForProgrammers_Part_1.html

81 129 16 years ago

solipsys.co.uk

scorchin4• 16 years ago

Thanks 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

I can't wait to read the next part!

jacquesm27• 16 years ago

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

RiderOfGiraffes8• 16 years ago

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

jacquesm27• 16 years ago

Sure, will mail you.

jacquesm27• 16 years ago

Ok, mail in your inbox, do I get my cookie now ?

JoachimSchipper5• 16 years ago

Yeah, 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.

axod12• 16 years ago

It 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

scorchin4• 16 years ago

Less trivial? It wasn't that difficult, although I wasn't able to complete it in 2 minutes like the colleagues of RiderOfGiraffes did!

jacquesm27• 16 years ago

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

miguelpais3• 16 years ago

Wasn't the big discussion all about how easy the task was, and how unable were the perfect-CV people to complete it?

scorchin4• 16 years ago

In RoG's write-up he explains that this is a task candidates would have to pass to gain an interview.

arethuza2• 16 years ago

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

barrkel2• 16 years ago

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

RiderOfGiraffes8• 16 years ago

OK - 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• 16 years ago

You'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.

RiderOfGiraffes8• 16 years ago

I'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%.

_3ex72• 16 years ago

I am curious to what the Python solution was, since the C requirement was to do it "in place".

masterj3• 16 years ago

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

SMrF• 16 years ago

I 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• 16 years ago

I had the same thought. You would have to be passed a list I guess but then that kind of changes the problem.

_3ex72• 16 years ago

I 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

RiderOfGiraffes8• 16 years ago

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

jemfinch5• 16 years 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_... says anything about spam (except this note).

bdonlan2• 16 years ago

Nor does 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• 16 years ago

Please check the profile, it mentions the AntiSpam measure (adding HackerNews to the subject): http://news.ycombinator.com/user?id=RiderOfGiraffes

xenophanes2• 16 years ago

Read his HN profile.

jbarciauskas• 16 years ago

I'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• 16 years ago

With standard C style my solution is 12 LOC.

dpritchett2• 16 years ago

I 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

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.

RiderOfGiraffes8• 16 years ago

Please email it using the instructions - I've got too many submissions to go chasing them by hand.

Thanks.

dpritchett2• 16 years ago

Done! 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• 16 years ago

If you're interviewing and are interested in filtering out the idiots with little work on your part, 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• 16 years ago

Seems 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• 16 years ago

The strlen would make this slow. Rather check if z_terminated[i] != 0.

petercooper2• 16 years ago

You 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• 16 years ago

For 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;
    }
  }

what2• 16 years ago

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

petercooper2• 16 years ago

That 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 - no idea if it's OK by today's standards but hey, it works

sethg• 16 years ago

The 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• 16 years ago

Well, 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.

nkurz2• 16 years ago

I 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 (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.

mcu6• 16 years 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• 16 years ago

This is an example of code that is unnecessarily O(n^2).

mcu6• 16 years ago

No. It isn't. There is only one iteration. It's O(n).

jacquesm27• 16 years ago

Points for the <= copying of the termination character :)

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

mcu6• 16 years ago

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

dusklight• 16 years ago

uh, 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.

jacquesm27• 16 years ago

That'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.

jemfinch5• 16 years ago

I'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• 16 years ago

Interesting 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);
  }

Interviewing programmers: coding test results.

Related Stories