Google interview question: count bounded slices(min/max queue) - dshao - 博客园

Google interview question: count bounded slices(min/max queue) - dshao - 博客园

A Slice of an array said to be a Bounded slice if Max(SliceArray)-Min(SliceArray)<=K.

If Array [3,5,6,7,3] and K=2 provided .. the number of bounded slice is 9,

first slice (0,0) in the array Min(0,0)=3 Max(0,0)=3 Max-Min<=K result 0<=2 so it is bounded slice

second slice (0,1) in the array Min(0,1)=3 Max(0,1)=5 Max-Min<=K result 2<=2 so it is bounded slice

second slice (0,2) in the array Min(0,1)=3 Max(0,2)=6 Max-Min<=K result 3<=2 so it is not bounded slice

in this way you can find that there are nine bounded slice.

(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (4, 4).

Read full article from Google interview question: count bounded slices(min/max queue) - dshao - 博客园