We pay for user submitted tutorials and articles that we publish. Anyone can send in a contributionLearn More
The fourteenth post of the series of programming job interview challenge is out, 83 readers provided an answer 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:
Those are other blog entries where you can find answers to the brackets question:
Those are the readers who provided correct answers in the form of a comment: sirrocco, Omar, Jason Kikel, Trinity, Justin Etheredge, Michael Mrozek, Nate, Kevin Hjelden, Jeremy Weiskotten, Alex, S Javeed, Steven Baker, leppie, Morgan Cheng, Hello world, herval, Samuel Williams, dextar, macmariman, Darrell Wright, Ryan, Shams Mahmood, Kimmen, Terje Myklebust, Jelle Hissink, Matt Howells, Dave Amphlett, Mark Brackett, configurator, Tim Kington, valera, Christof Jans, Michael, Richard Vasquez, Gerhard Balthasar, Daniel Jimenez, ilitirit, Sayre, Dejan Dimitrovski, Phi, Arni Hermann, Carl Anderson, bartek szabat, Klemen K., Petar Petrov, Niranjan Viswakarma, Michael Dikman, Alessio Spadaro, Santa, Marcos Silva Pereira and Joost Morsink.
This Week Question:
You need to determine whether the given point is inside or outside the given polygon. Here is an example of a point which is outside the polygon:
Provide the most efficient and simple algorithm. Please don’t provide Code snippets alone (without explanation), I don’t know each and every programming language… words will be enough.
Get updates by RSS to catch up with the next posts in this series and to get the correct answer for today’s question. As always you may post the solution in your blog or comment. Comments with answers will be approved only next week.
Tags :.Net2D spacebracketsC#challengeconcaveconvexgeometryjob interviewpointpolygonprogrammingquestionSoftware
Copyright © 2012 Dev102.com
Breeze : Designed by Amit Raz and Nitzan Kupererd