## Google Interview Question for Software Engineer / Developers

• 2

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

What is your distance metric ?
euclidean or manhattan ?

Comment hidden because of low score. Click to expand.
0

Streets. Most likely Manhattan distance --l1.
So, its the median in both x and y axis. If multiple people at the same point--- just repeat. Median on n points can be computed in O(n) time.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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,

Comment hidden because of low score. Click to expand.
0

It may be done in O(m+n) with algorithm introduced here: question?id=12994675

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

WRONG.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}

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));
}
}``````

Comment hidden because of low score. Click to expand.
0

The problem statement says "Write code to calculate the point",
so IMO we should return a point.

Comment hidden because of low score. Click to expand.
0

@kuroobi, I have added one extra step to find the total shortest distance from every point on the grid to the meeting point. You can ignore the total shortest distance step and return from the above step.

``````public static Point findPoint(Point points[]){
......
......
System.out.println("Meeting point is: "+ points[avgPoint]);
return points[avgPoint];
}``````

Please suggest me, if I am wrong.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>();
System.out.println(calcCenter(points));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

This is wrong, because it is easy to show, the point with shortest distance to all given points may not be one of the given points.

Comment hidden because of low score. Click to expand.
0

If you read the question more closely, you will see that they are asking for the closest point *on the grid*.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Why not to sort by both x and y at the same time:
say P1(x1,y1), P2(x2,y2) so Comparator is: if x1 < x2 P1 < P2,
else if y1 < y2 P1 < P2
else if y1 > y2 P1 > P2
else P1 == P2.
After sorting using the Comparator pick the median Point.

Comment hidden because of low score. Click to expand.
0

I'm not sure what you mean by sorting both, Eugene. But I think sorting x's and y's separately is already simple enough.

I don't understand what you mean by noting P1 < P2.

A little typo in my above answer, the last sentence should be "... and a y in between the middle two y's."

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.