Matchless
BAN USERI think most of you are in the right track.. my solution is inspired by all the above ideas, but in my opinion, simple, and slightly better..
I agree preorder is the best since it adds parents before children. So we output numbers as we go in preorder but everytime we go "up", we insert U (or some other character), and everytime we skip left child, we insert R.. since up characters are same as the number of parents, and right characters as much as nodes, we shall have 3n characters storage in the worst case. And while re-creating the tree, we shall be actually instructing the algorithm how to go, so the next character read will always be the one added..
suppose tree is:
a
b c
d e - f
g - h i j -
Output: abdgUUehUiUUUcRfj
Since this may involve a number of U just to get to the next available spot, we can probably just put one, denoting go to next place a node can be inserted after this node.
I know, it gets complicated, but you'll get an unambiguous, small, and fast storage format
I think the radix should be much higher than 52. Using only 52 possible hash values means that the probability that there is a collision in 53 runs of the program is 1.
My idea, though space consuming, was to have a 52x52 array of ints, storing in (i,j) the number of times ith card was placed in j. Then after N runs, we can see how many if (i,j) deviate from ideal value of N/52.
I think the point should be to minimize the number of arithematic and comparison operations, not just get the right answer. So a number of pruning steps are required to return false.
1. if difference between years >= 2 then false
2. if difference between month names >= 2, like "Jan" and "Apr" (1 and 4) then false
now you serialize the date, by 1 being the first date of the smaller month, +30 (or whatever) being the first date of the second month (include difference in year too).. then convert both dates into this format, subtract, and see if its less than 30 days..
Also cases like February, with 28 days, might need to be special cases.
Instead of storing the counters for each pair, you can save precious memory by writing out the pair of complements to a file as you encounter it. Why keep a count for pairs?
If repetitions of pairs are to be avoided, we don't even need the occurrence counters, instead just use 2 bit to store whether u has occurred or not, and has been used in a pair, and output the pair if u occurs, and hasnt been used in a pair yet
Two methods..
Create a Hash table for A, go through B and see if there are conflicts. Why we are creating hash for A, since it has lesser elements, lesser chance of collision, more efficient hashing.
Second method, if not using hash tables. well, sort A. then go through elements in B, and binary search it in A.
Ok, its like binary search. To find i, number of rotations, you have to find the position of the smallest element.
start with first and last (low and high). Also look at mid (always low+high/2). if mid is larger than low, then low=mid. If mid is smaller than high, then high-mid. Once u find smallest number, its index-1 is i. then just find array[(i+k)%n] to find kth element.
suppose original: 123456789
rotated 6 times: 456789123
low=1 high=9 mid=5
arr[low]=4 arr[high]=3 arr[mid]=8
therefore, low=5 high=9 mid=7
arr[low]=8 arr[high]=3 arr[mid]=1
therefor, high=7
soon we shall fine we cannot get a smaller number.
Since they've asked for algorithm, and not code, I shall attempt to describe a simpler recursive method.
For any n, func(n) returns a list of these string, okay? this is the function we have to write. In very broad pseudocode terms.
func(n)
- list<strings>
- for every string str in func(n-1)
- add "()"+str to list
- add "("+str+")" to list
- return list
for n=0, the function will return no string
for n=1, list will be ()
for n=2, u go into for loop
()() and (())
for n=3,
()()(), ()(())
(()()), ((()))
for n=4,
()()()(), ()()(()), ()(()()), ()((()))
(()()()), (()(())), ((()())), (((())))
Simple enough once you get it. Writing code is much-more straight forward. This also shows directly how number of these options will be 2^n
This is close. I agree with everything except for finding the lengths of ab and ab.
the coordinates need not be divided by the lengths, since we are testing for zero. suppose lac is length of ac, and lab length of ab.
(ac.x/lac)(ab.x/lab)+ (ac.y/lac)(ab.y/lab)+ (ac.z/lac)(ab.z/lab) ==0
This is same as:
(ac.x*ab.x)/(lac*lab)+ (ac.y*ab.y)/(lac*lab)+ (ac.z*ab.z)/(lac*lab) ==0
which is same as
(ac.x*ab.x)+ (ac.y*ab.y)+ (ac.z*ab.z) ==0
why I bring this up, since taking a square root is an expensive operation, since its a floating point operation. You can avoid floating point mathetics and stick to integers.
There is a big problem in all the above answers, whether finding intersection or union, whatever you want to call it. It'll fail when none of the corners of the rectangles is inside the other.
- Matchless February 21, 2007for example
--------
| |
-----|--- |
| | | |
-----|--- |
--------
or even more difficult
----
| |
-------------
| | | |
-------------
| |
----
comments?