Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
using quick select you can take the median of the x coordinates and the y coordinates.
the target function is sum i from friend 1 to friend n |friend i x corrdinate -X| + | friend i y coordinate - Y|
we need to find X,Y that minimize it.
and obviosly we get this from the median element from x coordinate list and y coordinate list.
weighted quick-union algorithm is best to find if 2 nodes are connected. with weighted I hope it is also a good option to find the shortest path.
- Anonymous February 10, 2014You always connect the smaller tree to the larger tree keeping the height of the tree no more than lg of n.