Solve Reported OA Coding Problems | Upstart Coding Question

Quick Overview

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.

Solve Reported OA Coding Problems

Company: Upstart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

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.

Overview: 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.

Hints

Think about one row at a time. In what order must the `1`s in a single row be removed?
Rows do not affect each other, so once each row order is known, you can combine the rows in any convenient way.

Part 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 one of them. If no such pair exists, return an empty list. Aim for linear time.

Constraints

`0 <= len(nums) <= 100000`
`-10^9 <= nums[i], target <= 10^9`
Indices in the answer must be distinct

Examples

Input: ([2, 7, 11, 15], 9)

Expected Output: [0, 1]

Explanation: Because `2 + 7 = 9`.

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

Expected Output: [1, 2]

Explanation: Because `2 + 4 = 6`.

Hints

While scanning from left to right, ask what complement value you would need to have seen already.
A hash map from value to index can find that complement in O(1) average time.

Part 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. If the array contains fewer than two elements, return `None`.

Constraints

`0 <= len(nums) <= 200000`
`-10^9 <= nums[i] <= 10^9`

Examples

Input: ([3, 8, 15, 17],)

Expected Output: 2

Explanation: The smallest difference is `17 - 15 = 2`.

Input: ([1, 5, 3, 19, 18, 25],)

Expected Output: 1

Explanation: After sorting, `18` and `19` are adjacent and differ by `1`.

Hints

After sorting, the closest pair must appear next to each other.
Be careful with the edge case where the array has fewer than two numbers.

Approach

Approach: per-row right-to-left greedy.

The removal rule says a block at (r, c) may be removed only when no block remains in the same row at any column > c. Rows are independent — a block's eligibility depends solely on what is still present to its right in its own row. So the whole problem decomposes into handling each row separately.

For a single row, if we always peel off the rightmost remaining block first and move leftward, then at the moment we remove any block every block to its right has already been removed, so the rule is satisfied. That is exactly what the code does:

Key steps

Guard the empty grid (if not grid: return []).
For each row index r, walk columns from len(row)-1 down to 0.
Append (r, c) for every cell equal to 1.

Why it's correct. Within a row, blocks are emitted in strictly decreasing column order, so the right-neighbor constraint holds for each removal. Rows never interact, so concatenating each row's order yields a globally valid sequence. The problem allows any valid order, and this is one. The single if not grid guard also covers m = 0; an empty inner row simply contributes nothing.

Time complexity:

O(m * n)

Space complexity:

O(1) auxiliary, excluding the output list (which holds B entries, one per block, B <= m * n)