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 Onsite rounds at Uber.

What role is this question designed for?

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

Find a Bounded Subarray and Largest Square

Quick Overview

This question evaluates array manipulation and algorithmic problem-solving skills across two tasks: enforcing bounded value ranges within contiguous subarrays and identifying largest uniform square regions in binary matrices, exercising concepts such as range-tracking, efficient data structures, and dynamic programming.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement the following two independent coding tasks. ### Task A: Longest bounded-range subarray Given an integer array `nums` and an integer `limit`, return the length of the longest contiguous subarray such that the difference between the maximum and minimum values inside that subarray is at most `limit`. Example: - Input: `nums = [8, 2, 4, 7]`, `limit = 4` - Output: `2` - Explanation: The longest valid subarray is `[2, 4]` or `[4, 7]`. Constraints: - `1 <= nums.length <= 100000` - `-1000000000 <= nums[i] <= 1000000000` - `0 <= limit <= 1000000000` ### Task B: Largest square area in a binary grid Given an `m x n` binary matrix `grid` containing only `0`s and `1`s, return the area of the largest square containing only `1`s. Example: - Input: `grid = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]` - Output: `4` - Explanation: The largest all-`1` square has side length `2`, so its area is `4`. Constraints: - `1 <= m, n <= 300` - `grid[i][j]` is either `0` or `1`.

Quick Answer: This question evaluates array manipulation and algorithmic problem-solving skills across two tasks: enforcing bounded value ranges within contiguous subarrays and identifying largest uniform square regions in binary matrices, exercising concepts such as range-tracking, efficient data structures, and dynamic programming.

Part 1: Longest Bounded-Range Subarray

Given an integer array `nums` and an integer `limit`, find the length of the longest contiguous subarray such that the difference between the maximum and minimum values inside that subarray is at most `limit`. You must return only the length, not the subarray itself.

Constraints

1 <= len(nums) <= 100000
-1000000000 <= nums[i] <= 1000000000
0 <= limit <= 1000000000

Examples

Input: ([8, 2, 4, 7], 4)

Expected Output: 2

Explanation: The longest valid subarrays are `[2, 4]` and `[4, 7]`, both of length 2.

Input: ([10, 1, 2, 4, 7, 2], 5)

Expected Output: 4

Explanation: The subarray `[2, 4, 7, 2]` has max 7, min 2, and difference 5, so the answer is 4.

Hints

A sliding window is a good fit because the subarray must be contiguous.
To expand and shrink the window efficiently, maintain the current minimum and maximum using monotonic deques.

Part 2: Largest Square Area in a Binary Grid

Given an `m x n` binary matrix `grid` containing only `0`s and `1`s, return the area of the largest square that contains only `1`s. The area of a square is its side length multiplied by itself.

Constraints

1 <= m, n <= 300
grid[i][j] is either 0 or 1

Examples

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

Expected Output: 4

Explanation: The largest all-1 square has side length 2, so its area is 2 * 2 = 4.

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

Expected Output: 1

Explanation: There is no 2x2 square of 1s, but there are individual 1 cells, so the largest area is 1.

Hints

Think about the largest square that can end at each cell.
If a cell contains 1, its square size depends on the top, left, and top-left neighboring cells.