Google Interview Question Software Engineers
Country: United States
Interview Type: In-Person
But the number of guardians is infinite. In the simple example provided (no reflection) a guardian can be placed at (0.1,0.1) or (0.11,0.11) or (0.111, 0.111) or even (0.511111, 0.511111) and etc.
You are right, the solution (as provided in the example without bullet reflection) is not necessarily unique. This is totally fine, if problem allows multiple solutions it's typically OK to find just one of them.
However, surprisingly, the optimal solution (min. no of guardians) for the case with bullet reflection is unique.
Hint: for the simple example with bullet reflection - you also need only one guardian to protect the victim.
This is actually pretty good interview question.
Describing my thought process which allowed me to find the solution.
First of all, the question is much more complex than initially seems. For each fixed killer and victim positions (minus degenerate cases) there's infinite number of bullet trajectories which are fatal to the victim. Each of those trajectory killing the poor victim from infinite number of angles. How I can protect the victim with finite number of guardians!?
Blocking infinite number of paths with finite number of points is possible if and only if all those fatal paths have finite number of intersection points where we can put guardians. Using reasoning by symmetry those intersection points must be either exactly in the midway of the bullet (center of the trajectory) or at least symmetrical in respect to the center of the trajectory.
I wanted to see the intersection pattern and I decided to draw few trajectories and I confirmed that interesting intersection points are in the middle of the trajectories.
While drawing, I also found that it is very inconvenient to draw all the reflections, so I started to think about the problem in the following way:
Room walls are mirrors, and killer is pointing to the victim with the laser pointer, instead of shooting a bullet. In interpretation version of a problem I need to put guardians in the places to block the killer's view of a victim. It's easy to observe that killer sees infinite number of victim's reflections (except degenerate cases).
Now I can actually draw infinite reflected space on the paper with an infinite grid of reflected room, as seen by killer. Bullet trajectories are now straight lines instead of poly-lines.
If you start drawing the infinite space of reflections described above, you can see that it consists of repeated tiles where each tile is a block of 2x2 rooms. This was my “Aha” moment. I realized that I need to find intersection points using fmod 2 arithmetic (floating point modulo).
A little bit of fmod 2 math for coordinates of intersection points:
(x1+x2)/2 == (x1+x2+2)/2 (fmod2)
(y1+y2)/2 == (y1+y2+2)/2 (fmod2)
showed to me that I don't need to consider all the reflections of the rooms – only the immediate neighborhood: reflections which reflect an x or y coordinate at most once. If A is a room and B is a reflection, this is the only fragment of space I need to consider:
BBB
BAB
BBB
Killer is in A, victim is in the room A, 8 reflections of the victim can be seen in rooms B. In total killer sees 9 victims.
Now, the algorithm:
1) Connect the killer with 9 victims with straight segments and find a middle point of those segments
2) Some middle points might be outside of room A, in this case reflect them back to A.
3) De-duplicate the points (duplicates might occur in previous step).
4) Place guardian to each point
Update: the proof above has a mistake. The fmod2 identities should be written as:
(x1+x2)/2 == (x1+x2+4)/2 (fmod2)
(y1+y2)/2 == (y1+y2+4)/2 (fmod2)
Which tells that 16 rooms has to be considered not 9. So victim needs at most 16 guards.
Could you elaborate more about x1 x2 y1 y2 and how do you understand that only B rooms are needed for consideration?
My thought process
1) Imagine every room is the same, not reflected anyhow, we will fix this later by reflecting guardian positions in all 4 ways
2) now there is one killer on an infinite plane at (k_x, k_y) and infinite victims {(v_x + n, v_y + m) where n, m integer}
3) shift everybody so that killer is at (0, 0)
4) now we have a set of tangents that we need to protect - {(v_y - k + n) / (v_x - k_x + m)
5) protect them by putting guardians at {(v_x - k_x + n) / 2, (v_y - k_y + m) / 2}. Notice that we need only 4 guardians since they are automatically duplicated to all rooms
7) repeat 1) for every 4 positions of reflected victim, now we have 16 guardians
8) shift everything back
> Could you elaborate more about x1 x2 y1 y2
>and how do you understand that only B rooms
>are needed for consideration?
Killer pos: (x1,y1)
Victim pos: (x2,y2) (real one or mirrored within A/B area)
The middle point on the straight line between (x1,y1)-(x2,y2) is
((x1+x2)/2, (y1+y2)/2). This point is obviously withing A/B area.
Now let's look at rooms other than A and B. It's easy to see that if (x2,y2) is a victim position in A/B then all other victim positions have coordinates in a form (x2+2*i, y2+ 2*j) for any pair of integers i,j. Note that if i==j==0 then this matches the original victim positions within A/B.
OK, now let's try to compute a generic form of a midpoint coordinate:
((x1 + x2+2*i)/2, (y1+ y2 + 2*j)/2)
it is easy to see that this is exactly same pair of numbers under fmod2 as ((x1 + x2)/2, (y1+ y2)/2), which means that we already have a guardian there.
Thus, we only need to consider case where i==0 and j==0 which is precisely A/B area.
Let me know if this isn't clear enough, I'll try to explain better.
Follow-up: since there will be not more than 9 victims in A/B area 9 guardians is enough to protect them (after de-mirroring and deduplication there could be less than 9 for some inputs).
How long did it take you to find the answer? Was it realistic to expect that that kind of answer could be found during limited interview time?
It seems to me that you make the assumption that a solution with a finite number of guardians exists in order to find it (this assumtion leads you to make the hypothesis that the guardians must be midway)
I may be wrong, but to me, calculating this way is logically flawed since it does not prove there is no other solution than the solutions you found.
> How long did it take you to find the answer?
About an hour + 10 minutes coding.
> Was it realistic to expect that that kind of answer could be found during limited interview time?
Yes. When those (hard) questions are asked during interview, candidate isn't expected to actually find the solution on his/her own. interviewer usually provides a lot of useful hints which can drive to the answer, and observes how candidate reacts on those.
> It seems to me that you make the assumption that a solution with a finite number of guardians exists in order to find it...
This is find as soon as you prove (later) that the solution is valid.
I use a trick with assumption of existence of solution pretty frequently if I'm blocked, since time to time it allows to deduce some properties of the solution which aren't obvious.
If you look carefully, most part of my explanation is actually about proving that solution is valid. I showed that every trajectory will be blocked (it's kind of obvious when you put a blocking point on a midway of EACH fatal bullet path) and showed that those number of points is finite using fmod 2 artithmetic.
I did not believe you because 9 points should contain some point twice.
There can be 16 points necessary. Each mirror can be described by a pair of even or odd reflections from vertical and horizontal axis. This gives us 4 groups of targets. Consider one group. For this group we can choose arbitrary amount of reflections for the middle point, it gives us 4 combinations for each group.
For points double x1 = 0.25, y1 = 0.125; double x2 = 0.5, y2 = 0.75;
I have the following result:
(0.125, 0.3125)
(0.125, 0.4375)
(0.125, 0.5625)
(0.125, 0.6875)
(0.375, 0.3125)
(0.375, 0.4375)
(0.375, 0.5625)
(0.375, 0.6875)
(0.625, 0.3125)
(0.625, 0.4375)
(0.625, 0.5625)
(0.625, 0.6875)
(0.875, 0.3125)
(0.875, 0.4375)
(0.875, 0.5625)
(0.875, 0.6875)
It can be up to 16 guards needed. We can reflect target so there will be 4 targets. Definitely there are 4 group of reflections. For each group we choose amount of reflections for horizontal and vertical axes of the shooting ray: (even, odd), (even, even), (odd, even), (odd, odd).
x1 = 0.25, y1 = 0.125;
x2 = 0.5, y2 = 0.75;
(0.125, 0.3125)
(0.125, 0.4375)
(0.125, 0.5625)
(0.125, 0.6875)
(0.375, 0.3125)
(0.375, 0.4375)
(0.375, 0.5625)
(0.375, 0.6875)
(0.625, 0.3125)
(0.625, 0.4375)
(0.625, 0.5625)
(0.625, 0.6875)
(0.875, 0.3125)
(0.875, 0.4375)
(0.875, 0.5625)
(0.875, 0.6875)
Yes you are right. My proof has a mistake:
(x1+x2)/2 == (x1+x2+2)/2 (fmod2)
(y1+y2)/2 == (y1+y2+2)/2 (fmod2)
the above is obviously false. It should be re-written as:
(x1+x2)/2 == (x1+x2+4)/2 (fmod2)
(y1+y2)/2 == (y1+y2+4)/2 (fmod2)
We need to consider more reflected rooms:
CCCC
BBBC
BABC
BBBC
or
DDDD
CCCD
BBCD
ABCD
It yields at most 16 points, exactly as you described.
Thanks for pointing to my mistake!
Treat the room as a vector spaces over [0,1] real scalar. It will help in proving that there are infinite solutions even in case where K(0,0) and V(1,1) (ie. the vector 0,0 to 1,1).
Cheers.
I may wrong but it seems to me you base the calculation of a solution with finite guardians on the assumption that such solution exist and thus, you restrain the possible direction to the one that can be solved by such solution.
So it is logically biaised because you only consider the direction that can be stopped by the guardians of such solution, but no the others. More specifically, I think your assumption about the guardians which must be at a symetrical position is not true for every case.
It's OK to derive a hypothesis from any assumption, as soon as you prove the hypothesis later without relying on the original assumption. Instead of describing my thinking process, I could just say that I guessed the hypothesis, without mentioning those assumptions. Assuming that solution exists (without knowing it a priori) and use that assumption derive some properties of the solution, is pretty powerful trick which helped me to solve many algorithmic puzzles.
> I think your assumption about the guardians which must be at a symmetrical position is not true for every case.
Let me expand the symmetry claim to be crystal clear. Let X be a set of all intersection points of fatal bullet trajectories (whether it is finite or not – doesn't matter at this point). The symmetry claim is following: for every fatal path T all points X belonging to T are symmetrical in respect to the center of T. Note, that those symmetry reasonings aren't about guardians yet. Those reasonings only provide hints where it makes common sense to put guardians.
Now, assumption of existence of a solution allows to claim that there exists a finite set G (a subset of X) which covers all the fatal paths. G is obviously a solution and there may be many such Gs. While not all solutions can be constructed as such Gs, it can be shown that every _finite_ solution has one of Gs as a subset. Thus, minimal G must be an optimal solution (min no of guardians). Now, using all other data (fmod 2 and midpoints) it is also possible to prove that the the optimal solution is unique.
A friend of mine suggested an extended version of this problem where we have a rectangular room and consider a cases whether width/height is a rational number or not.
It seems that rational ratio always yields finite solution. The problem can be reduced to the square version with the size of NxN where N = LCM(p,q), and p/q are integers such as p/q=width/height.
Irrational version is awkward to reason about. If we exclude degenerate cases (where line between killer and victim is perpendicular to the walls or is lying on the diagonal) is solution always infinite or is there a class of inputs yielding a finite solution?
is it really google interview question? I wonder what it means, you can put several gaurdian along the ray, would could one count them?
Keeping minimum possible number of guardians is not a requirement in the question. Draw a circle around victim.
- jagtiani.akshay September 08, 2015