Find viewing direction that sees most points
Company: Aurora
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are standing at the origin on a 2D plane. You are given a list of points `points[i] = (xi, yi)` (not necessarily distinct), and a viewing angle `theta` in degrees.
You may choose any viewing **direction** (a ray starting from the origin). Your field of view is the **closed sector** of angular width `theta` whose central axis is your chosen direction (equivalently, a window of size `theta` when sweeping directions around the origin).
A point is considered **visible** if the angle from the positive x-axis to the vector `(xi, yi)` lies within that angular sector (after choosing the sector’s placement). Points exactly on the boundary are visible. If any points are exactly at the origin `(0,0)`, they are always visible regardless of direction.
**Task**: Choose a viewing direction that maximizes the number of visible points.
**Output**:
- Return the maximum number of visible points, and
- Return any one viewing direction (e.g., an angle in degrees in `[0, 360)`) that achieves this maximum.
**Constraints (typical interview scale)**:
- `1 <= n <= 2e5`
- `xi, yi` are integers (e.g., in `[-1e9, 1e9]`)
- `0 < theta <= 360`
Notes:
- Angles wrap around at `360°`.
- Your solution should be better than `O(n^2)`.
Quick Answer: This question evaluates computational geometry skills, angular normalization and counting within a sector, and the ability to design algorithms that scale to large inputs.
Choose a closed angular sector of width theta degrees to maximize visible points from the origin. Return [max_count, direction_degrees]. Ties use the smallest sector start angle, and direction is the sector center rounded to 6 decimals.
Constraints
- Points at (0,0) are always visible
- 0 < theta <= 360
Examples
Input: ([[1, 0], [0, 1], [-1, 0]], 90)
Expected Output: [2, 45.0]
Input: ([[1, 1], [2, 2], [-1, 0], [0, 0]], 1)
Expected Output: [3, 45.5]
Input: ([[1, 0], [0, 1], [-1, 0]], 360)
Expected Output: [3, 0.0]
Hints
- Convert points to polar angles, duplicate with +360, and use a sliding window.