Google interview experiences | SDE | Set-3

Question

All interview experiences for Google  can be found using the tag "google_interview_experiences" in the search bar.

Here is the link : https://www.desiqna.in/tag/google_interview_experiences

Answer 1

Got this question in the first round of Onsite interview and wasn't able to code the solution almost all the time went into discussion around it. If anyone can help that would be helpful.

 

A mountain can be simplified as an isoceles right triangle, whose base rests on the x-axis. The two sides of the mountain are both at 45 degress to the base so the peak of the mountain forms a right angle.
All the mountains are the same color so a mountian is invisible if its peak lies on or within the triangular shape of any other mountain.
Given a list of positions of all the mountain's peaks (x-y coordinates). Output the number of visible mountains.

 

Example:

 

Input:

 

1. (4, 6)
2. (7, 2)
3. (2, 5)

 

Output: 2

 

Point to note:

 

1. here the peak visible are 1 and 3
2. Mountains are of the same colour so you have to find the peaks which are visible. The question eventually was about the area covered by a triangle; if any peak point comes into that triangle, then that peak is not visible.