Would coming up with a top-down approach be enough for a DP problem in a technical interview?

Question

When I come up with a solution to an unfamiliar DP problem, I usually start with a decision tree, identify its subproblems, and draft a brute force approach that can easily be memoized, making it a top-down approach.

Since the time complexity for top-down and bottom-up is in the same magnitude, would most interviewers be satisfied if I stop there?

Rahul Pandey · Accepted Answer

It's really hard to say. This will depend on the interviewer and how much time is left in the interview.

Keep in mind that getting the correct time and space complexity is only partially what is being tested in an interview. Your ability to explain the code, the tradeoffs to various approaches, and your communication ability matters as much (or more). Alex talks about this in the Ace Your Tech Interview course: Data Structures And Algorithms (DSA).

Would coming up with a top-down approach be enough for a DP problem in a technical interview?

Discussion