This is the fifteen post of the series of programming job interview challenge, 37 readers provided an answer to job interview challenge #14. As you can understand from the title, I have a little announcement to make, but lets first head on to last weeks question answers.

This time, Omar was the first one to provide an efficient and correct detailed answer:

Draw a line from the single point (any direction will do).
Count the number of times that this line intersects with lines of the polygon.
An even count (including zero) indicates that the point is outside of the polygon.
An odd count indicates that the point is inside the polygon.

Here is a nice image taken from Jon von Gillern blog post

Continue Reading...

The fourteenth post of the series of programming job interview challenge is out, 79 comments with answers were provided to job interview challenge #13. We didn’t publish a question last week due to a sever lack of time, so another week is gone and here we are again.

Mark R was the first to provide a correct and detailed answer (which I can quote here):

As you examine each character, classify it as either an opening or closing bracket. If it’s an opening bracket, push it onto a stack. If it’s a closing bracket, pop the top character off of the stack; if the stack was empty, or the character was not the matching open bracket, then return an error. At the end of input, if the stack is empty, you have a legal expression.

C++ has a built-in stack class, so this becomes a trivial problem. I’m not sure about other languages. You could always simulate a stack by appending and deleting characters from the end of a string.

So, in one word, the most efficient answer is use a stack. Here is a nice image which was crafted by David Tchepak in his blog post Brackets, braces, parentheses, and other such creatures:

Continue Reading...