k-Radius Average Databricks Python Interview Question

You're given an array of integers and an integer .

The k-radius average for a subarray of centered at some index is the average of all elements from indices to (inclusive). If there aren’t enough elements before or after index to cover this radius, the k-radius average is .

Build and return an array of length , where contains the k-radius average for the subarray centered at index .

Return your result rounded to 2 decimal places.

p.s. before you tackle this challenge, maybe try this related warmup problem from Walmart called Average Subarray (where you find the maximum average of any subarray of length ).

Example #1

Input: nums = [7, 2, 5, 12, 9, 4, 1], k = 2

Output: [-1, -1, 7.0, 6.4, 6.2, -1, -1]

Explanation:

1. For i = 0, i = 1, i = 5 and i = 6, we can’t calculate a k-radius average since there aren’t enough elements before or after these indices, that is why the value at those indexes is -1.

2. For i = 2, we calculate the average of the subarray from nums[0] to nums[4], which gives us: $(7 + 2 + 5 + 12 + 9)/5 = 35/5 = 7.0$

3. For i = 3, we calculate the average of the subarray from nums[1] to nums[5], which gives us:
   $(2 + 5 + 12 + 9 + 4)/5 = 32/5 = 6.4$

4. For i = 4, we calculate the average of the subarray from nums[2] to nums[6], which gives us:
   $(5 + 12 + 9 + 4 + 1)/5 = 31/5 = 6.2$

Brute Force Approach

Like we did in the first part of this problem, the most straightforward approach would be to start at each point of the array. From there, we’ll move elements to the left and elements to the right, checking whether we have enough elements on both sides. Once we confirm there are enough elements, we will sum all the values in this subarray and then update the current index by dividing the total sum by the number of elements (). This will give us the average for that subarray.

Implementation

First, we initialize our answer () with , so that if we don’t have enough elements on either side, no further action is needed. One special case to handle is when is —in this case, we just return the original array itself. The number of elements in a -centered subarray can be calculated as .

Here’s the brute force solution:

Prefix Sum Approach

Intuition

If you’re not familiar with the prefix sum technique, it’s a popular strategy used to calculate ranges of sums efficiently. Instead of recalculating sums from scratch each time, we store cumulative sums, allowing us to compute any subarray sum in constant time.

Consider the array: and .

The prefix sum would look like this:

Each number in represents the sum of all elements up to, but not including, the current index. So, means that the sum of the first three elements in is .

Example

Let's say we want to find the sum of the subarray . Using the prefix sum, we simply subtract from :

This is way faster than recalculating the sum from scratch!

Implementation

Once we construct the prefix sum, we initialize our array with using . This ensures that each element in starts as . Then, we iterate through indices from to , finding the sum of the -radius subarray at each valid index, and updating the averages accordingly.

Here’s the code:

Sliding Window Approach

The sliding window technique is a step up from the brute force method. Instead of recalculating the sum of the entire subarray each time, we maintain a running sum of the current -centered subarray and update it efficiently as we "slide" the window across the array.

Intuition

Here’s how it works:

1. Sum the first -centered subarray to initialize the window.
2. As we move the window one element to the right, we add the new element and subtract the element that is now out of the window.
3. Update the average for the current index accordingly.

Here’s the implementation: