3 ms·
Just did that one, didn't find the actual coding hard at all. But, just understanding what it wanted took a lot of time which would make me nervous, which woul
by mixmastamyk 7y ago
Just did that one, didn't find the actual coding hard at all. But, just understanding what it wanted took a lot of time which would make me nervous, which would make me look stupid under the gun.
I don't think I could do it confidently with someone looking over my shoulder, clock ticking, and $200k in sitting in a suitcase.
- dominotw 7y ago> 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 7y agoIt 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.