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
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.
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