🔒 Locked

algorithms/data structures with boggle boards!

Started by Darkbouncer4689 Dec 6, 2011 at 12:25 AM 3 replies 2.8k views

Original Post

Dec 6, 2011 at 12:25 AM

I recently received this as an interview question. The interview is over and I did not get the job (so I'm not trying to cheat on an interview, just trying to further my knowledge of algorithms and data structures for the future).

The question is as follows:
[font="Times New Roman"]Write a function which will find all the words on ageneralized Boggle™ board. The functionshould take as input the board dimensions, the board, and a dictionary of validwords and it should output the list of all found words to the calling function. You should consider how your approach willperform with a large dictionary and a large board.

My solution to this was to perform a quicksort on the dictionary words. Then I would do a depth first search to get all of the permutations of letters along the board and use a binary search to see if the permutation is in the dictionary.

Based on the interview I guess this is not the best solution and at the time I could not think of a better one. Assuming the O(n log n) quicksort is a pre computational cost, each binary search is O(log n). The only thing I know of that could be faster than O(log n) would be to hash everything and have constant lookup time.

If anyone has some recommendations on better solutions to solving this problem I would love to hear them.

Thanks![/font]

[font="Times New Roman"][/font]

BradBobak_68669

Dec 6, 2011 at 12:55 AM

Maybe a trie would be of use here. Build it from the dictionary words, then walk the board tile-by-tile (tagging each as entered), recursively entering the neighbouring tiles and tagging the tile as entered. (do not enter the tile when its tagged). Keep a pointer to the current trie node you are in, and if this tile completes a word, output it. Move on to the next neighbouring tile skipping any tagged tiles(if none are left, return from the recursive function). Move the trie pointer to the new letter if there is one. If not, leave the recursive function. When you exit the recursive function, untag that tile, adjust the trie pointer, and move on to the next. When the top-level recursive function ends, untag the current top-level tile and move on to the next.

Darkbouncer4689

Author

Darkbouncer4689

Dec 6, 2011 at 1:54 AM

Nice answer! I had actually used a trie structure before but didn't think about it until you mentioned it. I think this structure would definitely be more efficient than peforming a binary search each time. Since you would traverse the tree as you form potential words it would be constant time with little overhead for each lookup right?

What is the general lookup time for a structure such as this? Most tree structures are log n, but since this tree isn't balanced it makes things a little different.

BradBobak_68669

Dec 6, 2011 at 2:02 AM

Since you will be pointing to the current letter (partial word), I guess it would depend on looking up the sub-nodes. If you use a vector, you will have to iterate to find the next letter. an array of 26 elements would be faster (since you can index the letter) but this could be expensive memory-wise.

iMalc

182

iMalc

Dec 6, 2011 at 6:19 AM

I would perhaps approach this the other way around. Step through the dictionary from start to finish and for each word see if you can find it on the board, making only legal moves.
As a bonus, there is no need to sort first, but if you do then the results come out in sorted order.

You can also buld a set of all letters that are on the board and if the word contains letters not on the board, then skip it immediately.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.