How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Capital One.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Capital One during technical interviews.

Rotate matrix and find max lamp coverage | Capital One Coding Question

Quick 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.

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.

Rotate Square Matrix 90 Degrees Clockwise

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 and the target time complexity is O(n^2). The element at input position (i, j) moves to output position (j, n-1-i). Equivalently, the first row of the input becomes the last column of the output, the second row becomes the second-to-last column, and so on. Follow-up to discuss in an interview: how would you rotate the matrix in place (O(1) extra space)? The classic trick is to transpose the matrix and then reverse each row, or to rotate the four corner cells of each concentric ring in groups of four. Compare the trade-offs: the extra-space version is simpler and avoids index-juggling bugs, while the in-place version saves O(n^2) memory at the cost of trickier code. Edge cases to handle: 1x1 (returns itself), 2x2, odd vs even n (odd n has a fixed center element), and negative values (rotation is purely positional, so sign is irrelevant). Input: matrix, an n x n list of lists of integers (n >= 1). Output: a new n x n list of lists representing the clockwise-rotated matrix.

Constraints

1 <= n <= 1000
matrix is square (n x n)
-10^9 <= matrix[i][j] <= 10^9

Examples

Input: ([[1,2,3],[4,5,6],[7,8,9]],)

Expected Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Explanation: Each row becomes a column: row [1,2,3] becomes the last column (top-to-bottom 1,2,3 -> read as col with 1 at bottom).

Input: ([[1,2],[3,4]],)

Expected Output: [[3, 1], [4, 2]]

Explanation: 2x2 clockwise rotation; top-left 1 moves to top-right.

Input: ([[42]],)

Expected Output: [[42]]

Explanation: 1x1 matrix rotates to itself.

Input: ([[-1,-2],[-3,-4]],)

Expected Output: [[-3, -1], [-4, -2]]

Explanation: Negative values rotate positionally just like positive ones.

Input: ([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]],)

Expected Output: [[13, 9, 5, 1], [14, 10, 6, 2], [15, 11, 7, 3], [16, 12, 8, 4]]

Explanation: 4x4 (even n): first column of output is the bottom row of input read upward.

Input: ([[0,5],[-7,3]],)

Expected Output: [[-7, 0], [3, 5]]

Explanation: Mixed signs and zero; purely positional.

Hints

Element (i, j) of the input lands at (j, n-1-i) of the output. Allocate a fresh n x n matrix and scatter each element into its destination.
Equivalently, the i-th row (read left to right) becomes the (n-1-i)-th column (read top to bottom).
For the in-place follow-up: transpose the matrix (swap matrix[i][j] with matrix[j][i] for i < j), then reverse each row.
Rotation only moves elements around, so negative values and the center cell of an odd-sized matrix need no special handling.

Maximum Lamp Coverage on a Number Line

You are given N lamps on a number line. Lamp i sits at position x_i and illuminates the closed interval [x_i - r_i, x_i + r_i]. Each lamp is given as a pair [x_i, r_i]. Compute the MAXIMUM number of lamps that illuminate any single point, and return that maximum together with ALL maximal closed segments where this maximum is achieved, merged and sorted by coordinate. A segment [lo, hi] means every point p with lo <= p <= hi is illuminated by exactly the maximum number of lamps, and the segment is maximal (cannot be extended left or right while keeping that count). Return a tuple (max_count, segments) where segments is a list of [lo, hi] closed intervals sorted by lo. Design an O(N log N) time, O(N) space sweep-line algorithm: turn each lamp into a +1 event at its left endpoint and a -1 event that takes effect just after its right endpoint, sweep across sorted critical coordinates while tracking the running coverage, and record the closed coordinate ranges where coverage equals the global maximum. Because intervals are CLOSED, a point where one interval starts and another ends counts both, so order start events before end events at equal coordinates. Follow-ups to discuss: for OPEN intervals the endpoints would no longer count, shrinking the max segments to open intervals; for integer-only coordinates the answer can be reported as a set of integer ranges, and you can compare coverage only at integer sample points. Input: lamps, a list of [x, r] integer pairs (1 <= N <= 2e5, |x| <= 1e9, 1 <= r <= 1e9). Output: (max_count, segments) as described.

Constraints

1 <= N <= 2*10^5
-10^9 <= x_i <= 10^9
1 <= r_i <= 10^9
Intervals are CLOSED: [x_i - r_i, x_i + r_i]

Examples

Input: ([[0,2],[3,2],[6,2]],)

Expected Output: (2, [[1, 2], [4, 5]])

Explanation: Intervals [-2,2], [1,5], [4,8]. First two overlap on [1,2] (count 2); last two overlap on [4,5] (count 2). Max is 2 on those two closed segments.

Input: ([[5,3]],)

Expected Output: (1, [[2, 8]])

Explanation: Single lamp covers [2,8] with count 1 everywhere inside it.

Input: ([[0,1],[0,1],[0,1]],)

Expected Output: (3, [[-1, 1]])

Explanation: Three identical intervals [-1,1] stack to count 3 across the whole shared segment.

Input: ([[0,1],[10,1]],)

Expected Output: (1, [[-1, 1], [9, 11]])

Explanation: Two disjoint lamps; max count is 1 achieved separately on each interval.

Input: ([[0,5],[1,1],[8,1]],)

Expected Output: (2, [[0, 2]])

Explanation: Intervals [-5,5], [0,2], [7,9]. The big lamp and the small lamp at 1 overlap on [0,2] (count 2); the lamp at 8 only overlaps nothing else, so the unique max segment is [0,2].

Input: ([[-3,2],[2,3]],)

Expected Output: (2, [[-1, -1]])

Explanation: Intervals [-5,-1] and [-1,5] touch only at the single closed point -1, where both count, giving a degenerate max segment [-1,-1].

Hints

Convert each lamp into the closed interval [x - r, x + r]. The coverage at a point p is (number of intervals whose left endpoint <= p) minus (number whose right endpoint < p) — two binary searches over sorted endpoint arrays.
Coverage is a step function that only changes at the 2N endpoint coordinates. The maximum is achieved on a union of closed regions whose boundaries are these critical coordinates.
Sweep the sorted distinct critical coordinates. Evaluate coverage both AT each critical point and ON the open gap to its right; record every region whose coverage equals the global maximum, then merge adjacent max regions into maximal closed segments.
Because intervals are closed, a coordinate where one interval starts and another ends still counts both — process start (+1) events before end (-1) events at equal coordinates.
Follow-up: for OPEN intervals the endpoints stop counting, so max segments become open; for integer-only coordinates you only need to compare coverage at integer points.

Quick Overview