4 ms·
It could be improved yes. Earlier I noticed I only split the array into two and not into m pieces. So later went on a tangent on finding the best way to do th
by mixmastamyk 7y ago
It could be improved yes. Earlier I noticed I only split the array into two and not into m pieces. So later went on a tangent on finding the best way to do that. But, I made the test case happy.
Also it says the length of the array is under 1000, so such an optimization is unnecessary.
The point though is that I probably couldn't do the basic solution with a gun to my head, much less an optimized one. One whiff of struggle and I'd panic and it'd be over at that point. I get very good reviews on my work under normal conditions.
Expecting an optimized, "original" work in a watched/timed environment is ridiculous imho. Interviewer is clueless and destined for failure.
I'll keep this link however. Next time a poor interviewer comes to me with similar I'll first state, I don't do 'swordfish' problems. If they insist, I'll challenge them to this one first. :D
- dominotw 7y agook this is what i got def splitArray(self, nums: List[int], m: int) -> int: @lru_cache(maxsize=None) def minSum(pos,count): currentSum = 0 minSoFar = float("inf") for i in range(pos,len(nums)): currentSum+=nums[i] if count !=1: next = minSum(i+1,count-1) maxSplit = max(currentSum,next) minSoFar = min(minSoFar,maxSplit) return currentSum if count ==1 else minSoFar return minSum(0,m) I think putting that @lru_cache annotation is what makes this a Dynamic programming problem. If thats the case, i think its resonable interview question.