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 Technical Screen rounds at Waymo.

What role is this question designed for?

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

Find Largest Adjacent Sorted Difference

Q: Find Largest Adjacent Sorted Difference

This question evaluates skills in array processing, linear-time algorithm design, and application of bucket-based, non-comparison techniques for computing maximum adjacent gaps after sorting.

Company: Waymo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an unsorted array of integers `nums`, compute the largest difference between two consecutive elements after the array is sorted in ascending order. Return `0` if the array has fewer than two elements. Your algorithm must run in `O(n)` time and use `O(n)` extra space. A comparison-based sort is not allowed. **Example 1:** ```text Input: nums = [3, 6, 9, 1] Output: 3 Explanation: After sorting, nums becomes [1, 3, 6, 9]. The consecutive differences are 2, 3, and 3, so the answer is 3. ``` **Example 2:** ```text Input: nums = [10] Output: 0 ``` **Constraints:** - `1 <= nums.length <= 100000` - `0 <= nums[i] <= 1000000000` - The expected solution should use a bucket-based linear-time approach.

Quick Answer: This question evaluates skills in array processing, linear-time algorithm design, and application of bucket-based, non-comparison techniques for computing maximum adjacent gaps after sorting.

Given an unsorted array of integers nums, compute the largest difference between two consecutive elements after the array is sorted in ascending order. Return 0 if the array has fewer than two elements. Your algorithm must run in O(n) time and use O(n) extra space. A comparison-based sort is not allowed, so the expected approach is to use buckets and the pigeonhole principle.

Constraints

1 <= len(nums) <= 100000
0 <= nums[i] <= 1000000000
The expected solution must run in O(n) time and use O(n) extra space without using a comparison-based sort

Examples

Input: ([3, 6, 9, 1],)

Expected Output: 3

Explanation: After sorting, the array is [1, 3, 6, 9]. The consecutive differences are 2, 3, and 3, so the largest is 3.

Input: ([10],)

Expected Output: 0

Explanation: There is only one element, so there are no consecutive pairs.

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

Expected Output: 0

Explanation: All values are identical, so every adjacent difference after sorting is 0.

Input: ([1, 1000000000],)

Expected Output: 999999999

Explanation: With two elements, the only adjacent difference after sorting is 1000000000 - 1.

Input: ([10, 3, 6, 15, 14],)

Expected Output: 4

Explanation: Sorted order is [3, 6, 10, 14, 15]. The consecutive differences are 3, 4, 4, and 1, so the answer is 4.

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

Expected Output: 97

Explanation: Sorted order is [1, 2, 3, 100]. The consecutive differences are 1, 1, and 97, so the largest is 97.

Input: ([0, 0, 5, 5, 9],)

Expected Output: 5

Explanation: Sorted order is [0, 0, 5, 5, 9]. The consecutive differences are 0, 5, 0, and 4, so the largest is 5.

Hints

If there are n numbers between a global minimum and maximum, think about dividing the range into buckets of width based on (max - min) / (n - 1).
You do not need to sort the contents of each bucket. Track only the minimum and maximum value in each non-empty bucket, because the largest gap must occur between buckets.

Quick Overview

This question evaluates skills in array processing, linear-time algorithm design, and application of bucket-based, non-comparison techniques for computing maximum adjacent gaps after sorting.