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

Hints

  1. Think about one row at a time. In what order must the `1`s in a single row be removed?
  2. 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

  1. While scanning from left to right, ask what complement value you would need to have seen already.
  2. 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

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

Loading coding console...