Coding questions · Waymo
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.
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:
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:
Input: nums = [10]
Output: 0
Constraints:
1 <= nums.length <= 1000000 <= nums[i] <= 1000000000- The expected solution should use a bucket-based linear-time approach.
Find Largest Adjacent Sorted Difference
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.