News for hackers. Stuff that matters.
Re:The ReadyForZero Programming Challenge by gjm11 on Tuesday June 14, 2011 @03:16PM (#2654328)
Three problems, algorithm-centric, each solvable with (some intelligent thought and) a few lines of (say) Python. Unsurprisingly, the payoff is "we're hiring; please send us your resume".

ReadyForZero appears to be a company that helps people get out of credit card debt by tracking what you owe to whom and recommending what to pay off in what order. They just got Series A funding.

Re:The ReadyForZero Programming Challenge by amalcon on Tuesday June 14, 2011 @04:44PM (#2654677)
The most difficult part was figuring out unspecified things in the problems. Generally I had to use my intuition about "otherwise this would be either impossible or too easy" to get the right answer.

The first problem should be more explicit about the nature of the difference: a "typo" or non-shared could reasonably be an omission of a character, which would mean that the position of the unknown character does not matter. This weaker problem has more than one correct answer for the given input data. Better to call it a "corrupted byte" or somesuch.

It should be explicitly stated that the tree is balanced in the second problem. It should also state that each node contains exactly one character or that all nodes have nonempty payload (you can figure out either of those pieces of information from the other one).

The third problem should specify that it's looking for a strict partition. Contiguous is not a strong enough requirement. As written, I can have as many "contiguous subsequences" of zero elements as I want located anywhere in the string.

I particularly like the third as a teaching problem, and I might have to use it sometime. It's pretty simple, not overly reliant on programming concepts, and the "clever" solution is both faster and easier to implement than the brute-force try-everything solution.

Re:The ReadyForZero Programming Challenge by ibdknox on Tuesday June 14, 2011 @05:53PM (#2654941)
Given that the point of this is to have fun and also tease out people worth hiring, having ambiguity in the problems is a good thing I think. Rarely is a real technical problem so clearly and obviously defined. So requiring a bit of thought and intuition might prove to be a good filter :)
Re:The ReadyForZero Programming Challenge by ithayer on Tuesday June 14, 2011 @05:19PM (#2654801)
Very good points. The computer screen wasn't that large so I tried to keep the descriptions short. :)
Re:The ReadyForZero Programming Challenge by nottodayy on Tuesday June 14, 2011 @03:40PM (#2654415)
Reading the first problem, I think I am not ready for zero, it seems that the first problem is not well described.
Re:The ReadyForZero Programming Challenge by zheng on Tuesday June 14, 2011 @03:46PM (#2654442)
You are looking for a sequence of 5 characters that differ by one character, but are otherwise identical (order matters). For example, an answer would be something like '89^hf' and '8z^hf'
Re:The ReadyForZero Programming Challenge by nottodayy on Tuesday June 14, 2011 @04:04PM (#2654521)
Thanks, order matters that's what I missed.
Re:The ReadyForZero Programming Challenge by kevinholesh on Tuesday June 14, 2011 @03:13PM (#2654316)
From the source of the website: "<!-- Are you looking at the source code? Like we'd put the answers here. Creative tho... -->"

It was worth a shot.

Re:The ReadyForZero Programming Challenge by gmaslov on Tuesday June 14, 2011 @03:42PM (#2654425)
These are very similar to (and easier than most of) the Project Euler problems. http://projecteuler.net/ -- Highly recommended for everyone.
Re:The ReadyForZero Programming Challenge by ithayer on Tuesday June 14, 2011 @04:00PM (#2654509)
If anyone wants the hard version, let me know (you can upvote this comment)
Re:The ReadyForZero Programming Challenge by pom on Tuesday June 14, 2011 @08:28PM (#2655464)
That was a fun before-breakfast warmup; the input was always short enough that a simple, brute-force approach would usually work. The problem statements could have been made a little bit clearer though.

And what's up with the green-on-black Mac screen?!

EDIT: my solutions (using Node.js) https://github.com/julienq/incubator/tree/master/misc/readyf...

Re:The ReadyForZero Programming Challenge by owenjones on Thursday June 16, 2011 @02:32PM (#2662569)
Hello could someone help me with problem 2? I believe I am splitting the string correctly, 1 2 4 8 16 ... 512 = 1023 total chars/nodes, but when I add the integers of the last line (aka the leaves) I get the wrong result.

https://gist.github.com/1029356

Thanks.

Re:The ReadyForZero Programming Challenge by sokolski on Tuesday June 14, 2011 @09:33PM (#2655601)
My solutions: https://gist.github.com/1026309 Didn't really stop and think on the first one for too long, so it's a bit messy. Overall it's quite easy but not trivial. Knowing the length of the challege at the beginnig wold be nice though.
Re:The ReadyForZero Programming Challenge by llimllib on Tuesday June 14, 2011 @04:58PM (#2654722)
My answers in 31 lines of code: https://gist.github.com/1025860

I am either misreading the third problem's description, or I have a bug I can't for the life of me see, because the answer my program puts out is not accepted.

Re:The ReadyForZero Programming Challenge by DanielStraight on Tuesday June 14, 2011 @05:05PM (#2654747)
The third problem is looking to partition the entire sequence of numbers into contiguous subsequences, all of which add up to the same sum. In other words, if the list were 23415, you subsequences could be 23, 41 and 5, all equaling 5. But the subsequences have to use up the entire string and they can't overlap.
Re:The ReadyForZero Programming Challenge by llimllib on Tuesday June 14, 2011 @07:04PM (#2655195)
They can't overlap! I don't think the problem specifies that?

You have to interpret "break up" to mean "non-overlapping" to claim that the problem means what you're saying it means; I found 341 "contiguous subsequences such that the sums of each of the subsequences are equal", but they overlap.

(If you had said "partition" I suspect I would have got what you meant)

Re:The ReadyForZero Programming Challenge by DanielStraight on Wednesday June 15, 2011 @08:37AM (#2656817)
Contiguous implies non-overlapping.
Re:The ReadyForZero Programming Challenge by hugh3 on Tuesday June 14, 2011 @06:02PM (#2654964)
Did anyone else do that one without writing any code?
Re:The ReadyForZero Programming Challenge by genesiss on Tuesday June 14, 2011 @06:05PM (#2654976)
You mean with smart guessing? That's no fun!
Re:The ReadyForZero Programming Challenge by hugh3 on Tuesday June 14, 2011 @06:31PM (#2655066)
Yeah. It took me three guesses to get it right. :)
Re:The ReadyForZero Programming Challenge by wbhart on Tuesday June 14, 2011 @09:49PM (#2655639)
You didn't need 3 guesses. The sum of each partition has to be a factor of the number. In particular the sum of the first partition has to be a factor. Then the second. That already gives you the answer I think.
Re:The ReadyForZero Programming Challenge by hugh3 on Tuesday June 14, 2011 @10:49PM (#2655773)
Sure, but then I'd actually have to look at the numbers. My solution works without having to download the file! ;)
Re:The ReadyForZero Programming Challenge by apaprocki on Tuesday June 14, 2011 @05:08PM (#2654754)
> #pip install python-levenshtein > from Levenshtein import distance

That doesn't seem in the spirit of the challenge.

Re:The ReadyForZero Programming Challenge by llimllib on Tuesday June 14, 2011 @06:56PM (#2655165)
Why? It's not hard to write a quick and dirty levenshtein function, but when google gets it for me in 1 minute, why do it?

edit: just for fun, as a one-liner:

    def levenshtein(a,b): return sum(x!=y for x,y in zip(a, b))
edit 2: and just to clarify, I know this fails if the lengths of the input strings differ, they were guaranteed to be equal in my code.
Re:The ReadyForZero Programming Challenge by ithayer on Tuesday June 14, 2011 @05:20PM (#2654809)
Can you do it in linear time in the length of the input?
Re:The ReadyForZero Programming Challenge by kilburn on Friday June 17, 2011 @10:10AM (#2665539)
Find an actual (amortized) linear time implementation for this question in the following gist:

https://gist.github.com/1026638

Re:The ReadyForZero Programming Challenge by drdo on Tuesday June 14, 2011 @05:35PM (#2654870)
It's not hard to prove that that's impossible
Re:The ReadyForZero Programming Challenge by amalcon on Tuesday June 14, 2011 @06:38PM (#2655100)
It's possible if RAM isn't a constraint, using a bitset of all possible five-letter strings. The bitset would take up 4G of RAM (128G for extended ASCII, more for unicode).

In practice, that would actually be slower on this input, because of the cost of initializing the bitset. But that is not dependent on the input, so computational complexity is unaffected.

edit: Removed description. Yes, you're right, you can't even look at the whole input in constant time.

Re:The ReadyForZero Programming Challenge by drdo on Tuesday June 14, 2011 @07:21PM (#2655257)
This is a misunderstanding, you must have answered to my reply after ithayer edited his comment, the initial comment said "constant time".
Re:The ReadyForZero Programming Challenge by drdo on Tuesday June 14, 2011 @06:49PM (#2655144)
Didn't understand what you meant, care to elaborate?
Re:The ReadyForZero Programming Challenge by ithayer on Tuesday June 14, 2011 @05:36PM (#2654871)
:) I meant linear, but I'd review a proof :)
Re:The ReadyForZero Programming Challenge by wccrawford on Tuesday June 14, 2011 @02:39PM (#2654165)
Oh, that first question looks tasty. I dunno what a 'ReadyForZero' is, but the challenge could be fun.
Re:The ReadyForZero Programming Challenge by decultured on Tuesday June 14, 2011 @07:00PM (#2655180)
Fun challenge, but not too difficult. The largest challenge was making the intuitive leaps to discover the missing information in the questions, especially for problem two. A bit of trial and error, and a few lines of Python made for quick testing of those assumptions.
Re:The ReadyForZero Programming Challenge by ralphc on Saturday June 18, 2011 @07:53PM (#2669830)
Solutions in Clojure https://gist.github.com/1033605

I "cheated" on the third one in that I read the discussion here which helped clarify the problem, non-overlapping, etc.

Re:The ReadyForZero Programming Challenge by ralphc on Wednesday June 22, 2011 @09:47PM (#2686283)
I figured out a better challenge 1 with combinatorics, also figured out non-anonymous gists https://gist.github.com/1041697
Re:The ReadyForZero Programming Challenge by dhugiaskmak on Tuesday June 14, 2011 @11:46PM (#2655887)
Here are my solutions for #1 and #3. I cheated on #2 just like everyone else.

https://gist.github.com/1026404

Re:The ReadyForZero Programming Challenge by drdo on Tuesday June 14, 2011 @03:49PM (#2654456)
Wasn't hard. The problems could be better explained, for example in the second one they should clarify that the binary tree is balanced and that each node is one character.
Re:The ReadyForZero Programming Challenge by noglorp on Tuesday June 14, 2011 @04:00PM (#2654507)
> binary tree is balanced and that each node is one character

I found that pretty intuitive given they tell us it is a tree with 2^n-1 nodes, and that this is then umber of characters in the text file.

What I'm wondering about is what the '=' pad character means in the context of non-valid base64 (i.e. isn't it the same as the 'A' character - a null?)

Re:The ReadyForZero Programming Challenge by ithayer on Tuesday June 14, 2011 @04:10PM (#2654545)
you're right - we should explain that it's balanced.
Re:The ReadyForZero Programming Challenge by noglorp on Tuesday June 14, 2011 @04:42PM (#2654668)
Any comment in regard to my question above? At present, question 2 has serious ambiguity as to how one should interpret the data. Clearly each character represents one node, but again, there is no clear procedure for converting values. Padding makes no sense in this context.

Can you clarify?

Re:The ReadyForZero Programming Challenge by drdo on Tuesday June 14, 2011 @04:45PM (#2654683)
It's just as ASCII, you should sum the leaves that have ASCII digits (sum their digit value, not their ASCII code) and ignore the non-digit leaves.
Re:The ReadyForZero Programming Challenge by noglorp on Tuesday June 14, 2011 @05:11PM (#2654763)
I still don't follow. Digit value rather than ASCII code... you mean Base64 digit value? If so, do you just ignore the pad char? (I mean... by "non-digit leaves" you are referring to the leaves represented by '=' and only those?)

EDIT: I understand now... jeez that was a run-around! Ascii encoded decimal! Thanks for the clarifying replies all over.

Re:The ReadyForZero Programming Challenge by zwieback on Tuesday June 14, 2011 @05:18PM (#2654798)
I think it's literally one ASCII code (byte) per each of the 1023 nodes in the tree. Any time there's a non-digit in one of the leaf positions you ignore it.
Re:The ReadyForZero Programming Challenge by drdo on Tuesday June 14, 2011 @05:22PM (#2654817)
There's no Base64, it's just regular ASCII, for each leaf that has an ASCII character '0' through '9', you sum 0 through 9 respectively.
Re:The ReadyForZero Programming Challenge by zwieback on Tuesday June 14, 2011 @04:59PM (#2654724)
Ah, that's the part I was missing. When I didn't see a digit in the first leaf I thought I had it wrong.
Re:The ReadyForZero Programming Challenge by ithayer on Tuesday June 14, 2011 @05:25PM (#2654835)
The characters should be interpreted as ASCII.
Re:The ReadyForZero Programming Challenge by drdo on Tuesday June 14, 2011 @04:26PM (#2654607)
One quickly realises that you must mean a balanced tree, since otherwise there would be no unique solution, but it would still be nice if it was explicit in the text.
Re:The ReadyForZero Programming Challenge by leif on Tuesday June 14, 2011 @06:20PM (#2655016)
yeah I thought it was base64 and that was annoying
Re:The ReadyForZero Programming Challenge by DanielStraight on Tuesday June 14, 2011 @03:11PM (#2654300)
I don't usually do these challenges, but this one was pretty fun. It's three problems long. Took me about 30 minutes.
Re:The ReadyForZero Programming Challenge by genesiss on Tuesday June 14, 2011 @05:46PM (#2654923)
I enjoyed solving these. Last one is cool, but hint is too obvious ;>
Re:The ReadyForZero Programming Challenge by drdaeman on Tuesday June 14, 2011 @06:56PM (#2655167)
When one has cookies disabled (and those days I believe everyone should) it throws Django error page:

> Forbidden (403)

> CSRF verification failed. Request aborted.

They should've checked that cookie exists. Or, better, not rely on cookies.

Re:The ReadyForZero Programming Challenge by ithayer on Tuesday June 14, 2011 @07:20PM (#2655254)
Thanks for pointing that out. Yes, we could have checked every single corner case, but our job is to build financial software, not programming challenges, so we did it quick and dirty :)
Re:The ReadyForZero Programming Challenge by troyk on Tuesday June 14, 2011 @03:27PM (#2654363)
Could that be a booger on the 1 key (numeric keypad)?
Re:The ReadyForZero Programming Challenge by abofh on Tuesday June 14, 2011 @05:31PM (#2654857)
Meh, it killed an hour or two that needed to suffer.
Re:The ReadyForZero Programming Challenge by leon_ on Tuesday June 14, 2011 @04:53PM (#2654714)
> Are you ready to get out of credit card debt? > ReadyForZero is a free online financial tool that lets you track your credit card debt ...

what is this? some kind of a sick SEO experiment? flagged for spam.

Re:The ReadyForZero Programming Challenge by ithayer on Tuesday June 14, 2011 @05:26PM (#2654841)
Not an SEO experiment - trying to hire smrt people!