2 ms·

> Just did that one, didn't find the actual coding hard at all. what what the time complexity of your solution? I failed the interview cos n^m soln wasn't acce

> Just did that one, didn't find the actual coding hard at all. what what the time complexity of your solution? I failed the interview cos n^m soln wasn't accepted. he said hes looking for logarithmic soln.

mixmastamyk 6y 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 6y ago
  ok 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.

mixmastamyk 6y 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 6y ago
ok 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.