Panda Guru LogoPanda
Guru

D.E Shaw | Choose Students | DP | Top Down➡️Bottom Up | Clean CPP Code

Round 1

Questions: You are the teacher of a class and you have totalStudents students in the class. You are asked to choose chooseLimit students from your class for a competition. All your students are equally competent. Find the number of ways you can choose chooseLimit students from a class of totalStudents students.
Note: Number of ways of choosing 0 students from totalStudents is 1.

Input:

totalStudents = 3, chooseLimit = 2

Output:

3

Explanation: Ways to choose 2 students from 3 is: {1,2}, {1,3}, {2,3}.

Constraints: 1 <= totalStudents <= 200
0 <= chooseLimit <= totalStudents


Candidate's Approach

Approach 1: Using Top Down DP (Recursion To Memoization)

class TopDown { public: // O(TS*CL) & O(TS*CL) : Where TS = totalStudents, CL = chooseLimit int numWays(int totalStudents, int chooseLimit) { vector<vector<int>> dp(totalStudents + 1, vector<int>(chooseLimit + 1, -1)); return solveWithMemo(dp, totalStudents, 0, chooseLimit); } private: // O(2*TS*CL) & O(TS*CL + TS) int solveWithMemo(vector<vector<int>>& dp, int totalStudents, int student, int chooseLimit) { if(chooseLimit == 0) return 1; // Edge case when you've chosen students with specified limit then return 1 if(student == totalStudents) return 0; // Edge case when all the students are exhausted then return 0 if(dp[student][chooseLimit] != -1) return dp[student][chooseLimit]; // There are always two possibilities at each student int currSkip = solveWithMemo(dp, totalStudents, student + 1, chooseLimit); // Is to skip it int currChoose = solveWithMemo(dp, totalStudents, student + 1, chooseLimit - 1); // Is to choose it return dp[student][chooseLimit] = (currSkip + currChoose); } };

Approach 2: Using Bottom Up DP (2D + 1D Tabulation)

class BottomUp { public: // O(TS*CL) & O(TS*CL) int numWays_V1(int totalStudents, int chooseLimit) { vector<vector<int>> dp(totalStudents + 1, vector<int>(chooseLimit + 1, 0)); for(int student = 0; student <= totalStudents; ++student) dp[student][0] = 1; // Initialize the first edge case for(int student = totalStudents-1; student >= 0; --student) { for(int limit = 1; limit <= chooseLimit; ++limit) { int currSkip = dp[student + 1][limit]; int currChoose = dp[student + 1][limit - 1]; dp[student][limit] = (currSkip + currChoose); } } return dp[0][chooseLimit]; } // O(TS*CL) & O(CL) int numWays_V2(int totalStudents, int chooseLimit) { vector<int> nextRow(chooseLimit + 1, 0), idealRow(chooseLimit + 1, 0); nextRow[0] = 1; // Initialize the first edge case for(int student = totalStudents-1; student >= 0; --student) { idealRow[0] = 1; // Initialize the first edge case for(int limit = 1; limit <= chooseLimit; ++limit) { int currSkip = nextRow[limit]; int currChoose = nextRow[limit - 1]; idealRow[limit] = (currSkip + currChoose); } nextRow = idealRow; } return nextRow[chooseLimit]; } };
Interviewer's Feedback

No feedback provided.