Trello test

TwitterGoogle+FacebookShare

I was about to create a Trello board when i saw the positions tab. Like a moth attracted by the light, I clicked on it (after all, I love the product and was curious about what positions were being offered).
And BOOM, there it was: nodejs developer. Curiously, clicked on the link, and found that to apply, I needed to solve the following problem:

Write JavaScript (or CoffeeScript) code to find a 9 letter string of characters that contains only letters from: ‘acdegilmnoprstuw’ such that the hash(the_string) is 956446786872726.

Normally, I would not pay attention to this kind of problems. I was not even thinking on applying, but don’t know why, I got engaged to the problem and solved it in the background thinking. Apparently the hash function gave higher numbers for longer strings, and higher values for using latter letters from the alphabet (or it seemed so). 30 minutes of coding and testing after that, lead to the following solution. It works. And is making a very low number of tests to get the solution. 88 comparisons actually for the sample. It could make even less comparisons by using binary traversal of the alphabet. And it does not take into attention the expected word length hint.
The solution is written in the worst javascript ever. imperative but has no side-effects. I am more curious about what they’d expect from a solution than the solution itself. Algorithm complexity ? Functional code ? …

Is this a general inverse hash algorithm ? of course not. This is only possible because it is a very simple hash function.


/**
 * Original hash function.
 * @param alphabet {string} alphabet composing the guessed words
 * @param s {string} string to get hash for
 *
 * @return {number} string hash value
 */
function hash (alphabet, s) {
    var h = 7;
    for(var i = 0; i < s.length; i++) {
        h = (h * 37 + alphabet.indexOf(s[i]));
    }
    return h;
}

/**
 * Guess the closest (if not exact) string to a given hash value.
 * The guess happens by approximation of hash value.
 * Based on the guessed word expected length, we iterate on every character
 * changing it for the next alphabet letter until the hash value is the
 * expected one (return the string as is) or is greater than the expected.
 * In the final case, change the current char for the previous one in the
 * alphabet, and move to the next character.
 *
 * @param alphabet {string} alphabet composing the guessed words
 * @param find {number} the guessed word hash must match this value.
 *
 * @return {string} the guessed word, or "not found :(" if unable to match.
 */
function find( alphabet, find ) {

    // initialize guessed word based on supplied hash.
    var letters= [ ];
    while(true) {

        letters.push(alphabet[0]);
        var word= letters.join('');
        var hashValue= hash( alphabet, word );

        if (hashValue > find) {
            letters.pop();
            break;
        } else if ( hashValue===find ) {
            // lucky boy
            return word;
        }
    }
    
    // guess the hashed word
    for( var currentCharIndex=0; currentCharIndex < letters.length; currentCharIndex++ ) {

        for( var index=0; index < alphabet.length; index++) {

            letters[ currentCharIndex ]= alphabet[index];
            var str= letters.join('');
            var value= hash( alphabet, str );

            if ( value===find ) {
                return str;
            } else if ( value > find ) {
                letters[ currentCharIndex ]= alphabet[index-1];
                break;
            }
        }
    }

    return "not found :(";
}

// get the word with the given hash. 
// takes 88 iterations on the double nested for loop.
// result: trellises
console.log( find( "acdegilmnoprstuw", 956446786872726 ) );

// takes 44 iterations.
// result: leepadg
console.log( find( "acdegilmnoprstuw", 680131659347 ) );