Google Interview Question
Country: United States
explaining the point 5. In the input array like 3 0 0 2
weigth is the (index difference) * value
output will be
2*3 + 0*2 + 0*1 3*1 + 0*1 + 2*2 3*2+0*1+2*1 3*3+0*2+0*1
6 7 8 9
so the meeting ppoint should be the first index
step 5 was explained in the previous comment
Again it goes lilke this.
What we are trying to do in step five is that we are finding the cost of moving rest of the groups to current index i. So for each j in (1 to n) calculate |j-i|*weight of position j and sum them up. Though it looks like for every index i it will take n steps to find out this total, but if you break the "total" in two halves (left and right of i), you can update them in constant time while moving from i to i+1
@Abhishek:
This explanation of "total" is still confusing me.
All I understood is that for all the index from 0..N, for every pair of index i,j, we need to do
SUM( mod(i-j) * (A[i] + A[j]) ). This gives us an O(n2) complexity.
To make step 5 O(n), we need to additionally maintain a left and right sum for each position in the group. Suppose the numbers are 5, 1, 0, 3, then the left_sum(0) = 0, left_sum(1) = 5, left_sum(2) = 6, left_sum(3) = 6, right_sum(0) = 4, right_sum(1) = 3, right_sum(2) = 3, right_sum(3) = 0.
Then when we can quickly compute the cost(i+1) depending on cost(i). ( cost(i) is the cost of moving all numbers to position i )
For instance, at the beginning, cost(0) = 1*1+2*0+3*3 = 10;
Next, cost(1) = cost(0) + left_sum(1) - right_sum(0) = 10 + 0 + 5 - 4 = 11;
Similarly, cost(2) = cost(1) + left_sum(2) - right_sum(1) = 11 + 6 - 3 = 14;
Finally, cost(3) = cost(2) + left_sum(3) - right_sum(2) = 14 + 6 - 3 = 17;
I hope this clarifies.
I can prove that the optimal point must come from the G groups. Using your idea in step 5, It seems that I can give a O(G) algorithm.
How does solving the problem in 1D lead to solution in 2D? Consider three groups with equal number of people, forming a triangle, the solution is the Fermat point, which is clearly inside the triangle. How to find that point based on the x and y picked individually?
@PC
Your example does not hold in this case, as not all points in the triangle can reach the fermat point with 'ONE' move in a GRID, where you can only move along X and Y directions.
Look at the perspective that the cost of moving a group of people is a (distanceX+distanceY)*amount. So we need to calculate the minimal cost moving by X and then by Y axis.
public static class Location {
public int x;
public int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
public static class MeetingLocation extends Location {
public int amountOfPeople;
public MeetingLocation(int x, int y, int amountOfPeople) {
super(x, y);
this.amountOfPeople = amountOfPeople;
}
}
public static Location moveLowestCost(int n, int m, MeetingLocation... meetingLocations) {
Location newLocation = new Location(0, 0);
int minCostX = Integer.MAX_VALUE, minCostY = Integer.MAX_VALUE;
for (int x = 0; x < m; x++) {
int costX = 0;
for (MeetingLocation location : meetingLocations) {
costX += location.amountOfPeople * calculateAbsDistance(x, location.x);
}
if (minCostX > costX) {
minCostX = costX;
newLocation.x = x;
}
}
for (int y = 0; y < n; y++) {
int costY = 0;
for (MeetingLocation location : meetingLocations) {
costY += location.amountOfPeople * calculateAbsDistance(y, location.y);
}
if (minCostY > costY) {
minCostY = costY;
newLocation.y = y;
}
}
return newLocation;
}
public static int calculateAbsDistance(int x, int x1) {
if (x >= x1) {
return x - x1;
} else {
return x1 - x;
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
final Location newLoc = moveLowestCost(3, 4, new MeetingLocation(0, 1, 4), new MeetingLocation(1, 3, 3), new MeetingLocation(2, 0, 5));
System.out.println("X = " + newLoc.x + "; Y = " + newLoc.y);
}
Nice code. But time complexity is O(mG+nG). Actually, it can be O(G^2) at least. Since we can prove that the best point must be one of the G groups, we just need to loop through every point having people.
In your code :
for (int x = 0; x < m; x++) ==> for (MeetingLocation location : meetingLocations)
YES, it's enough to applies in one dimension. Actually, What I want to say is that the optimal meeting point must come from the groups in one dimensional problem. See my fully answer for this problem, which is O(G), in the next comment.
Find the center of mass with respect to x round it to nearest x,
Find the average of y
get the intersection of above two equation
that should be the meeting point.
for eg :
Group1: (0, 1), 4
Group2: (1, 3), 3
Group3: (2, 0), 5
wrt to x cm =(4*0 + 1*3+2*5)/12 =~1
wrt to y = average (1+3+0)/3 = ~1
x=1
and y=1
meeting point should be (1,1)
Time: O(mn)
public int[] min(int[][] a)
{
int total = 0;
int weightX = 0;
int weightY = 0;
int m = a.length;
int n = a[0].length;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
total += a[i][j];
weightX += a[i][j] * j;
weightY += a[i][j] * i;
}
}
int x = Math.round(weightX / total);
int y = Math.round(weightY / total);
return new int[] {x, y};
}
Hey, I just found out that in the given example (1,1) is not the minimum,
it is (1,0)....
Cost is 4 at (1,0).
What i mean is u can take the ceil or floor
in the worse can u have four values of meeting point (2 for x, 2 for y)
so at most u have to calculate the distance from 4 point and then decide the optimal solution
though i didn take much example.... try on diff-2 example u might end up fixing the decision of ceil or floor value
Anonymous...
Suppose
[ 5 . . . ]
[. 8 . . ] is given,
The meeting point should be either (0,1) or (1,0) .
What will you take Ceil or Floor ????
i already mentioned in the worse case u might end up with 4 diff values for meeting point in that case calculate the distance with those 4 values and choose the minimum one.
@Fishi
there are 4 possibilities here
since x=8/13
and y=1/2
four possibilities are
points distance
0,0 9
1,0 6
0,1 9
1,1 6
u can take either 1,0 or 0,1 since both of them has equal value
sorry for the above reply
i thought distance has following formula w *(|Xm-xi| ) + (|Ym-yi|)
but the real formula is w*((|xm-xi|) + (|Ym-yi|))
in that case we can take the cm wrt to x as well as y also
i.e
Xm = sum over all i for xi*mi / sum of all mi
Ym= sum over all i for yi*mi / sum of all mi
please ignore the above update
as someone has already pointed, find the geometric median (GM), (weighted in this case, as multiple elements at same place)
Sometimes, its good to calculate min distance for constant number of points close to GM.
may be around 100-150 for many people/groups (~10000)
Using the weighted median is wrong. Consider
2 . . . . . . . . 1
The optimal choice is to set the meeting point where the 2 people are, not anywhere in between the 2 and 1.
At the beginning, I thought it is median problem too. This problem has weight, which is a weighted median problem. But median's weight is always 1.
In median problem, we find an x, which make sum|ai-x| is smallest. For example, in x-coordinate, a1 . a2 . . . . a3, we know the median is a2, since sum of distance from a2 to other 3 points is shortest.
But in this problem, each point ai has a weight wi, the problem is to find x, which sum(|ai-x|*wi) is smallest.
Inspired by abhishek's idea. It seems that there is a O(G) solution for this problem. Since everyone agree with the two dimensional problem can be reduced to two one dimensional problem. I will not repeat it again. I just focus on how to solve the one dimensional problem with O(G).
Suppose, people are standing like this, a[0], a[1], ... a[n-1]. There is a[i] people standing at spot i. There are G spots having people(G <= n). Assuming these G spots are g[1], g[2], ..., g[G], where gi is in [0,...,n-1]. Without losing generality, we can also assume that g[1] < g[2] < ... < g[G].
It's not hard to prove that the optimal spot must come from these G spots. I will pass the prove here and left it as an exercise if you guys have interest.
Since the above observation, we can just compute the cost of moving to the spot of every group and then chose the minimal one. There is an obvious O(G^2) algorithm to do this.
But using kilotaras's idea, we can do it in O(G)(no sorting).
cost[1] = sum((g[i]-g[1])*a[g[i]], i = 2,...,G) // the cost of moving to the
spot of first group. This step is O(G).
cur_r = sum(a[g[i]], i = 2,...,G) //How many people is on the right side of the
second group including the second group. This step is O(G).
cur_l = a[g[1]] //How many people is on the left side of the second group not
including the second group.
for i = 2:G
gap = g[i] - g[i-1];
cost[i] = cost[i-1] - cur_r*gap + cur_l*gap;
if i != G
cur_r = cur_r - a[g[i]];
cur_l = cur_l + a[g[i]];
end
end
The minimal of cost[i] is the answer.
Using the example 5 1 0 3 to illustrate the algorithm. In this example,
n = 4, G = 3.
g[1] = 0, g[2] = 1, g[3] = 3.
a[0] = 5, a[1] = 1, a[2] = 0, a[3] = 3.
(1) cost[1] = 1*1+3*3 = 10, cur_r = 4, cur_l = 5.
(2) cost[2] = 10 - 4*1 + 5*1 = 11, gap = g[2] - g[1] = 1, cur_r = 4 - a[g[2]] = 3, cur_l = 6.
(3) cost[3] = 11 - 3*2 + 6*2 = 17, gap = g[3] - g[2] = 2.
I agree that "the optimal spot must come from these G spots" but I can't prove it.
How do you prove it ?
We can use math formular to prove it. We can also prove that the point be chosen is the point divided the sum of weight into 2 half. Then just need to sort one dimension, cal total sum, find the point where just turn left sum bigger than right.
How are you calculating Left and Right, What is the mid point or the point from where you are calculating left and right.
the more population at a cordinte the less we want them to move. so the one center point should be weighted mean of inverse of population.So we can take the LCM (population of each place)and do following
Summation (Xi * LCM(Pop)/pop(Xi,Yi), Summation (Yi * LCM(Pop)/pop(Xi,Yi),
the proof lies in the section formula of dividing lines into m:n ratio.
One more thing, We must respect the sign of a cordinate as Xi,Yi can be in any quadrant.
Here is what I did in C#:
public struct Group
{
public Point Location;
public int Count;
}
public Point GetNearestCenter(Group[] input)
{
if (input == null || input.Length == 0)
{
throw new ArgumentException();
}
Rectangle rect = this.GetBoundingBox(input);
Point result = new Point();
int moveSteps = int.MaxValue;
for (int x = rect.X; x < rect.Right; x++)
{
for (int y = rect.Y; y < rect.Bottom; y++)
{
int temp = 0;
for (int i = 0; i < input.Length; i++)
{
temp += Math.Abs(input[i].Location.X - x) * input[i].Count + Math.Abs(input[i].Location.Y - y) * input[i].Count;
}
if (temp < moveSteps)
{
result = new Point(x, y);
moveSteps = temp;
}
}
}
return result;
}
private Rectangle GetBoundingBox(Group[] inputs)
{
int xmax = int.MinValue;
int ymax = int.MinValue;
int ymin = int.MaxValue;
int xmin = int.MaxValue;
for (int i = 0; i < inputs.Length; i++)
{
xmax = Math.Max(xmax, inputs[i].Location.X);
ymax = Math.Max(ymax, inputs[i].Location.Y);
xmin = Math.Min(xmin, inputs[i].Location.X);
ymin = Math.Min(ymin, inputs[i].Location.Y);
}
return new Rectangle(xmin, ymin, xmax - xmin, ymax - ymin);
}
Test:
/// <summary>
///A test for GetNearestCenter
///</summary>
[TestMethod()]
public void GetNearestCenterTest()
{
Google1 target = new Google1(); // TODO: Initialize to an appropriate value
Google1.Group[] input = new Google1.Group[]{
new Google1.Group(){Location = new Point(0, 1), Count=4},
new Google1.Group(){Location = new Point(1, 3), Count=3},
new Google1.Group(){Location = new Point(2, 0), Count=5}
};
Point expected = new Point(1, 1); // TODO: Initialize to an appropriate value
Point actual;
actual = target.GetNearestCenter(input);
Assert.AreEqual(expected, actual);
}
The solution is as follows:
As xiaoc10 said, we should reduce the problem to two one dimensional problem.
Now, assume that we are going to find the best X. First sort the group based on their x => O(G) because possible value for x is limited!
Then start from one of the ends of the list, try to sum up the number of people in each group until the sum is greater or equal to total/2. Here will be the best place!
An easy intuitive solution would be O(mn) where m is number of rows and n is number of columns ....
First create four arrays two each of size m and n respectively
1. array 1 of size m will contain how many elements lie before x coordinate
2. array 2 of size m will contain how many elements lie after x coordinate
3. array 3 of size n will contain how many elements lie above y co-ordinate
4. array 4 of size n will contain how many elements lie below y co-ordinate
In each of the arrays, the x or y co-ordinates refer to the array index.
Now follow the following steps:
1. Compute Cost[0][0]
2. Compute Cost[0][1] as Cost[0][0]+array[1]-array2[1] (No need to account for y-axis movement.
3. Compute Cost[1][0] as Cost[0][0]+array3[1]-array4[1]
Whichever i,j pair has minimum value for cost will be the answer.
I'm not really sure about the correctness of previously mentioned algorithms
I think this can be solved in O(n>m?n:m) time and O(n>m?n:m) space. We have to find the median of x coordinates and median of all y coordinates in the k points and the answer will be (x_median,y_median);
Assumption is this function takes in the following inputs: a. total number of points :int k= 4+3+5 = 12; b. An array of coordinates: struct coord_t c[12] = {(0,1),(0,1),(0,1), (0,1), (1,3), (1,3),(1,3),(2,0),(2,0),(2,0),(2,0),(2,0)}; c.int size = n>m ? n:m;
Let the input of the coordinates be an array of coordinates. coord_t c[k]
struct coord_t {
int x;
int y;
};
1. My idea is to create an array of size = n>m?n:m;
2. int array[size] = {0} ; //initialize all the elements in the array to zero
for(i=0;i<k;i++)
{
array[c[i].x] = +1;
count++;
}
int tempCount =0;
for(i=0;i<k;i++)
{
if(array[i]!=0)
{
tempCount += array[i];
}
if(tempCount >= count/2)
{
break;
}
}
int x_median = i;
//similarly with y coordinate.
int array[size] = {0} ; //initialize all the elements in the array to zero
for(i=0;i<k;i++)
{
array[c[i].y] = +1;
count++;
}
int tempCount =0;
for(i=0;i<k;i++)
{
if(array[i]!=0)
{
tempCount += array[i];
}
if(tempCount >= count/2)
{
break;
}
}
int y_median = i;
coord_t temp;
temp.x = x_median;
temp.y= y_median;
return temp;
Sample Working code for MxM matrix with k points:
/*Problem Given a MxM grid . and N people placed in random position on the grid. Find the optimal meeting point of all the people. / / Answer: Find the median of all the x coordiates of the positions of the people. Find the median of all the y coordinates of the positions of the people. */
#include<stdio.h>
#include<stdlib.h>
typedef struct coord_struct {
int x;
int y;
}coord_struct;
typedef struct distance {
int count;
}distance;
coord_struct toFindTheOptimalDistance (int N, int M, coord_struct input[])
{
coord_struct z ;
z.x=0;
z.y=0;
int i,j;
distance * array_dist;
array_dist = (distance*)(malloc(sizeof(distance)*M));
for(i=0;i<M;i++)
{
array_dist[i].count =0;
}
for(i=0;i<N;i++)
{
array_dist[input[i].x].count +=1;
printf("%d and %d\n",input[i].x,array_dist[input[i].x].count);
}
j=0;
for(i=0;i<=N/2;)
{
printf("%d\n",i);
if(array_dist[j].count !=0)
i+=array_dist[j].count;
j++;
}
printf("x coordinate = %d",j-1);
int x= j-1;
for(i=0;i<M;i++)
array_dist[i].count =0;
for(i=0;i<N;i++)
{
array_dist[input[i].y].count +=1;
}
j=0;
for(i=0;i<N/2;)
{
if(array_dist[j].count !=0)
i+=array_dist[j].count;
j++;
}
int y =j-1;
printf("y coordinate = %d",j-1);
z.x=x;
z.y =y;
return z;
}
int main()
{
coord_struct input[5];
input[0].x =1;
input[0].y =2;
input[1].x =1;
input[1].y =2;
input[2].x =4;
input[2].y =1;
input[3].x = 5;
input[3].y = 2;
input[4].x = 5;
input[4].y = 2;
int size = m>n?m:n;
coord_struct x = toFindTheOptimalDistance(5,size,input);
}
My guess is that if we find center of mass of this configuration:
i.e. weighted average of their cordinates, that should be what we are looking for. But I cant prove it will be the minimum. Again in algorithms we hardly prove anything unless someone points out a wrong case :).
one dimensional examples.
[1 1] [4 2] [x, population]
[1 1] [4 8] [x, population]
Can you explain your algorithm for the above examples?
I guess its solved. the solution has 2-3 points about it: it goes like this.
- abhishek March 11, 20121) treat both the dimensions independently (lets first solveit for X whose cardinality is N in MxN)
2) assume a group of 0 ppl on the points where where is no group.
3) now we have an array (ith element is the total of ppl on x=1)
4) we have an array like 5 0 0 3 2 7 0 0 0 0 1
5) now for each element find the weighted sum of the rest of the elements. it can be done in O(n). Not writing the algo for that.
6) pick the index with lowest value in this array. that is x cordinates
repeat it for y
solution will be O(m+n)