Google Interview Question: You are given a grid, with po... | Glassdoor

Interview Question

Software Engineer Interview

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.