We pay for user submitted tutorials and articles that we publish. Anyone can send in a contributionLearn More
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
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:
The thirteen post of the series of programming job interview challenge is out, Only 13 comments with answers were provided to job interview challenge #12. This is a small amount comparing to the previous challenges, but I realize and understand that it was language specific and not very trivial challenge…
Jason Kikel was the first one to solve the question, and here is his short answer:
UnmanagedClass is referencing an address on ManagedClass without pinning it. The ManagedClass instance needs to be pinned so the GC won’t move it to another location during a collection.
The twelfth post of the series of programming job interview challenge is out, 28 readers provided answers to job interview challenge #11. I have to admit that I probably failed explaining what I was looking for in challenge #11, because I asked you to provide the best algorithm in both manners: performance and memory. What I really meant is that performance is most important but don’t neglect the memory issue. Due to my little “embarrassing failure”, there are two groups of correct answers - the performance oriented and the memory oriented.
The correct answer which I was looking for (best at performance) as Alex, the first one to provide a detailed solution (its two times in a row), wrote:
The eleventh post of the series of programming job interview challenge is out. 75 readers provided answers to job interview challenge #10 and most of them had the correct solution. The correct answer as Alex, the first one to provide a detailed solution, wrote:
Here’s an O(N) solution:
Have one variable that stores the sum of all the values. Iterate through the list to add all numbers to the variable, which for simplicity I will call “listSum”.
Now, take the theoretical sum of all numbers between 1…n+1: This can be computed in O(1), as the sum of numbers up to N is n(n+1)/2: So for numbers up to n+1, it’d be (n+1)(n+2)/2 (for instance, if the array is of size 9, we’d do 10*(11)/2, or a theoretical sum of 55). Call this sum “allSum”.
The missing number will be the result of computing “allSum - listSum”.
O(N)complexity, with only two tracking variables.
Its time for a new Challenge. But before that, last weeks answer. Well the answer could have been summed up by saying just traverse in reverse and return the second node . There were a few interesting answers among them Jonathan Gilbert’s who was the first to answer correctly:
This seems pretty simple to me. An [...]
That’s it, the 9th post of the series of programming job interview challenge is out and alive. 19 readers provided answers to job interview challenge #8, Pieter G was the first to provide a correct answer:
The fastest way I can come up with is to generate a finite state machine at initialization. The transitions between states would be defined by the records you look for in the pattern and one transition for an unmatched record. When the machine enters the goal state is should send the notification (how to most quickly do that I leave to someone else). When reaching the goal state the machine should not terminate but continue (else we may miss a occurrence).
You can see more details about the solution in those blog entries:
The eighth post of the series of programming job interview challenge is out. 68 readers provided answers to job interview challenge #7 and most of them had the correct solution. As rvh mentioned, the trick here was to understand that the round table has a symmetric shape and: Actually this algorithm isn’t limited to just a round table. It will work with any shape that is symmetric with respect to both x and y axes. I couldn’t describe the correct answer better than Yoav Zobel, as he was the first one who also formally proved his algorithm:
The Correct answer (as provided by Yoav Zobel):
The correct answer is that both will return false.
You could sum up the answer by saying Boxing.
An ArrayList hold objects, so when you insert a ValueType into it, it will be boxed and become an object. When you compare List to List you are comparing references, and they will never be the same because they are pointing to different objects. This is the reason for getting the false in both comparison. It is true that in the second comparison you are comparing a double and an int ( 2.0 and 2), but that is not why you get false, it is due to the Boxing.
The sixth of the series of programming job interview challenge is out. Other then commenting the solution, I remind you that you can post the solution on your blog and get a link next week!
Here is the solution to the previous challenge:
Two-way merge sort (External Sorting) : The idea is breaking the big file into subfiles, sorting them and than merging them back together. In the first pass read one page at a time, the records in the page are sorted (quicksort for example) and the page is written back to disk. in subsequent passes, each pair of sorted output from the previous pass are read and merged to produce sorted subfile twice as long:
1. Read each page, Sort it, Write it back
2. while more than one sorted subfile:
while subfiles from previous pass left to merge:
- Choose next two subfiles from previous pass
- Read each subfile into a memory page (one page at a time)
- Merge the subfiles (remember each of them is already sorted), write output to a memory page
- Write output page to disk when needed.
Copyright © 2012 Dev102.com
Breeze : Designed by Amit Raz and Nitzan Kupererd