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.

Implement stream queries and bounded-difference subarrays

Q: Implement stream queries and bounded-difference subarrays

This question evaluates proficiency in data structures and algorithmic problem-solving, covering streaming uniqueness tracking (first-non-repeated element) and range-bounded contiguous subarray computation (max-min constraints).

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Solve both coding tasks. ### Task 1: Track the first non-repeated number in a stream Design a data structure that supports a stream of integers. Implement the following operations: - `FirstUnique(int[] nums)`: initializes the data structure with the given initial stream values, in order. - `int showFirstUnique()`: returns the first integer in insertion order that has appeared exactly once so far. If no such integer exists, return `-1`. - `void add(int value)`: appends `value` to the stream. Example: ```text Input: FirstUnique([2, 3, 5]) showFirstUnique() -> 2 add(5) showFirstUnique() -> 2 add(2) showFirstUnique() -> 3 add(3) showFirstUnique() -> -1 ``` Design the data structure so that each operation is efficient for a long stream. ### Task 2: Find the longest bounded-difference subarray Given an integer array `nums` and an integer `limit`, return the length of the longest contiguous subarray such that the absolute difference between any two elements in the subarray is less than or equal to `limit`. Equivalently, for a subarray `nums[l..r]`, it is valid if: ```text max(nums[l..r]) - min(nums[l..r]) <= limit ``` Example: ```text Input: nums = [8, 2, 4, 7], limit = 4 Output: 2 Explanation: The longest valid subarray is [2, 4]. ``` ```text Input: nums = [10, 1, 2, 4, 7, 2], limit = 5 Output: 4 Explanation: The longest valid subarray is [2, 4, 7, 2]. ```

Quick Answer: This question evaluates proficiency in data structures and algorithmic problem-solving, covering streaming uniqueness tracking (first-non-repeated element) and range-bounded contiguous subarray computation (max-min constraints).

Part 1: First Unique Number in a Stream

You are given an initial stream of integers and a list of operations to perform on the stream. Instead of implementing a class, write a function that processes all operations and returns the answer for each query. Each operation is encoded as a pair [op, value]: [1, x] means append x to the stream, and [2, 0] means return the first number, in insertion order, that appears exactly once so far. If no such number exists, return -1 for that query. Return a list of answers for all query operations in order.

Constraints

0 <= len(nums) <= 100000
0 <= len(operations) <= 100000
Each operation is a pair [op, value] where op is either 1 or 2
For op = 1, -10^9 <= value <= 10^9
For op = 2, the second number is ignored
The returned list may be empty if there are no query operations

Examples

Input: ([2, 3, 5], [[2, 0], [1, 5], [2, 0], [1, 2], [2, 0], [1, 3], [2, 0]])

Expected Output: [2, 2, 3, -1]

Explanation: This matches the example sequence: first unique starts as 2, stays 2 after adding 5, becomes 3 after adding 2, and becomes -1 after adding 3.

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

Expected Output: [-1, 10, -1]

Explanation: Edge case with an empty initial stream. Before any add, there is no unique number.

Input: ([7, 7, 7, 7], [[2, 0], [1, 3], [2, 0], [1, 3], [2, 0]])

Expected Output: [-1, 3, -1]

Explanation: All initial values are repeated. Adding 3 makes it unique temporarily, then adding 3 again removes it.

Input: ([5, 6], [[1, 5], [1, 7]])

Expected Output: []

Explanation: There are no query operations, so the returned list is empty.

Hints

Use a hash map to count how many times each value has appeared.
Keep a queue/deque of numbers that were unique when first seen, and remove invalid ones from the front only when needed.

Part 2: Longest Bounded-Difference 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 elements in that subarray is at most limit. In other words, for a valid subarray nums[l..r], max(nums[l..r]) - min(nums[l..r]) <= limit.

Constraints

0 <= len(nums) <= 100000
-10^9 <= nums[i] <= 10^9
0 <= limit <= 10^9

Examples

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

Expected Output: 2

Explanation: The longest valid subarray is [2, 4], whose max-min difference is 2.

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

Expected Output: 4

Explanation: The longest valid subarray is [2, 4, 7, 2], with max 7 and min 2.

Input: ([4, 2, 2, 2, 4, 4, 2, 2], 0)

Expected Output: 3

Explanation: With limit 0, all numbers in a valid subarray must be equal. The longest such run is [2, 2, 2].

Input: ([], 3)

Expected Output: 0

Explanation: Edge case: an empty array has no subarrays, so the answer is 0.

Input: ([-1, -2, -3], 2)

Expected Output: 3

Explanation: The whole array is valid because max = -1, min = -3, and their difference is 2.

Hints

Try a sliding window: expand the right end, and if the window becomes invalid, move the left end forward.
To check the window quickly, maintain the current maximum and minimum using two monotonic deques.

Quick Overview

This question evaluates proficiency in data structures and algorithmic problem-solving, covering streaming uniqueness tracking (first-non-repeated element) and range-bounded contiguous subarray computation (max-min constraints).