Interesting Media.net interview question.

Revision en2, by CHRONOS7, 2023-08-10 22:31:09

We are given an integer k (size of an interval) and an array A. Since we know every element in the array can be a part of at most k intervals of size k, we need to construct an array B where B[i] represents the maximum value of

abs(A[i] — p) — abs(A[i] — q)

over all intervals that A[i] is part of(at most k intervals), here p denotes the maximum value in the interval and q represents the minimum value in the interval.

Expected time complexity is O(n).

Tags interview, problem

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English CHRONOS7 2023-08-10 22:31:09 14
en1 English CHRONOS7 2023-08-10 22:28:54 513 Initial revision (published)