bobthrollop
BAN USERTwo words: That doesn't work.
- bobthrollop April 21, 2014Nice.
- bobthrollop April 21, 2014Wikipedia says
{a smart pointer is an abstract data type that simulates a pointer while providing additional features, such as automatic memory management or bounds checking. }
With the line
{p2=p1;}
there may be different behaviors, since "smart pointer" is a generic concept. A shallow copy means that the pointer value is copied and still points to the same contents. "Deep copy" means that the contents of the pointer are copied to the new pointer. Smart pointers don't necessarily behave the way that plain pointers (in whatever language you're using) would with the same syntax.
Wikipedia says
{a smart pointer is an abstract data type that simulates a pointer while providing additional features, such as automatic memory management or bounds checking. }
With the line
{p2=p1;}
there may be different behaviors, since "smart pointer" is a generic concept. A shallow copy means that the pointer value is copied and still points to the same contents. "Deep copy" means that the contents of the pointer are copied to the new pointer. Smart pointers don't necessarily behave the way that plain pointers (in whatever language you're using) would with the same syntax.
I don't understand your last sentence.
If you construct both lists as LIFO stacks, i.e. add each parent node to the front of the list as you work your way up the tree, you end up with two lists that both start with root and are identical for their first one or more elements. Step through the lists together, and the last element before you find two non-matching elements is the nearest common ancestor.
No one has pointed out yet that you need examine at most 5 points, no matter how long the input list is. Two points have an integer midpoint if the X values are either both even or both odd, and ditto for the Y values. There are 4 different permutations of even-odd for both X and Y, and therefore if you examine 4 points and haven't found a match, you have exhausted all the possibilities and the 5th point must match one of them.
For N dimensions, the worst-case number to examine would be 2^N+1.
This problem is a variant of a long-standing math problem known as the "N-Queens problem." This version in which the queens also can move like a knight is sometimes called "superqueens." The problem, in general, is computationally very complex and requires just a lot of searching and iterating; there isn't any one best way to do it and therefore a good answer is one that's efficient in CPU time.
I found a discussion of the general problem at a Web site by Jeff Somers (I'm not allowed to include the URL here). A couple of noteworthy comments I found there:
{
There is no quick and easy way to calculate the total number of N queen solutions for an N x N board.
}
and
{
The backtracking algorithm used to solve this problem
We place a queen in the top row, then note the column and diagonals it occupies. We then place a queen in the next row down, taking care not to place it in the same column or diagonal. We then keep track of the occupied columns and diagonals and move on to the next row. If no position is open in the next row, we back track to the previous row and move the queen over to the next available spot in its row and the process starts over again.
}
Got that? It's an iterative, row-by-row search of possible solutions, terminating each branch when it gets stuck, or when a solution is found.
Is such a search too slow? Our problem states that we only need to search up to a 14x14 board. If we place each queen on a different row, and each queen must be in a column not already used, then an upper bound on the number of arrangements is 14! = over 81 billion. But each queen actually has fewer legal spots than that since it can't be within 2 columns of the queens in the 2 rows above it; therefore the number of choices to search is bounded (I'm being approximate since it gets more complicated when some queens are near an edge) by 14x11x8x8x8x8x8! = 25.4 billion. This is not an optimal solution but it indicates that such a search is doable on any current-generation PC. According to Somers (above), the largest board for which the regular n-queens problem had been solved at his time of writing was 23x23.
You could do such a search either with an iterative loop, or a recursion formula. Since the maximum depth of recursion is only 14 levels, there's no risk of a stack overflow.
Can someone explain to me how the two-pointer method is done? I didn't quite follow the hint.
- bobthrollop April 20, 2014
The answer will still be correct even if an overflow happens, since the integer values will simply wrap around and keep counting. In fact, even if (n*(n+1)/2) is a negative value because of overflow and sum is a large postive value, the subtraction of (n*(n+1)/2) - sum will "re-underflow" to the correct answer.
- bobthrollop April 21, 2014