For the last year or two I used this question for interviews I did at work, along with others. I’ve got bored of it and have decided it is being retired.

I would like you to tell me how to solve a wordsearch using a computer. A wordsearch is a grid of letters that is completely filled in, plus a dictionary of words. The words may appear in the grid either left-right, right-left, top-bottom or bottom-top. A solution to the problem prints out what locations in the grid the words appear and in what direction.

i.e.

plus

  • dog
  • cat
  • ball
  • bat

The point of the question was to determine if candidates can at a basic level:

  • clarify what the problem is,
  • describe coherently how to do a procedure school children can do easily,
  • discuss data structures and algorithms,
  • ideally find an efficient algorithm, and
  • possibly write code on the board.

If candidates cannot describe how to solve the problem in the most basic way, that is a red flag to me that they may not be able to express themselves properly. However the problem also has some really elegant solutions so that a good candidate can really show off.

Since I’m not using it any more I thought I’d just test myself to write down the solution I’d use, which might be interesting to somebody.

Observation 1

There is little point in solving the problem for each direction, might as well find an algorithm that works for only left-right and get the remaining directions by applying the same algorithm to the transpose, the grid reflected in the x-axis and the grid reflected in the y-axis. Now we can forget about the directions unless there is a special algorithm that does all directions efficiently.

Bad first steps

The most common bad first step I’ve heard is to put the words into a hashset. The problem there is that you have committed to a dead end solution that involves checking every substring in each row, since you can only look up a whole substring in a hash table and not look at the first few characters and figure out that no words exist.

E.g. The first row is

If you have a hashset {dog, cat} then clearly nothing beginning with x can possibly be a match, but you need to try out x, xa, xao, xaog because the hashset doesn’t let you check.

The best algorithm starting out that way is expected for an m by n table with dictionary size d, because you first need to build the dictionary in time linear in the dictionary lengthXXXXXXX.

School solutions

Describe the basic dumb algorithm

Give time complexity

Good extensions to the basic algorithm

I like people to talk about sorting the dictionary in some way, because it basically shows that they’re trying to find an efficient way to see if a particular position could be part of a word. Typically people put the words into a hashmap keyed by first letter

Extending that

Extend that algorithm by hashing at every level

Best solution I know

Prefix trie