Google Interview Question
Software Engineer / DevelopersCountry: United States
Yes it is fermat point is a point such that the total distance from the three vertices of the triangle to the point is the minimum possible.
#include<stdio.h>
#include<string.h>
int main()
{
char a[]="xyz";
char b[]="abc";
char c[]="axytbc" ;
check(a,b,c);
getch();
return 0;
}
int check(char *a,char *b, char *c)
{
int i=0,flag=1;
while(i<strlen(c))
{
if(*c==*a || *c==*b)
{
if(*c==*a)
{*c++;
*a++;}
else
{*c++;
*b++;}
i++;
}
else{
printf("NO");
flag=0;
break;
}
}
if(flag==1)
printf("yes");
}
Cool!! Good to learn new thing. This was the only question given. I was thinking to solve it by taking meddle in 2D Matrix. and then find. Since from middle element, it could be the shortest path if 3 People are scattered very widely.
I think here we will go for Manhattan distance.
wen we hav to minimize distances for each .. shdnt we look for circumcenter of the triangle ? i cud b terribly wrong also :)
hey abhinav, circumcenter will give you the point equidistant from the three starting points, no reason it will minimise the sum of distances... in fact an easy counterexample can be constructed using a *very* obtuse isosceles triangle
in any case, as Anonymous has commented, manhattan metric is the likely choice here as a mention of grid is made
Gut feeling is that this is a version of TSP and thus NP-complete. I'd try simulated annealing, since there is an easy cost metric that can be incrementally refined in constant time at each iteration.
hi simon, this is a very specific case of the stiener tree problem which is NP-hard. in that prblem in stead of choosing just one point, you get to choose more (and thus the complexity)
here we just need to choose one vertex, so its a stiener-star of sorts and as anonymous has commented on top, for euclidean metric, its just a convex program that can be solved efficiently and up to any desired precision
@Andy2000, after some mathematical calculations, i concluded that the distance will be minimum if we fix the meeting point as one of the person's co-ordinates. Can the meeting point be one of the person's position? If yes, the solution goes simple. O( N^2).
Let me know if i am missing anything.
I also thought the same. If position of one of the member is acceptable then it will give the the shortest distance for 3 as well as for N persons.
I dont see any issue in fixing the point of a one person. Can you pls elaborate the solution?
we have 3 persons means 3 points(X,Y,Z) in 2D plane. Now we choose any point other than these three for meeting, let say M, then join M to these three points. We will have three distances XM,YM,ZM. Now join XZ and YZ, you will find that there are 2 triangles XMZ and YMZ. Now here is the answer, why to go through M when I can directly go to Z from X. and using triangle inequality, XZ will be smaller than XM +MZ. and similarly for YMZ. So, choose Z as meeting point because any other path other than direct straight line will give more distance.
The above solution is not correct. Solution is the point somewhere inside the triangle joining three persons and for equilateral triangle it is center of the triangle.
@Tarun.Yadav, i encourage you to give some counter examples.
Why do you think that there will always exist a triangle with those three co-ordinates? The positions can be co-linear.
Co-linearity is a case not a general case. in general case they will make a triangle.
Counter example of for putting one of the person as meeting point is equilateral triangle. (all are equi-distance from each other and distance is A).
Let say meeting point is centroid of triangle, we know for equilateral distance of centroid to vertex is A/root(3). so if all three come to centroid distance total sum is 3*A/root(3) which is A*root(3)=1.732*A.
But if one of them is meeting point then total distance covered by other two is A+A=2A.
Here I am not stating that Centroid is the always the right answer but I am proving that making one of the person is not the correct because it fails in case of equilateral triangle case.
Surely the answer is the centroid or "average" of the positions of the N people.
Let the position of person i be x_i, and a hypothesized meeting point be m. Then we want to find the m which minimizes the following
J(m) = \sum_{i=1}^N ||x_i - m||^2.
The easiest way to minimize this is take its derivative and set to zero. This gives us:
\nabla_m(J(m)) = \sum_{i=1}^N 2(x_i - m)
which equals
-2Nm + 2\sum_{i=1}^N x_i
Now setting this derivative to zero we see that
m = 1/N \sum_{i=1}^N x_i
which is the centroid of the people's locations.
I hope you don't mind the pseudo-latex code :-)
This is correct only for if the persons are on the same line. On a 2D grid, it is different though and its mathematical proof is difficult. I can only think of Brute forcing here which is pretty bad I know.
I think I can propose something and for N > 3, it can be generalized.
// y = mx+c notation
Struct line_t
{
int x;
int y;
int slope;
};
We have to create 3 lines which pass through each of the three given positions and are perpendicular to the other two.
like, Line 1: passes through A, and is perpendicular to BC.
Line 2: passes through B, and is perpendicular to AC.
and line 3 similarly.
these lines can be got by just finding the line y = mx+c, where m is the perpendicular slope of the other two lines. ( if m1 is the slope of BC, then the line through A should have slope -1/(m1).)
After your get two lines find thier intersection.
Now we gotta retrieve these two lines in our structs.
have a function similar to this.
void (int &x, int &y, struct line *line1, struct line *line2)
{
// just do the mathematical equivalent of finding the intersection of two lines..
multiply(line1, line2->y);
multiply(line2, line1->y);
// Im equating the mx + c with each of the y cordinate.
// now two lines will have equal y cordinate.
// *x = solve (line1, line2); // simply equate mx+c term and retrieve x;
// now use *x, line to get y.
// x , y is the required solution
}
Now every N greater than 3, break it down into triangles, find the point and again find the nearest of the respective points which are obtained. (corner case: if you get two points, find its midpoint and return it) eg: 6 people, 2 triangles, 2 points ==> mid point of these gives the reqd solution.
this is just on top of my mind, and would appreciate if someone has any thoughts to improve this.
I think it can be easily solved using below trick. for a given set of points say.. (x1,y1), (x2,y2), (x3,y3).... we need to find (mx,my) such that manhattan distance from all points to this is minimized. so we need to minimize,
|x1-mx| + |y1-my| +....
Note : here we are adding only positive numbers so if this is minimum then sum of square is also minimum..
(x1-mx)^2 + (y1-my)^2 + .....
expanding and solving we get...
(x1)^2 + (x2)^2 + ...
(y1)^2 + (y2)^2 + ...
- 2 mx * (x1+x2+x3+...)
- 2 my * (y1+y2+y3+...)
+N * mx^2 + N * my^2
so in short we need to minimize the below term..
- 2 mx * (x1+x2+x3+...)
- 2 my * (y1+y2+y3+...)
+N * mx^2 + N * my^2
which indirectly means first minimize it for x and then for y...
Just a thought: Could this be done using BFS, where each node in the graph would look like:
struct node{
int Person1X,Person1Y,Person2X,Person2Y,Person3X,Person3Y;
int steps;
}
While doing the BFS we could put a constraint,
if steps>min(sum of any two edges of the triangle with 3 persons as vertices) return;
Why not do the following (I'm generalizing for N persons):
For each person, find the Xmin, Ymin, Xmax and Ymax. This will form a bounding rectangle. Pick a point inside the rectangle. Cost so far is O(N) in time.
Once at that point, measure distances (L1 or L2 distances) to each person and sum. This is still O(N). Then I would try some gradient descent method as I would "walk" to neighbors to find a minimum.
Question: I can do this all in O(N) time with no significant extra memory... can I prove that the minimum I find is a global minimum and not a local minimum? I did see someone suggesting simulated annealing... similar idea and that might help avoid local minima if that's a problem. Still O(N).
may be it is fermat point of a traingle...
- Anonymous September 05, 2012