# 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];
}```