9

I was asked this question in an interview, have no clue how to solve it. "Given a fixed camera in a forest (with predefined trees), give the best angle in which the camera pictures the maximum of trees" How would you approach it or at least what questions would you ask to get more requirements?

Youcef LAIDANI
  • 55,661
  • 15
  • 90
  • 140
JDD
  • 101
  • 1
  • 6

2 Answers2

8

If trees don't obscure over trees then:

  1. Sort all trees by angle around the camera position.
  2. Use sliding window approach to find direction to look at.

If trees can obscure other trees then the second step is a bit trickier.

Yola
  • 18,496
  • 11
  • 65
  • 106
  • 1
    @JDD you want to rotate you camera and see how many trees are seen from every angle. To do this quickly you need to sort trees. You don't really need to try all possible angles, but only ones for which you have a tree at. You can do it using [sliding windows](https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples) – Yola Nov 21 '19 at 15:20
  • @JDD do you have more follow-up questions? – Yola Nov 27 '19 at 20:37
5

the idea is this:

  1. convert the list of tree coordinates to a list of angles.
  2. sort the list of angles
  3. use a sliding window to find the starting and ending indices that maximize the number of trees.
  4. note: because the best angle to position the camera might actually be very near the 360 degree, you need to take into account trees on the other side of the 360/0 line. The easiest way to handle that is to add duplicate trees to the list (in step 2) with a 360 shift. for example, a tree in degree 10 would be added twice, at degree 10 and 360+10. you don't actually need to add ALL the trees twice - you only really need to duplicate trees in the range 360+camera_angle, but its easy to just duplicate all the trees and it doesn't hurt.
FuzzyAmi
  • 7,543
  • 6
  • 45
  • 79
  • So for a given angle, how does the algo find the number of trees within it? does it loop through the list of tree angles and checks if it the given angle? – Embedded_Mugs Feb 10 '22 at 09:14