I am looking for a job, and here I am preparing DSA again.
I am expecting 4 questions in this 90 minutes test. Roughly this should be the format:
Question 1: Array-based Questions, Searching-Sorting, Adhoc Problems
Question 2: Strings, Number Theory
Question 3: Trees or Graphs
Question 4: Dynamic Programming (covers all Recursion only questions as well)
Since there is a high chance of Dynamic Programming question for sure, I started with it.
DYNAMIC PROGRAMMING
Round 1
- I wanted to start with templates (All top-down approach i.e. memoization.)
- Fibonacci
- Knapsack (0-1 and Unbounded)
- Longest Common Subsequence (LCS)
- Longest Increasing Subsequence (LIS)
- Matrix Chain Multiplication (MCM)
- Classic DP Problems. Approach these problems without thinking that they are a variant of a template. Think of them as a standalone topic and should be solved independently. These I will prefer with top-down approach as well i.e. memoization.
- Weighted Job Scheduling
- DP Problems on Grids (Grids are easy to be solved using bottom-up approach i.e. tabulation.)
- Min cost path in a grid with 2-directional motion allowed
- Max sum submatrix in a 2D matrix
- Follow Up: Largest submatrix with sum divisible by k
- Largest submatrix with all 1s in a binary 2D matrix
Round 2
- Advanced Theory on DP (Usually optional in the first round. These are typical for competitive programming and I am skeptical companies ask such questions in interviews.)
- DP with Bitmasking
Problem Set (for my practice/test)