CareerCup

I believe this might be solvable if we view the decisions for the crossword as a tree and do DFS.

Every time we assign a certain word to a certain position, that corresponds to arriving at a node. Any subsequent decisions after this can be viewed as children of this node. The children of this node would need to satisfy two constraints:
1. Required length
2. Same character positions in the word when touching other words already present.

DS for dictionary
1) 1-D array of linked lists where ith row contains all the words which have length i+1
or
2) 2-D array [26][variable length array] of linked lists where [i],[j] contains a list of all words for which i+1'th alphabet lies in position j.

Based on the choice of either data structures, one needs to perform an additional check on character position and length respectively.

Now one can continue traversing the tree till the tree reaches depth of N where N is the total number of words to be filled in crossword.

Hari
Interviewer told you to write a code or only algo ?

Just to get mailers about this problem :-)

this problem and the idea for solution can be found in the famous book "Etudes for Programmers" by Charles Wetherell. The book suggests 4-man-weeks estimate to write the completed code for the solution + 1 week for graphics output O_o
Minor note: The problem input description that was sent here is missing the direction of to-be-filled word(horizontal or vertical)

We can use a Trie data structure for this problem.

Patricia for storing the dictionary.

Do we need to solve the crossword? or just fill it?

I think a suffix array/suffix tree would be a good data structure to solve this

We can use an adjacency graph to depict dependencies of words with other words. Once we have a graph, we can start with any node, Get a set of words which match the 'local' constraint, select any one word and traverse all neighbors by DFS (BFS will work too) . We will have to perform backtracking if any of the nodes fails to get a word among the set of words. We have to keep in mind that this is a graph and can be cyclic. There should be an ending condition where all the nodes satisfy the constraints.