Amazon | OA Coding Questions and Solutions | Set - 7 | 2022

Question

All past online assesments of Amazon can be found using the tag "amazon_oa" in the search bar.

Here is the link : https://www.desiqna.in/tag/amazon_oa

Answer 1

Amazon warehouse has a group of n items of various wirghts lined up in a row. A segment of contiguously placed items can be shipped ogether if only if the difference betweeen the weihts of the heaviest and lightest item differs by at most k to avoid load imbalance.

 

Given the weights of the n items and an integer k, fine the number of segments of items that can be shipped together.

 

Note: A segment (l,r) is a subarray starting at index l and ending at index r where l less than equal(<=) r.

 

Example
k=3
weights = [1, 3, 6]

 

weight difference between max and min for each (l,r) index pair are:

 

• (0,0) -> max(weights[0]) - min(weights[0]) = max(1)-min(1) = 1-1 =0
• (0,1) - > max(weights[0],weights[1]) - min(weights[0],weights[1])= max(1,3)-min(1,3)=3-1=2
• (0,2) - > max(weights[0],weights[1],weights[2]) - min(weights[0],weights[1],weights[2])= max(1,3,6)-min(1,3,6)=6-1=5
• (1,1) -> max(weights[1]) - min(weights[1]) = max(3)-min(3) = 3-3 =0
• (1,2) -> max(weights[1],weights[2]) - min(weights[1],weights[2]) = max(3,6)-min(3,6) = 6-3 =3
• (2,2) -> max(weights[2])-min(weights[2]) = max(6)-min(6) = 6-6 =0

 

as only 5 out 6 pair, is less than equal equal to k (3) , so the number of segemets that can shipped together is 5.

 

Constraints

 

• 1<=k, weights[i] <=10^9
• 1 <= n <=3*10^5