Barnsley fern fractal

Thoughts on software architecture and development, and methods and techniques for improving the quality thereof.

David B. Robins (home)


Code Visions: Improving software quality
That's not a hash… that's an encoding!

By David B. Robins tags: Development, Hiring Wednesday, February 4, 2015 20:13 EST (link)

The Trello Android Developer job page requires applicants to solve a programming puzzle, the solution of which must be sent with an application. (In case the question changes or page moves, searching for the source string "acdegilmnoprstuw" or 680131659347, the "hash" of "leepadg" should bring up the question.) The question is presented as reversing the hash of a string, i.e., given a (numeric) hash value, producing the original string. For strong hashes used in the real-world, such as MD5 or SHA1, this is a difficult problem and almost certainly requires a degree of brute-forcing, i.e., enumerating all the possible strings (billions and billions…), putting them through the hash function, and checking if the result matches the given hash value. Doing it significantly more efficiently would make someone famous and (from generating Bitcoins alone) rich.

However, the Trello developer question is actually an encoding, and while that doesn't technically exclude it from being a hash, one desirable quality in a hash is that it's difficult to go from hash value to original string (or even a possible original string, accounting for collisions), whereas being able to do that is a necessary property of an encoding. (I expect the Trello problem writers know this, and want to filter brute force attempts, which are, given the smaller space than in-use hashes, possible.) Encoding vs. Encryption vs. Hashing is a well-written post that clarifies the differences. It is trivial for someone with the most basic understanding of algebra to reverse the encoding in the question (it's a "weeder" question; I'm certain they'll have harder ones to ask in an actual interview).

I'd refrain if others hadn't already posted some solutions on the web (since it's a pain to have your screening question's answer available for cutting and pasting, although a few quick live (phone or in person) questions to the candidate should suffice to detect ignorant copying), but here's a Perl one-liner that solves it:

perl -wle '$t=956446786872726; while($t) { unshift @a, $t % 37; $t -= $a[0]; $t /= 37; } shift @a; print map { substr("acdegilmnoprstuw", $_, 1) } @a'

Given that it's folded into one line, it won't win you any style points anyway. While the Android developer position doesn't specify a language, the Node.js developer opening also posted specifically requires JavaScript or CoffeeScript. And note that at least one of the answers posted online does present a brute force and ignorance "solution"; perhaps a trap for those that might ignorantly search and copy?

Content on this site is licensed under a Creative Commons Attribution 3.0 License and is copyrighted by the authors.