Google - Final Round - SDE III
Anonymous User
831

Interviewer joined late & started without any intro

question:
You're optimizing video chunks for streaming. Each chunk has a size represented in a 0-indexed array nums. To ensure smooth playback, chunk sizes must be in non-decreasing order.

You can split any chunk into two smaller chunks whose sizes add up to the original.

For example, if nums = [10,5,8], you can split 10 into [4,6] making it [4,6,5,8].

Return the minimum number of split operations needed to make the array sorted in non-decreasing order.

was able to come up & code O(n^2) soln within 15 mins

He asked to improvise to O(n) which I couldnt

What are my chances?

Comments (9)