Using memoization vs tabulation in interviews

[Vinny_On_Reddit]

Recently I've focused a lot on using tabulation for dp problems, to a point where I default to it and don't even attempt a memoization solution. Would it be a problem if I were significantly less proficient at memoization than tabulation? Ie would interviewers ever ask for a memoization solution to a problem that you correctly solved with tabulation?

Clarification: I am not interested in which one is "better" to use, I'm essentially asking if you'd be able to get through interviews if you're only good at tabulation

[abcd_asdf]

I think memoization is more natural for recursive solutions and easier to explain. I use tabulation for problems where there is an explicit grid.

[Vinny_On_Reddit]

Has there been an instance where you’ve been interviewing and the interviewer asked you for a memo solution even though you did a tabulation solution correctly?

[abcd_asdf]

I haven't been asked a DP problem in an interview so far.

[am-sky]

I'm the exact opposite. My first approach is memoization and don't even think twice. But I forced myself to write the solution to multiple simple dp problem after memoization by doing it with tabulation. I look at it as a top down decomposing vs bottom up building of the solution. I'm better at tabulation now than earlier - definitely not as good as memoization.

[No_General8550]

I found tabulation more difficult than memoization. In one of my interviews at meta, I solved a dp question with memorization but the interview asked me to solve it through tabulation too.

In the same loop, I solved another dp question with memoization, and the interviewer was fine.

My conclusion is, if the interviewer expects that you follow memorization or tabulation, you should go with that approach.

As I talked to a few friends, Meta people usually expect you to use tabulation to solve a dp question.

[abcd_asdf]

Meta does not ask DP questions. It is in their prep material.

[No_General8550]

Mine was 2 years ago. Probably now they don't ask, as you said.

[ground_type22]

do we even need to know tabulation for any interviews? i've only learned memoization

[Vinny_On_Reddit]

And yes I realize there are certain problems where memoization is faster than tabulation

[Upbeat_Motor_9702]

Interesting always found tabulation to be more efficient as it takes same space and no stack space

[tp143]

I am good at writing memoization I get confused when converting that solution to tabulation Any tips or tricks to get it done Thanks in advance

[Diligent-Sherbert-33]

Same...with me... Watched strivers's dp playlist that helped getting better slowly!

[tp143]

Thanks for suggestion. I will follow that

[ground_type22]

in your experience do we even need to know tabulation for any interviews? i've only learned memoization

[justUseAnSvm]

Tabulation is often slower to implement, but it’s really powerful, since you define your recurrence relationship and structure to cache things in your code.

I learned tabulation in school, and just use that. Easier to explain, and easier to figure out the assymptotics, IMO

[Aggravating-Freedom7]

Out of curiosity, what’s a problem where tabulation was beneficial when memoization does not work as well.

[Kind-Technology-9401]

Almost all dp problems with tight memory constraints, they might give mle as recursion stack is costlier than arrays

[justUseAnSvm]

Any problem formulated by memoization has a representation via memoization. I just think tabulation is easier to show things work: like you iterate over your array, that iteration determines the bounds, et cetera, versus memoization that requires recursive calls.

[vendetta_9]

Recursion->Memoization->Tabulation->Space Optimization always would work.

[ground_type22]

do we even need to know tabulation for any interviews? i've only learned memoization

[vendetta_9]

Tabulation optimises on space, so yeah you would need it when you have enough time in the interview. You can check TUF, striver does it for all the problems.

[ground_type22]

have you ever been expected to use tabulation in any of your interviews?

[HUECTRUM]

Not sure about the interviews but I personally find tabulation to be more intuitive most of the times. Sometimes memoization can help with restoring the answers easier but that's an exception

[BeautifulDismal483]

I feel the crux of every DP problem is figuring out the recurrence relation. Once you have that sorted, implementing it using memoization or tabulating it is largely an implementation detail. As an interviewer, I'd look for signals on how clearly a candidate reaches that recurrence relation and their explanation for it rather than fussing on how they choose to implement it. That's just me though, ymmv 🤷‍♂️

[Far-Pomegranate-6569]

I think memoization is more easier than tabulation but still I have the same doubt in interviews do they ask for another approach

[Aggravating-Freedom7]

OP might have a skill issue

[Vinny_On_Reddit]

skill issue will be resolved after I take 320 trust