hack
BAN USERIts just my thought and I am not sure if this will work
Solution 1:
If we consider ith row and ith column to be a chunk, then the top right element in the inverted L will be the median. Then use the concept similar to median of median algorithm to eliminate the top chunk and bottom chunk and follow procedure similar to median of median algo
Solution 2:
With the below method we might be more efficient, but the algo is not complete
Sort the elements in the leading diagonal. In case n is odd, the middle element will be the median.
In case n is even, we need to find all the elements between the 2 middle elements which will give us the median. ( Little more time as to be invested to come up with a precise algorithm for this part)
A binary tree has a loop, if a child has more than one parent. So sort the given list with child as the key. Then travese the list to find if there are two adjacent node pair with same child . One more way I could think is to go through the list and create a hash table with child as key to figure out the number of parent the child has.
- hack November 28, 2013
Yup the solution is totally wrong :(
- hack January 29, 2014