Quick Overview

This question evaluates array-manipulation and interval-analysis skills, specifically in-place 2D matrix transformations (row/column swaps, reversals, rotations) and determining the point with maximum overlap among one-dimensional illumination intervals.

Implement 2D transforms and find max-lit point

Company: Capital One

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

Part A — 2D array transforms: Given an m×n integer matrix, implement the following in-place operations with clear function boundaries and complexity: ( 1) swapRows(A, i, j) that swaps two row indices i and j; ( 2) swapCols(A, i, j) that swaps two column indices i and j; ( 3) reverseRowOrder(A) that reverses the order of rows (top↔bottom) and reverseColOrder(A) that reverses the order of columns (left↔right); ( 4) rotate90(A, direction) that rotates the matrix by 90 degrees in the specified direction (clockwise or counterclockwise), supporting both square and rectangular matrices (for rectangular, return a new matrix or explain constraints). Specify time and space complexities and any edge-case handling (e.g., empty matrix, single row/column). Part B — most-illuminated point: You are given a list of street lights as pairs (x, r) where x is the light’s coordinate on a 1D line and r is its illumination radius. Each light illuminates the interval [x − r, x + r]. Find the point on the line covered by the maximum number of lights; if multiple points achieve the same maximum coverage, return the smallest such coordinate. Describe and implement an algorithm with optimal time complexity, and analyze time and space.

Quick Answer: This question evaluates array-manipulation and interval-analysis skills, specifically in-place 2D matrix transformations (row/column swaps, reversals, rotations) and determining the point with maximum overlap among one-dimensional illumination intervals.

Rotate a Matrix by 90 Degrees (Clockwise / Counterclockwise)

Given an m x n integer matrix, return a NEW matrix that is the input rotated by 90 degrees in the given direction. The direction is the string "clockwise" or "counterclockwise". The function must support both square and rectangular matrices (the result is an n x m matrix). Handle edge cases: an empty matrix returns an empty list; a single row, single column, or single cell rotates correctly. For a clockwise rotation, the first column of the result (top to bottom) is the first column of the input read bottom to top; equivalently result[i][j] = matrix[m-1-j][i]. For counterclockwise, result[i][j] = matrix[j][n-1-i]. Return the rotated matrix.

Constraints

  • 0 <= m, n
  • direction is exactly 'clockwise' or 'counterclockwise'
  • matrix may be empty, a single row, a single column, or a single cell
  • rectangular matrices are supported: result has shape n x m

Examples

Input: ([[1, 2, 3], [4, 5, 6]], 'clockwise')

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

Explanation: 2x3 rotated clockwise becomes 3x2; first result row [4,1] is the first input column read bottom-to-top.

Input: ([[1, 2, 3], [4, 5, 6]], 'counterclockwise')

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

Explanation: Counterclockwise: first result row [3,6] is the last input column read top-to-bottom.

Hints

  1. A clockwise 90-degree rotation maps input cell (r, c) to output cell (c, m-1-r). Invert this to write the result directly: result[i][j] = matrix[m-1-j][i].
  2. For rectangular matrices the result shape flips to n x m, so you cannot rotate fully in place — allocate the n x m output.
  3. Counterclockwise is the mirror: result[i][j] = matrix[j][n-1-i]. Check single-row and single-column inputs first.

Most-Illuminated Point on a Line

You are given a list of street lights, each as a pair (x, r) where x is the light's integer coordinate on a 1D line and r is its illumination radius. A light illuminates the closed interval [x - r, x + r]. Find the point on the line covered by the maximum number of lights. If several points achieve the same maximum coverage, return the smallest such coordinate. If there are no lights, return None. The maximum-coverage point can always be taken at one of the interval start coordinates (x - r), so a sweep over endpoints gives the optimal answer.

Constraints

  • 0 <= number of lights
  • each light is a pair (x, r) with r >= 0
  • the interval is closed: [x - r, x + r]
  • ties in coverage are broken by the smallest coordinate
  • return None when there are no lights

Examples

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

Expected Output: 3

Explanation: Intervals are [-2,6] and [3,5]. They overlap on [3,5] with coverage 2. The smallest point with coverage 2 is 3.

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

Expected Output: -1

Explanation: Intervals [-1,1] and [4,6] do not overlap; max coverage is 1; the smallest covered coordinate is -1.

Hints

  1. The answer can always be placed at some interval's left endpoint x - r, so you only need to evaluate coverage at those coordinates.
  2. Use a sweep line: emit +1 at x-r and -1 at x+r. Process start events before end events at the same coordinate so a point touched by an interval's edge still counts (closed intervals).
  3. Scan coordinates in increasing order and only update the answer on a STRICT increase in coverage — this automatically returns the smallest coordinate when several points tie for the maximum.

Loading coding console...