Palantir Technologies Interview Question
The following question was the programming question during the second phone interview. The coding portion was conducted using Stypi (similar to Google Docs). I was allowed to use my language of choice (Python) rather than being forced to use Java. I was asked to write a routine to verify that all the words in the solution of a crossword puzzle were valid words. The crossword puzzle was represented as a two-dimensional array of single-character strings (and empty strings for the empty blocks). While this question is pretty straightforward, but there is a "better" solution than others which seemed to pique the interest of the interviewer—see the answer section for details. It is also worth pointing out that I later found that certain technical details of my solution were incorrect, but either the interviewer didn't notice or didn't care. I think the question was intended more to see how I work.
Interview Answer
Anonymous
In order to verify a crossword, you need to check words across and down. While the obvious solution is to code both directions separately, the more elegant solution is to transpose the crossword as you would a matrix. Then you need to write code for only one direction (the "across" code is easiest) and verify that all the words in that direction for the original crossword and the transposed crossword are the same. If your language of choice does not have built-in operator or function for matrix transposition like Python does, the interviewer would probably let you assume the existence of such a function in the standard language library (since it is a relatively common operation).