CareerCup

What is your distance metric ?
euclidean or manhattan ?

As I understand the task, the result must be one or more of the given points on the grid and not any extra point somewhere in between. In my opinion, this is backed by the hint that one should imagine a map of streets.

Given this interpretation is correct, the task is just to sum up all distances that would have to be gone if all people would come together at any of the given points. The distance between two points on a grid is trivial to calculate, just the distance on the x asis plus the distance on the y axis, no graph theory required. The sum must be computed for every point, so the runtime complexity is O(N^2).

Here is my solution written in go. It contains 6 examples that can be verified with a bit of common sense by drawing the points on a grid.

package main

import "fmt"

type Point struct {
	X, Y int
}

type Solution struct {
	Indexes []int
	Min_sum uint
	Points  []Point
}

func abs(a int) uint {
	if a < 0 {
		a = -a
	}
	return uint(a)
}

func grid_distance(p1, p2 Point) uint {
	distance := uint(0)
	distance += abs(p1.X - p2.X)
	distance += abs(p1.Y - p2.Y)
	return distance
}

func median_of_grid(points ...Point) {
	sol := new(Solution)
	sol.Min_sum = ^uint(0)
	for i, ivalue := range points {
		sum := uint(0)
		for _, jvalue := range points {
			sum += grid_distance(ivalue, jvalue)
		}
		if sum < sol.Min_sum {
			sol.Min_sum = sum
			sol.Indexes = []int{i}
		} else if sum == sol.Min_sum {
			sol.Indexes = append(sol.Indexes, i)
		}
	}
	for _, value := range sol.Indexes {
		sol.Points = append(sol.Points, points[value])
	}
	fmt.Println(sol)
}

func main() {
	// one solution:
	median_of_grid(Point{0, 1})
	median_of_grid(Point{0, 0}, Point{0, 1}, Point{1, 0})
	median_of_grid(Point{0, 0}, Point{3, 4}, Point{4, 3}, Point{1, 1})
	// two solutions
	median_of_grid(Point{0, 1}, Point{1, 0})
	median_of_grid(Point{0, 0}, Point{3, 4}, Point{4, 3})
	// four solutions
	median_of_grid(Point{0, 1}, Point{1, 0}, Point{2, 1}, Point{1, 2})
}

Enjoy,

It is the center of gravity of these points. It is also known as Weber point, Fermat point, or Fermat-Torricelli point. in general it is :
1/n Sum_{1<= i <= n} w_i p_i where w_i are the weights associated to each of points p_i on the grid. If several of such points are desirable, then we can use K-clustering algorithm to divide the input points into a number of clusters whose distances to the center of their corresponding cluster is minimized.

public class FindMeetingPoint {

	static class Point{
		double x, y;
		Point(double x, double y){
			this.x = x;
			this.y = y;
		}
		@Override
		public String toString() {
			return "Point [x=" + x + ", y=" + y + "]";
		}
	}
	
	public static double findPoint(Point points[]){
		// Calculate the average point
		double avgX = 0.0;
		double avgY = 0.0;
		for (int index = 0; index < points.length; index++) {
			avgX += points[index].x;
			avgY += points[index].y;
		}
		avgX = avgX/points.length;
		avgY = avgY/points.length;
		
		// Calculate the distance average point to particular point   
		int avgPoint = 0;
		double pointsdiff = Math.sqrt(Math.pow(avgX - points[0].x, 2)	+ Math.pow(avgY - points[0].y, 2));
		for (int index = 1; index < points.length; index++) {
			double tempdiff = Math.sqrt(Math.pow(avgX - points[index].x, 2)	+ Math.pow(avgY - points[index].y, 2));
			if (pointsdiff > tempdiff) {
				pointsdiff = tempdiff;
				avgPoint = index;
			}
		}
		System.out.println("Meeting point is: "+ points[avgPoint]);
		
		double totalDistance = 0;
		for (int index = 0; index < points.length; index++) {
			double sumx = Math.abs(points[index].x - points[avgPoint].x);
			double sumy = Math.abs(points[index].y - points[avgPoint].y);
			totalDistance += Math.max(sumx, sumy);
		}
		return totalDistance;
	} 
	
	public static void main(String[] args) {
		Point points[] = new Point[6];
		points[0] = new Point(0, 0);
		points[1] = new Point(4, 1);
		points[2] = new Point(2, 0);
		points[3] = new Point(1, 5);		
		points[4] = new Point(3, 2);
		points[5] = new Point(2, 4);
		System.out.println(findPoint(points));
	}
}

Do you have more test cases?

import java.util.ArrayList;
import java.util.List;

class Point {
	int x, y;
	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	public String toString() {
		return "(" + x + "," + y + ")";
	}
}

class PointUtil {

	public static Point calcCenter(List<Point> points) {
		if (points == null)
			return null;
		if (points.size() == 0)
			return null;
		Point center = new Point(0, 0);
		for (Point p : points) {
			center.x += p.x;
			center.y += p.y;
		}
		center.x /= points.size();
		center.y /= points.size();
		return center;
	}

	public static void main(String[] args) {
		List<Point> points = new ArrayList<Point>();
		points.add(new Point(0, 0));
		points.add(new Point(0, 4));
		System.out.println(calcCenter(points));
	}
}

This can be solve in O(n); given n is the # of intersection points. How?
- First find the center of the gravity of all points. Let say C. This takes T1=O(n)
- Then find the k points around it (in 1D: k=2, in 2D k=4, in xD k=2x). This can be done by binary search on each dimension. T2=O(2xlog(sqrt(n)). Even if we don't consider binary search it can be done in T2=O(2xn)
-Find the min distance between these points and all points T3=O(n)
-Choose point with min distance T4=O(2x)
And we have: T=O(n)

Suppose the grid is represented by (X,Y) points and each Node has coordinates (x1,y1), X2,y2) .......(Xn,Yn).
First find a good starting point (will solve later). say Xk, Yk.
Now calculate the sum of the distance of all the 4 neighbours of Xk, Yk from all the points.
i.e D(Xk-1, Yk), D(Xk+1, Yk), D(Xk, Yk+1) D(Xk, Yk-1)
Pick the (x y) which is the minimum. Greedy approach.
Continue this algorithm till you reach a point, where all the subsequent D's are larger than the current D.
How to select the starting good point? In case we select a very far away point, it will take very large iterations to reach the global min-sum-distance point.
- We need to choose a point from an area where there are large number of cluster of points. This can be achieved by dividing the X-Range into a reasonable number of bins. (ranges) And Scan all the X points and increment each bin based on the X coordinate. The bin with maximum number of points is the range in which there are maximum number of X-coordinates. Similarly Scan all the Y points and repeat the process of Y corrdinate i.e. Y-Bins. Now the intersection of the Max-X-bin and Max Y-bin ranges is my cluster of interest. So we can pick the mid point of the Max-Xbin range and Max-Ybin range. Finding the good point to start will be done in linear order. (Bins space can be choosen as per the number of points 10% will be fine).
Calculation of distance of all the points for a grid point is again linear order. How fast you reach the min-distance point will depend on the distribution of the points on which we do not have no control.

We want to find a point (x, y) such that sum(x_i - x + y_i - y) for all i in the range [0, N) is minimal.

First fact: The x and y coordinates of the optimal point can be found out independently. The algorithm below is therefore specified only for the x-coordinate. The y-coordinate is similar.

Lets define L(x) as the number of given points which have an x-coordinate smaller than x. Lets define R(x) as the number of given points which an x-coordinate larger than x. And lets define D(x) as the absolute value of the difference between L(x) and R(x). For the optimal x, D(x) will be minimal (Think why!!).

So, sort the array of given points by x, and create arrays L(x), R(x) and then D(x). Now, if D(x) is zero for some x, then we are done. Else, the minimal D(x) found so far is non-zero. In this case, there must be two indices i and j in the D(x) array such that the minimal and second minimal D(x) are present here. If there are any x's available between these two points, choose the one that is closest to the side having greater number of points. Else, report the thus far found minimal D(x) as minimal.

Example:
Following is a sequence of x's in sorted order
x ---> 0 2 3 3 3 3 6 6 7 8 9 (O(nlogn))
L(x)-> 0 1 2 2 2 2 6 6 8 9 10 (O(n) left to right)
R(x)-> 10 9 5 5 5 5 3 3 2 1 0 (O(n) right to left)
D(x)-> 10 8 3 3 3 3 3 3 6 8 10 (O(n))

Thus, 3 and 5 have minimal D(x)'s using only the given set of points. We can improve this further by choosing 4 because that would have a D(x) of 1 (6 points to the left and 5 points to the right), which cannot be improved upon further.

As shown in the example above, the runtime is O(nlogn).

1. Calculate the distance matrix by Floyd-Warshall algorithm O(V^3) or Johnson algorithm (V(VlgV+E)).
2. find the row in that matrix with the minimum sum.

I think the ideal position will try to best satisfy the condition that:

1) number of points to its left equals number of points to its right
2) number of points to its up equals number of points to its down side

The reasoning behind this is in a one-dimension problem, any point in between 2 points gives shortest sum of distances. Extending it to two-dimension has similar behavior.

So to solve this problem, just sort the x's and y's of the points, and pick the middle-indexed x and y will do. If the total number of points is even, then pick an x in between the middle two x's and a y in between the middle two x's.