Detecting GrabScrab Steals

This is a problem solving question appropriate for a fairly experienced C/C++ programmer.

Problem

At Tellme, a popular game to play was GrabScrab. In GrabScrab, players take turns flipping over shuffled Scrabble tiles, winning ownership of words by calling them out when the exposed letters spell them. At any time you can "steal" another player's word by forming a new word from any exposed letters. For example, if Alice has word "LIVE" and a "D" is overturned, Bob can call "DEVIL" and steal Alice's word.

Write a function is_steal(bigword, littleword) which returns true if bigword is a steal for littleword.

Solution

The straightforward "human style" solution is to walk through each letter of the smaller word and locate and mark each in the larger word. If you can't find an unmarked letter in the larger word for a letter in the smaller word, then you don't have a valid steal:

int is_steal(char *big, char *little) {
    char *lp, *bp;
    int found;

    for(lp = little; *lp; lp++) {
        found = 0;
        for(bp = big; *bp; bp++) {
            if(*lp == *bp) {
                found = 1;
                *bp = ' ';
                break;
            }
        }
        if(!found) return 0;
    }

    return 1;
}

This is O(n*m), where n and m are the lengths of the strings, or, more generically, just O(n2) for the input strings.

One improvement is to sort characters in each word, then just iterate linearly through the letters in the smaller string, and locate the corresponding letter(s) in the bigger string. This comparison only takes linear time, but sorting characters will impose an O(n*log n) overhead, assuming QuickSort is used.

The optimal linear time solution is to count letters (there are only 26 possible letters, so using an integer array of 26 elements suffices). The most efficient way is to count the letters in the longer word, then decrement each count for the letters in the shorter word.

Interview Tips

This is a fun question because it is culturally interesting. International candidates, or folks who were exceptionally popular in school, may not be familiar with Scrabble, so it's worth asking, and explaining the basic concept of letter tiles if necessary.

Experienced candidates will immediately recognize the basic nature of the problem: find out if one set of unsorted characters is a subset of another. The name of the predicate should be clear and declarative (is_steal() or contains_chars() are good examples), and the variable names are better if they are unambiguous (bigword and littleword, or steal and root, instead of something like w1 and w2).

Expect good candidates to get the n2 solution fairly quickly, and eventually to move to the lookup table version. Candidates not using C may use whatever dictionary idiom their language provides.

You may want to list some sample steals to make the GrabScrab rules clear. You may want to withhold the trickier variants, like doubled letters, to let candidates independently discover any relevant problems caused by them—good candidates will set about testing the solution after writing it. Here are some basic example steals:

By the way, the official GrabScrab rules state that words must be four or more letters, but I sometimes use shorter examples to make the code testing easier. I also usually stipulate that inputs can be assumed valid (all uppercase letters, for example) to minimize the amount of bookkeeping in the code.

See Also

is_steal.c (1.1k)
A test program demonstrating the letter counting solution.