Solve Reported OA Coding Problems
Company: Upstart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
The post describes several algorithm questions from an online assessment. The concrete problems that can be reconstructed are:
1. **Remove Blocks in a Grid**
You are given an `m x n` grid of `0`s and `1`s, where `1` means a block exists. A block at position `(r, c)` can be removed only if there is no remaining block in the same row at any column `k > c`. Remove blocks one at a time until all blocks are gone, and return any valid removal order as a list of coordinates. If multiple answers exist, return any one of them.
2. **Find Two Indices for a Target Sum**
You are given an integer array `nums` and an integer `target`. Return two distinct indices `i` and `j` such that `nums[i] + nums[j] = target`. If multiple answers exist, return any valid pair. Aim for linear time.
3. **Compute the Minimum Gap**
You are given an integer array `nums`. Return the minimum absolute difference between any two distinct elements in the array.
Quick Answer: This prompt evaluates algorithmic problem-solving skills across grid-based ordering constraints, array pair-sum identification, and minimum-difference computation, testing knowledge of data structures, time/space complexity, and correctness conditions.
Part 1: Remove Blocks in a Grid
You are given a 0-based `m x n` grid containing only `0` and `1`. A cell `(r, c)` with value `1` represents a block. You may remove a block only if there is no remaining block in the same row at any column greater than `c`. Remove blocks one at a time until all blocks are gone, and return one valid removal order as a list of coordinate tuples. If there are no blocks, return an empty list. Any valid order is acceptable; the sample outputs show one possible answer.
Constraints
- `0 <= m, n <= 200`
- Each cell is either `0` or `1`
- If `m > 0`, all rows have the same length
Examples
Input: ([[1, 1, 0], [1, 0, 1]],)
Expected Output: [(0, 1), (0, 0), (1, 2), (1, 0)]
Explanation: Within each row, blocks must be removed from right to left. The shown output processes row 0 first, then row 1.
Input: ([[1, 0, 1, 1]],)
Expected Output: [(0, 3), (0, 2), (0, 0)]
Explanation: In a single row, only the rightmost remaining block can be removed at each step.
Input: ([[0, 0], [0, 0]],)
Expected Output: []
Explanation: There are no blocks to remove.