Trello test

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  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  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 ) );

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s