Trello's Hashing Interview Question

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.