LinkedIn interview experience Real time questions & tips from candidates to crack your interview

SDE - 1

LinkedIn
upvote
share-icon
1 rounds | 3 Coding problems

Interview preparation journey

expand-icon
Preparation
Duration: 4 months
Topics: Data Structures, Algorithms, System Design, Aptitude, OOPS
Tip
Tip

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.

Application process
Where: Campus
Eligibility: Above 7 CGPA
Resume Tip
Resume tip

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.

Interview rounds

01
Round
Medium
Online Coding Test
Duration60 minutes
Interview date26 May 2015
Coding problem3

This was a online test round where I was given 3 DSA questions to be solved in 60 minutes.

1. Count Ways To Reach The N-th Stairs

Moderate
30m average time
80% success
0/80
Asked in companies
InfosysTata Consultancy Services (TCS)Amazon

You have been given a number of stairs. Initially, you are at the 0th stair, and you need to reach the Nth stair.


Each time, you can climb either one step or two steps.


You are supposed to return the number of distinct ways you can climb from the 0th step to the Nth step.

Example :
N=3

Example

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)}.
Problem approach

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)

Try solving now

2. Optimal Strategy for a Game

Easy
15m average time
85% success
0/40
Asked in companies
GoogleIBMJP Morgan

You and your friend Ninjax are playing a game of coins. Ninjax place the 'N' number of coins in a straight line.

The rule of the game is as follows:

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. 

Ninjax is a good friend of yours and asks you to start first.

Your task is to find the maximum amount you can definitely win at the end of this game.

Note:

'N' is always even number.

Ninjax is as smart as you, so he will play so as to maximize the amount he wins.
Example 1:
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.
Example 2:
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.
Problem approach

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.

Try solving now

3. Generate all parenthesis

Moderate
30m average time
85% success
0/80
Asked in companies
InfosysFacebookGoogle

You are given an integer 'N', your task is to generate all combinations of well-formed parenthesis having ‘N’ pairs.


A parenthesis is called well-formed if it is balanced i.e. each left parenthesis has a matching right parenthesis and the matched pairs are well nested.


For Example:

For ‘N’ = 3,
All possible combinations are: 
((()))
(()())
(())()
()(())
()()()
Problem approach

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.

Try solving now

Here's your problem of the day

Solving this problem will increase your chance to get selected in this company

Skill covered: Programming

Which SQL keyword removes duplicate records from a result set?

Choose another skill to practice
Similar interview experiences
company logo
SDE - 1
3 rounds | 5 problems
Interviewed by LinkedIn
908 views
0 comments
0 upvotes
company logo
SDE - 1
3 rounds | 9 problems
Interviewed by LinkedIn
942 views
0 comments
0 upvotes
company logo
SDE - 1
2 rounds | 4 problems
Interviewed by LinkedIn
925 views
0 comments
0 upvotes
company logo
SDE - 1
2 rounds | 4 problems
Interviewed by LinkedIn
927 views
0 comments
0 upvotes
Companies with similar interview experiences
company logo
SDE - 1
1 rounds | 2 problems
Interviewed by Tata Consultancy Services (TCS)
0 views
0 comments
0 upvotes
company logo
SDE - 1
3 rounds | 4 problems
Interviewed by Tata Consultancy Services (TCS)
5992 views
0 comments
0 upvotes
company logo
SDE - 1
2 rounds | 3 problems
Interviewed by BNY Mellon
5242 views
3 comments
0 upvotes