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,
- Choose an index 𝑖 and an integer 𝑥, where 0 ≤ 𝑥 ≤ 10^18.
- 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.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.