Want a Free Job Posting?

Buy a job posting today and the second one is on us. For a limited time only. Act Now.

Interview Question


You are given a grid, with points on the intersections

  (think a map of streets, people are standing on random corners). Write code to calculate the point on the grid that is the shortest distance from every point on the grid

Interview Answer

2 Answers


this a weighted median problem. find the median of all the x-points find the median of all the y-points This (x,y) obtained from above will be the point shortest to all the points to find the median, you can sort the points (x values, y values) if you use merge sort, you can do it in nlogn finding the median from the sorted points takes O(1)

Gbele on Jan 18, 2013

Use Dijakstra's Shortest Path Algorithm either using adjacency matrix or adjacency list

Ankit on Jan 31, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.