I feel like they're quite possibly the most deceptively simple data structure I've yet to encounter. That is to say that for me at least there was/is a wide gulf between simply understanding what the data structure is (doesn't get much simpler than a stack!) and when/how to actually apply it.
Do folk genuinely get asked problems like that in technical interviews these days? I can't think of any plausible reason why anyone would want to do a calculation as contrived as that. I love the required modulo value too.
I assume the trick is to somehow leverage the distributive property of multiplication to refactor the data to no longer require as much iteration? Is there supposed to be a linear time solution?
> 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.
I feel like they're quite possibly the most deceptively simple data structure I've yet to encounter. That is to say that for me at least there was/is a wide gulf between simply understanding what the data structure is (doesn't get much simpler than a stack!) and when/how to actually apply it.