3 ms·

I think market now has moved on to leetcode DP/hard in ~30 mins. I got this in my last phone screen at tier 2-3 shop https://leetcode.com/problems/split-array

I think market now has moved on to leetcode DP/hard in ~30 mins. I got this in my last phone screen at tier 2-3 shop https://leetcode.com/problems/split-array-largest-sum/ https://leetcode.com/problems/split-array-largest-sum/

vmception 6y ago
DP? and yes, I got good at the easy problems, which would be all that appears in some interviews. In other interviews I could tell or got feedback that I was close to the bar, which is about 30 minutes. Or if I had an opportunity to finish a harder question later after the interview, I could tell that writing a working solution would have still taken me MUCH longer.
- dominotw 6y ago
  > DP? Dynamic programming, for the problem I linked. Oh maybe I am having bad luck I got hit with another DP/Hard , https://leetcode.com/problems/word-ladder-ii/ https://leetcode.com/problems/word-ladder-ii/ at company called ' The Trade Desk' , which i believe is no where near Tier 1/2 tech companies. Exhaustive graph search ins't an acceptable solution.
  - vmception 6y ago
    what is an acceptable solution? what criteria does the acceptable solution solve such as computation time and space, or is that a factor at all?
    - dominotw 6y ago
      Not sure. Thats what interviewer told me before he failed me. I am guessing he was expecting some sort of caching, memo soln.
mixmastamyk 6y 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 6y 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 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.

vmception 6y ago

DP? and yes, I got good at the easy problems, which would be all that appears in some interviews. In other interviews I could tell or got feedback that I was close to the bar, which is about 30 minutes. Or if I had an opportunity to finish a harder question later after the interview, I could tell that writing a working solution would have still taken me MUCH longer.

dominotw 6y ago
> DP? Dynamic programming, for the problem I linked. Oh maybe I am having bad luck I got hit with another DP/Hard , https://leetcode.com/problems/word-ladder-ii/ https://leetcode.com/problems/word-ladder-ii/ at company called ' The Trade Desk' , which i believe is no where near Tier 1/2 tech companies. Exhaustive graph search ins't an acceptable solution.
- vmception 6y ago
  what is an acceptable solution? what criteria does the acceptable solution solve such as computation time and space, or is that a factor at all?
  - dominotw 6y ago
    Not sure. Thats what interviewer told me before he failed me. I am guessing he was expecting some sort of caching, memo soln.

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