Google

  www.google.com
Work in HR? Unlock Free Profile

Google Software Engineer 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"
Add Tags [?]
Answer

Part of a Software Engineer Interview Review - one of 3,050 Google Interview Reviews

Answers & Comments

2
of 2
votes

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
0
of 2
votes

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

- Ankit on Jan 31, 2013

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.