DP in LinkedIn Technical Phone screen?
Does LinkedIn ask DP problems in technical phone screen or on-site? I live in terror of DP problems 😥 and I have a phone interview tomorrow with LinkedIn. The problem I'm trying to understand right now: Perfect Sum problem: nums = [2, 3, 5, 6, 8, 10] K = 10 Find all subsets that add up to k. On g4g it uses a dp table. Them bastards. 😕 Anyways will LinkedIn ask such evil 😈 questions?
Was asked https://leetcode.com/problems/word-ladder-ii/description/ on site
Not too hard to solve, but, it's a lot to code on whiteboard
From my experience the best way to handle DP problems is as follows (very easy) 1. Write a recursive solution 2. In your recursive function do the following: a. At the very top check if table has the result you are looking for and return DP[x] b. Just before the last return statement save the result into the table: DP[x] = result Return DP[x]
Yeah that's memoization / caching already computed results. Bottom up DP is the part that I never get very well. I read bottom up solutions, and they often build a 2d or 3d table of indicies or counts or booleans. And it never really is clear looking at a bottom up do table what any one entry represents
A lot of the bottom up solutions seem to come from nowhere
This seems like an O(n) problem, isn’t it?
How?
Store prefix sum in hash. For each i, check if sum - k is in hash
I had LinkedIn phone interview last week. They Didn’t ask DP. Btw this problem can be easily solved using backtracking. I don’t think they will ask you solve using dp.
For the kind of problem you described it would be so much easier to just write recursive solution and slap memoization on top of it. Same complexity, less bullshit.
Generalized 2sum
I'll be interviewing with them soon and heard the same thing re: DP questions. Absolutely hate them :) I wonder if the role you're interviewing matters at all?
For this particular question, summing up all subsets is good enough. The iterative solution of keeping track of all possible sums using a counting array is in programming pearls.
As far as I can remember, I wasn't asked DP in phone screen. But you should expect DP during onsite.
Yes. I was asked one
What were you asked? So I can practice on it. Thanks Were you asked in phone screen or on-site?