LinkedIn | OA | Minimum Total Increase In The Stack Size

Round 1

Questions: A team must optimize context switching between processes. There are 𝑛 segments where a thread is assigned to each segment. The maximum stack size of a thread assigned in the 𝑖 th segment is denoted by threadSize[i], for all 1 ≤ 𝑖 ≤ 𝑛.

For any high-priority process, some stack size of the segments must be increased. A segment 𝑖 is said to be special when threadSize[i - 1] < threadSize[i] > threadSize[i + 1]. The segments at each end cannot be special. The stack sizes must be modified in such a way as to maximize the number of special segments. To do so, choose any segment and increase the stack size by 𝑥. More formally,

1. Choose an index 𝑖 and an integer 𝑥, where 0 ≤ 𝑥 ≤ 10^18.
2. Increase the stack size of the 𝑖 th segment from threadSize[i] to threadSize[i] + x.

Find the minimum total increase in the stack size of the segments.

Example

Given n=6, and threadSize = [3, 1, 4, 5, 5, 2].

It is optimal to add 2 and 1 to the third and fifth segments, respectively. The final stack sizes of the segments are [3,1,6,5,6,2].

So the answer = 2 + 1 = 3.