I need a WordSearch board creator. Pay particular attention to item (5).
1) Boards should be configurable between 10x10 and 20x20.
2) Boards are always square
3) Input: array of required words + dictionary file filename
4) Output: Array of letters representing board + required words actually in the board + all other available words
5) Boards should be 'dense'. In the sense that after all the required words have been added to the board, the rest of the board needs to be filled with letters that allow additional words to be spelled. Words should be weighted so that longer words are preferred.
6) Boards should contain at least 100 words and all words used should be at least 4 letters.
7) Solution time should be under 4 seconds on a modern (i7core Intel) machine.
8) You should use a DAWG for the board solution at the end. I don't want to be rude, but if you need to Google what a DAWG is, you should not be applying for this job.
9) Please quote with a fixed price (ignore hourly).
10) You will be required to provide sample output for input I provide.
11) Tell me in the reply why you think this sort of problem is cool to work on.
12) Do not use non-standard libraries in the code. It should run on Google App Engine (you are not required to test on GAE).
13) Words are allowed to run horizontally, vertically and any 45deg diagonal. Reverse words are allowed.
Skype interview with audio (in English) required, in which you describe how you will ensure the boards of dense.