Rotate matrix and find max lamp coverage
Company: Capital One
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
1) Square-matrix rotation with extra space: Given an n x n integer matrix, return a new matrix that is the 90-degree clockwise rotation of the input. Extra space is allowed; target O(n^
2) time. Then explain how to perform the rotation in-place and compare time/space trade-offs. Describe edge cases (e.g., 1x1, 2x2, odd/even n, negative values) and basic tests.
2) One-dimensional lamp coverage maximum: You are given N lamps on a number line. Lamp i at position xi illuminates the closed interval [xi - ri, xi + ri]. Compute the maximum number of lamps illuminating any point and output all maximal closed segments where this maximum occurs, merged and sorted by coordinate. Constraints: 1 ≤ N ≤ 2e5; |xi| ≤ 1e9; 1 ≤ ri ≤ 1e9. Design an O(N log N) time, O(N) space algorithm (e.g., sweep line) and justify correctness and complexity. Discuss how results change for open intervals or integer-only coordinates.
Quick Answer: This question evaluates array and matrix manipulation, in-place algorithm design, interval processing (sweep-line) and interval merging skills, testing competencies in algorithm design, complexity analysis, and robust edge-case reasoning within the Coding & Algorithms domain.
