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

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Upstart during technical interviews.

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

Input: ([],)

Expected Output: []

Explanation: An empty grid has an empty removal order.

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

Input: ([3, 3], 6)

Expected Output: [0, 1]

Explanation: The same value can be used twice as long as the indices are different.

Input: ([5], 10)

Expected Output: []

Explanation: A single element cannot form a pair.

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

Expected Output: [2, 4]

Explanation: Because `-3 + -5 = -8`.

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

Input: ([-10, -3, 0, 4],)

Expected Output: 3

Explanation: The smallest absolute difference is between `-3` and `0`.

Input: ([7, 7, 20],)

Expected Output: 0

Explanation: Two equal values give an absolute difference of `0`.

Input: ([42],)

Expected Output: None

Explanation: There are not enough elements to form a pair.

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.

Quick Overview