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 http://www.vonsharp.net/ProgrammingJobInterviewChallengeAnswerWeek14.aspx:

image

Those are the other blog entries with answers to last weeks question:

  1. http://dotnetchris.wordpress.com/2008/08/05/a-programming-job-interview-challenge-14/ by Chris Marisic.
  2. http://blog.nvise.com/2008/08/programming-challenge-2d-geometry/ by Catalin.
  3. http://www.kevinwilliampang.com/post/Programming-Job-Interview-Challenge-14.aspx by Kevin Pang.
  4. http://www.kvnc.net/post/2008/08/07/My-Answer-to-Programming-Job-Interview-Challenge-14.aspx by Kivanc Ozuolmez.
  5. http://itscommonsensestupid.blogspot.com/2008/08/solution-to-programming-job-interview.html by Ngu Soon Hui.
  6. http://www.xerxesb.com/2008/a-programming-job-interview-challenge-14-2d-geometry/ by Xerxes.

Those are the other reader who provided correct, simple and efficient answers: Michael Mrozek, Jonathan Starr, Mark R, Michael Russell, redge, Tim Kington, Gabriele Cannata, Alex (one line would be enough), Stefan M, Niki, Marc Melvin, Ian Qvist, Kimmen and Valera KOlupaev.

Some readers provided correct answers which are less simple or efficient: David, Tristan, Joost Morsink, Andrew, Erik and Shams Mahmood.

This Week Question:

I think that this is the end of our series. I have no questions left in the bank… I have many design questions, which are best for job interviews, but I can’t publish those kind of questions because there are many correct answers and not just one or two…

I want to thank all of you who participated in this series, if you have any ideas for new questions and you want them to be published here at www.Dev102.com, don’t hesitate to contact us. Don’t be offended if we don’t publish your question, there are some great questions for real job interviews which does not fit for blog posts.

So, as you can understand, we might have more challenges in the future but the series won’t be weekly anymore. Get updates by RSS to catch up with those future posts and with our other “regular” articles.

Tags :

7 Responses to “A Programming Job Interview Challenge – The End”


  1. Catalin

    Said on August 11, 2008 :

    You can find lots of interesting problems here: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8

    But that kind of problem is not appropriate for job interview. Sadly, I never had to solve something like that in my professional life.

  2. leppie

    Said on August 12, 2008 :

    Hi

    The suggested solutions are all good and well. However, the implementation of that solution is another story.

    I would have like to have seen an actual working implementation.

    Cheers

    leppie

  3. Shahar Y

    Said on August 12, 2008 :

  4. leppie

    Said on August 13, 2008 :

    Thanks Shahar, not so trivial :)

  5. Tristan

    Said on August 14, 2008 :

    I would argue that my solution is just as effecient as the one given by Omar.

    I’m not saying his solution isnt effecient, just that after fleshing it out a simple algo can gain some ineffeciencies.

    for instance Omar would have to calculate the intercept for each line, not just the relevant ones. has to calculate the intercepts even if the point is outside the bounding box of the polygon. has to bounds check to make sure that the intercept is in the one particular direction based on the point (ie left, right, up, down, left-up, etc). then bounds check to make sure the intercept is in the actual line segment, and not an extension. it doesnt have any logic on hitting a point. ie a corner.

    like ______
    ^
    or —-

    not to mention the hideous complexity of
    var b =
    (ray.Origin.X – seg.Origin.X) * ray.Direction.Y –
    (ray.Origin.Y – seg.Origin.Y) * ray.Direction.X;

    compared to
    Point intercept = new Point((point.y + line.b)/line.slope,point.y);

    and since we are doing line scan and have discarded irrelevant lines we dont need akward bounds checking.

    you also benefit from having about 60% of a line scan poly fill written, why else are you trying to determine if a point is inside or out?

  6. Bob

    Said on August 27, 2008 :

    It’s not entirely obvious what happens when the newly created line passes through a vertex of the original polygon. It’s easy to construct examples that result in the test-point being either inside or outside the polygon, and to correctly figure out which one you’d have to compute the slope of the adjacent edges, complicating the algorithm. A potential workaround would be to keep tweaking the direction of this test line until it doesn’t hit any polygon vertices, but that doesn’t feel very clean either.

1 Trackback(s)

  1. Aug 11, 2008: Arjan`s World » LINKBLOG for August 11, 2008

Post a Comment