After Trello made headlines late July for raising $10.3mm in their latest round, I spent some time looking through Trello and Fog Creek’s websites. Buried within lay a challenge that they post to prospective engineers.

## Question

Find a 9 letter string of characters that contains only letters from *acdegilmnoprstuw* such that hash(the_string) is *945924806726376* if hash is defined by the following pseudo-code:

Int64 hash (String s) { Int64 h = 7 String letters = "acdegilmnoprstuw" for(Int32 i = 0; i < s.length; i++) { h = (h * 37 + letters.indexOf(s[i])) } return h }

For example, if we were trying to find the 7 letter string where hash(the_string) was 680131659347, the answer would be "leepadg".)

## Solution

The problem looks recursive to me, and we can define hash(string, length) = hash(string, length-1)*37 + letters.indexOf(s[x]). Rewriting the hash function recursively gives the following pseudocode:

Int64 hash_r (String s, int x) { if (x < 0) return 7 return hash_r(s, x-1) * 37 + letters.indexOf(s[x]) }

For the reverse function, when starting out with the hash, the last letter can be found by looking at the modulus: *hash%37*, with the character being letters[hash%37]. Then, after subtracting out the addition of that last letter, we divide by 37 to find the previous step and character.

String reverse_hash (Int64 hash, String letters) { int remainder = hash % 37; hash = (hash-remainder)/37; if (hash == 7) // base case return “”; return reverse_hash(hash, letters) + letters[remainder]; }

And to answer their question, *reverse_hash(945924806726376) = promenade*.