Edit for warning: This problem has proven substantially harder than I intended it to be. The spec keeps turning out to be ambiguous and needing patching and there are enough nasty edge cases that basically no one gets everything right (indeed, my reference implementation has just been pointed out to contain a bug). I’m going to leave it as is for the challenge but be warned.

This isn’t a question I’ve ever used to interview people, but it’s not dissimilar from the coding test we’ve got very good results from at Aframe (the problem is not at all similar, but the setup is fairly). I’ve been pondering this as an alternative, and I thought it might interesting to share it with people. I’ll explain what it’s designed to test in a later post.

If you want to answer it, I’m happy grade your answer, but there’s no exciting reward for doing so other than public or private recognition of a job well done. Details on this after the question.

The problem

You are required to write a command line program which reads lines which are terminated by ‘\n’ or EOF  from its STDIN until it gets an end of file and then writes a stably sorted version of them to STDOUT. Where a line is terminated by EOF it should have an implicit ‘\n’ inserted after it.

It is perfectly OK to use library sort functions for this. Additionally, ability to handle large numbers of lines is not required – the only performance requirement is to sort 500 lines of less than 1000 bytes each in less than 10 seconds (this should not be in any way onerous). You can write an external sort if you want, and you’ll get extra kudos for it, but it is in no way required for a correct answer. The task is to implement the comparator used for the sorting, not to implement a sorting algorithm.

The comparator to be implemented is as follows:

Each line is to be considered to be an arbitrary sequence of non-‘\n’ bytes, which will be interpreted as a sequence of non-overlapping tokens. A token is EITHER:

• a sequence of ascii letter characters a-zA-Z
• a numeric string. This is a decimal representation of a number, containing 1 or more digits 0-9, possibly with a leading – sign, possibly with a single decimal point (.) followed by additional digits. The decimal point must come after at least one digit. No other characters are permitted. e.g. -5 and 5.0 are valid numeric tokens but +5, .5 and 5. are not (though they all contain a valid numeric token: 5)

Non-ascii or ascii but non-alphanumeric bytes may be present in the line, but must not be considered to be part of a token.

Each token should be the longest possible token it can be, with ambiguity resolved in favour of making the leftmost token longer. So for example the line “foobar” is the token “foobar”, not the tokens “foo” and “bar”, and “3.14.5” is “3.14”, “5”

Note also that lines may contain characters other than those permitted in tokens, and that tokens are not necessarily separated by whitespace:

“-10.11foo10 kittens%$£$%”

should be tokenized as

-10.11, foo, 10, kittens

Lines should then be compared lexicographically as their list of tokens (as usual, if one is a prefix of the other then the shorter one comes first), with individual tokens being compared as follows:

1. Two numeric tokens should be compared as their numeric value when interpreted as a decimal representation
2. Any numeric token is less than any non numeric token
3. Non-numeric tokens should be compared lexicographically by single character, with characters compared case insensitively. Case insensitivity should be performed as in English with ‘a’ corresponding to ‘A’, ‘b’ to ‘B’, etc.

Submission

If you want me to grade your answer, email it to me at [email protected] If it’s not obvious how to run it, please include instructions. I will need to be able to run it on a linux VM.

Your email should include:

1. The source for your solution, either attached or as a link
2. Whether you want me to publish your name and grade (you don’t get to change your mind after you’ve been graded)
3. If so, how you want you want to be cited (pseudonym, full name, etc. I’m also happy to include a link
4. Whether you’re OK with me using your source code as an example in follow up posts (I will assume you are unless you explicitly say you are not)
5. Roughly how long you spent on the problem (I won’t publish this except in aggregate, it’s mostly just for my information)

I will then grade your submission as soon as I feasibly can (I don’t expect to be overwhelmed by submissions, and most of the grading will be automated, so hopefully this shouldn’t take too long). I will reply with your grade. You can at this point (assuming you didn’t get everything right. If you did, well done!) ask for examples of where you went wrong or submit an amended solution. We can keep iterating this process until one of us gets bored (I’m unlikely to accept more than 3 solutions from the same person). If you submit multiple solutions I’ll include your grades for all of them if you’ve asked for your name to be published.

Grading is as follows:

F

You have suffered from a serious failure to read the spec

C

You got some of it right, but there are significant omissions

B

You have mostly got it right, but you missed some edge cases

A

You have passed every test case I can throw at it

A+

And you implemented an external sort or otherwise did something clever. Go you!

(Note that there are no rewards for cleverness if you haven’t got the basic problem right. Such is life)

Hall of fame

(In order of solutions coming in)

1. Dave Stark with a grade of B, A. Bonus kudos also for the fact that his solution uncovered a bug in my reference solution
2. Alexander Azarov with a grade of B. Also his first solution uncovered some ambiguities in my spec
3. Kat (a different one than I’ve referenced here before). B on her first try followed by an A (she got all the hard edge cases right the first time but was tripped over by an annoying one). Also kudos for pointing out a lot of spec ambiguities.
4. Eiríkr Åsheim too gets kudos for the first solution which got everything right first time. Also for rolling his own IO code and finite state machine.

Comments policy

Feel free to point out problems in the spec. Note that a lack of detail is not a problem, but ambiguity is.

Do not post solutions in the comments. I will delete your comment. I will also delete or edit any comment I think gives too much away.

Also, comments of the form “What a stupidly easy test” will be deleted unless you have submitted a solution that was graded A.