Tip 1 : Must do Previously asked Interview as well as Online Test Questions.
Tip 2 : Go through all the previous interview experiences from Codestudio and Leetcode.
Tip 3 : Do at-least 2 good projects and you must know every bit of them.
Tip 1 : Have at-least 2 good projects explained in short with all important points covered.
Tip 2 : Every skill must be mentioned.
Tip 3 : Focus on skills, projects and experiences more.
This was a online test round where I was given 3 DSA questions to be solved in 60 minutes.
N=3
We can climb one step at a time i.e. {(0, 1) ,(1, 2),(2,3)} or we can climb the first two-step and then one step i.e. {(0,2),(1, 3)} or we can climb first one step and then two step i.e. {(0,1), (1,3)}.
The question can be approached using recursion. The person can reach nth stair from either (n-1)th stair or from (n-2)th stair. Hence, for each stair n, find out the number of ways to reach n-1th stair and n-2th stair and add them to give the answer for the nth stair. Therefore the expression for such an approach comes out to be : ways(n) = ways(n-1) + ways(n-2)
This is an expression for Fibonacci numbers only, where ways(n) is equal to Fibonacci(n+1).
Time Complexity: O(2^n)
The above solution can be optimised using dynamic programming. Maintain an array dp[] and fill it in bottom up manner using the relation :
Dp[i] = dp[i-1] + dp[i-2] for i>=2
Time complexity: O(N)
Auxiliary Space: O(N)
1. Each coin has a value associated with it.
2. It’s a two-player game played against an opponent with alternating turns.
3. At each turn, the player picks either the first or the last coin from the line and permanently removes it.
4. The value associated with the coin picked by the player adds up to the total amount the player wins.
'N' is always even number.
Ninjax is as smart as you, so he will play so as to maximize the amount he wins.
Let the values associated with four coins be: [9, 5, 21, 7]
Let’s say that initially, you pick 9 and Ninjax picks 7.
Then, you pick 21 and Ninjax picks 5.
So, you win a total amount of (9+21), i.e. 30.
In case you would have picked up 7 initially and Ninjax would have picked 21 (as he plays optimally).
Then, you would pick 9 and Ninjax would choose 5. So, you win a total amount of (7+9), i.e. 16, which is not the maximum you can obtain.
Thus, the maximum amount you can win is 30.
Let the values associated with four coins be: [20, 50, 5, 10]
Let’s say that initially, you pick 10 and Ninjax picks 20.
Then, you pick 50 and Ninjax picks 5.
So, you win a total amount of (10+50), i.e. 60.
In case you would have picked up 20 initially and Ninjax would have picked 50 (as he plays optimally).
Then, you would pick 10 and Ninjax would choose 5. So, you win a total amount of (20+10), i.e. 30, which is not the maximum you can obtain.
Thus, the maximum amount you can win is 60.
Using recursion: Suppose it's your turn and you are left with coins in the index range ['I', ‘J’]. You have the option to pick either ith or jth coin. Of these two options, you would select the one which maximizes your winning amount.
o If you pick the ith coin. The other player will have the option to pick ('I'+1)th or ‘J’th coin.
→ If the other player picks the ('I'+1)th coin. You can pick either end of the range ['I'+2, ‘J’].
→If the other player picks ‘J’th coin. You can pick either end of the range ['I'+1, ‘J’-1].
→ As the other player wants to maximize his amount (thereby minimizing the amount you can win). Hence, of the two ranges which you are left with (mentioned above), you can only use that range that gives us the minimum amount.
o If you pick the jth coin. The other player will have the option to pick ith or ('J'-1)th coin.
→ If the other player picks the ith coin. You can pick either end of the range ['I'+1, ‘J’-1].
→ If the other player picks ('J'-1)th coin. You can pick either end of the range ['I', ‘J’-2].
→ Similarly here, of the two ranges which you are left with (mentioned above), you can only use that range which gives us the minimum amount.
This solution can be optimized using dynamic programming.
Approach:
Suppose it's your turn and you are left with coins in the index range ['I', ‘J’] (other coins have already been picked up in previous turns). You have the option to pick ith or jth coin. Of these two options, you would select the one which maximizes your winning amount.
• If you pick the ith coin. The other player will have the option to pick ('I'+1)th or 'J'th coin.
→ If the other player picks the ('I'+1)th coin. You can pick either end of the range ['I'+2, 'J'].
→ If the other player picks 'J'th coin. You can pick either end of the range ['I'+1, 'J'-1].
→Now, as the other player wants to maximize his amount (thereby minimizing the amount you can win) hence, of the two ranges which you are left with (mentioned above), you can only use that range which gives us the minimum amount.
• If you pick the jth coin. The other player will have the option to pick ith or ('J'-1)th coin.
→ If the other player picks the ith coin. You can pick either end of the range ['I'+1, 'J'-1].
→If the other player picks (j-1)th coin. You can pick either end of the range ['I', 'J'-2].
→ Similarly here, of the two ranges which you are left with (mentioned above), you can only use that range which gives us the minimum amount.
Algorithm :
• Create a 2D table of size N*N.
• Each entry in the table stores the solution to a subproblem i.e. ‘TABLE’['I']['J'] represents the maximum amount you can win for the subarray ‘COINS’['I', 'J'] given that you start first.
• The algorithm for filling the table is as follows:
o Loop 1: For ‘LEN’ = 1 to ‘N’:
o Loop 2: For ‘I’ = 0 to ('N' - ‘LEN’):
→Let 'J' = 'I' + ‘LEN’ - 1
→If ('I'+1) < N && ('J'-1) >= 0 then, A = ‘DP’['I'+1]['J'-1], otherwise A = 0.
→If (i+2) < N then, B = ‘DP’['I'+2]['J'], otherwise B = 0.
→ If ('J'-2) >= 0 then, C = ‘DP’['I']['J'-2], otherwise C = 0.
→ Update ‘DP’['I']['J'] = max(‘COINS’['I'] + min(A, B), coins['J'] + min(A, C)).
o End Loop 2.
o End Loop 1.
• ‘DP’[0]['N'-1] stores the final answer.
For ‘N’ = 3,
All possible combinations are:
((()))
(()())
(())()
()(())
()()()
The question can be solved using a backtracking approach. Use two integers to count the remaining left parenthesis (n) and the right parenthesis (m) to be added. At each function call add a left parenthesis if n >0 and add a right parenthesis if m>n. Append the result and terminate recursive calls when both m and n are zero.
Steps :
1. Create a backtrack function that updates the current string if open_brackets are less than n or close_bracket are less than open_bracket
2. When the length of current string becomes equal to 2*n , add it to the combination result array.
Here's your problem of the day
Solving this problem will increase your chance to get selected in this company
Which SQL keyword removes duplicate records from a result set?