Rotate matrix and find max lamp coverage
Overview
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.
Capital One
Sep 6, 2025, 12:00 AM
Machine Learning Engineer
Take-home Project
Coding & Algorithms
0
0
- 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^
- 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.
- 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.