> Do folk genuinely get asked problems like that in technical interviews these days?
No idea! I'm still in interview prep mode though so I'm doing the LeetCode contests every weekend. Even if practicing problems like these is over-preparing I think it's probably a good idea for me because I imagine I'll be much more nervous and less performant during an actual live interview.
> Is there supposed to be a linear time solution?
Yes! Using a monotonic stack to find the "pivot points" of the contiguous subarray groups as well as both a prefix-sum array and prefix-product array to calculate the sum of all subarrays in each group in O(1) time after initially building the arrays in linear time.
There are some great explanations in the discussion section. This is one of the few problems that I got stuck on and wasn't able to solve on my own after a couple days of trying. The LeetCode community is awesome though and getting to see how other people solved the problem is a great educational resource.
No idea! I'm still in interview prep mode though so I'm doing the LeetCode contests every weekend. Even if practicing problems like these is over-preparing I think it's probably a good idea for me because I imagine I'll be much more nervous and less performant during an actual live interview.
> Is there supposed to be a linear time solution?
Yes! Using a monotonic stack to find the "pivot points" of the contiguous subarray groups as well as both a prefix-sum array and prefix-product array to calculate the sum of all subarrays in each group in O(1) time after initially building the arrays in linear time.
There are some great explanations in the discussion section. This is one of the few problems that I got stuck on and wasn't able to solve on my own after a couple days of trying. The LeetCode community is awesome though and getting to see how other people solved the problem is a great educational resource.