SDE - Intern Intuit interview experience | prerna singh

Interview rounds

Round

Hard

Online Coding Test

Duration90 Minutes

Interview date30 Jun 2021

Coding problem3

It was an online round in the morning for 90 minutes in which 4 questions were asked .

1. Partition a set into two subsets such that the difference of subset sums is minimum.

Hard

10m average time

85% success

0/120

Asked in companies

You are given an array 'arr' containing 'n' non-negative integers.

Your task is to partition this array into two subsets such that the absolute difference between subset sums is minimum.

You just need to find the minimum absolute difference considering any valid division of the array elements.

Note:

1. Each array element should belong to exactly one of the subsets.

2. Subsets need not always be contiguous.
For example, for the array : [1, 2, 3], some of the possible divisions are 
   a) {1,2} and {3}
   b) {1,3} and {2}.

3. Subset-sum is the sum of all the elements in that subset.

Example:

Input: 'n' = 5, 'arr' = [3, 1, 5, 2, 8].

Ouput: 1

Explanation: We can partition the given array into {3, 1, 5} and {2, 8}. 
This will give us the minimum possible absolute difference i.e. (10 - 9 = 1).

Problem approach

The recursive solution is to consider each item in the given set S one by one, and for each item, there are two possibilities:

Include the current item in subset S1 and recur for the remaining items.
Include the current item from the subset S2 and recur for the remaining items.
Finally, return the minimum difference we get by including the current item in S1 and S2. When there are no items left in the set, return the absolute difference between elements of S1 and S2.

But the compiler didn't accepted the recursive solution so an optimised version were required .

Try solving now

2. Find Maximum number possible by doing at-most K swaps

Moderate

15m average time

85% success

0/80

Asked in companies

You are given an array of 'N' non-negative integers, representing the digits of a number, and an integer 'K'. Your task is to find the maximum possible number that can be made by swapping the digits of the given number at most 'K' times.

Note :

1. The input may have 0 before the most significant digit, [0,3,5,7] is a valid input and it represents number 357.
2. Digits in the number can be repeated, i.e [3, 3, 4, 4] is a valid input and it represents the number 3344.

Problem approach

I followed backtracking based approach but some test cases were giving TLE.

Try solving now

3. Maximum Score

Hard

0/120

Asked in companies

Ninja is playing a board game in which two lists of distinct numbers ‘A’ and ‘B’ arranged in a non-descending order are given. The game has certain rules and the player has to pick some numbers from the given list and the score is the sum of unique picked numbers. The rules are:

1.  Choose any list ‘A’ or ‘B’.
2.  Traverse from left to right.
3.  After picking a number, if the picked number is present in both the arrays, you are allowed to traverse to the other array.

You are given arrays,’A’ and ‘B’ of size ‘N’ and ‘M’ respectively. Your task is to find the maximum score Ninja can achieve.

Since the answer can be very large, print answer % (10^9 + 7).

For Example

If the given array are ‘A’ = [1,3,5,7,9] and  ‘B’ = [3,5,100]”.The maximum score can be achieved is 109[1+3+5+100].

Problem approach

This is exactly how I thought about the problem , explained really well here

Try solving now

Round

Easy

Video Call

Duration30 Minutes

Interview date15 Jul 2021

Coding problem1

It was in the morning . It started with a brief introduction of both of us (interviewer and me). Then he pasted an input test case and output of that on the glider platform . I had to understand what the problem does exactly to give the desired output. I told the interviewer what I could comprehend seeing the corresponding output and he agreed to it and then asked me to solve the problem and write the code for it too .

1. Decode String

Easy

0/40

Asked in companies

Ninja requests a PS5 from Santa on Christmas. Santa decides to give Ninja a brand new PS5, but he locks it in a safe and gives Ninja a string SECRETCODE. The password to open the safe is the length of the longest palindromic subsequence present in SECRETCODE.

A palindromic subsequence is a subsequence (generated by deleting some character of a given string without changing its order) which is a palindrome. For example: ‘ABBA’ is the longest palindromic subsequence for ‘CACBDBA’.

As Ninja is busy sending Christmas presents to his friends, he asks you for help. Can you help Ninja open the safe and retrieve his PS5?

Note:

‘SECRETCODE’ consists of only English uppercases.

Problem approach

After thinking for some time and coming up with few dry runs ,I realised that stack would be an appropriate choice .
I took a stack which is of type 'char'to store the input string each character.
1.Traverse the string.
2.If the char is not a ]
push it into the stack.
Else
store all elements of the stack in a string in reverse fashion until we encounter a [.
pop the top element of stack as it it [.
After that create a number string and store the frequency in reverse fashion. We use while here and not if because we can also have 2 digit or 3 digit number as frequency. Keep popping from stack.
Then convert that number string into int k.
now use a while loop until k>0 and store each char of string k number of times.

Finally , traverse through the stack and store all the characters in reverse order until stack becomes empty.

Try solving now

Round

Easy

Video Call

Duration60 Minutes

Interview date15 Jul 2021

Coding problem3

It was a mix of everything - DSA ,Core computer subjects and I was also asked about my projects .

1. Shortest Path in a Binary Matrix

Moderate

37m average time

65% success

0/80

Asked in companies

You have been given a binary matrix of size 'N' * 'M' where each element is either 0 or 1. You are also given a source and a destination cell, both of them lie within the matrix.

Your task is to find the length of the shortest path from the source cell to the destination cell only consisting of 1s. If there is no path from source to destination cell, return -1.

Note:

1. Coordinates of the cells are given in 0-based indexing.
2. You can move in 4 directions (Up, Down, Left, Right) from a cell.
3. The length of the path is the number of 1s lying in the path.
4. The source cell is always filled with 1.

For example -

1 0 1
1 1 1
1 1 1
For the given binary matrix and source cell(0,0) and destination cell(0,2). Few valid paths consisting of only 1s are

X 0 X     X 0 X 
X X X     X 1 X 
1 1 1     X X X 
The length of the shortest path is 5.

Problem approach

It's a simple BFS problem. Basically, visit all the neighboring nodes first and then keep going till all the elements are visited at least once or if you reach the end node ie (n, m).

class Solution {
public:
int shortestPathBinaryMatrix(vector>& mat) {
int m=mat.size();int n=mat[0].size();
vector>visited(m,vector(n,false));
queue>q;
//start top right 0 as source node at level=0
//push its adjacent nodes in the queue
//such that we can find the shortest path
if(mat[0][0]==1 || mat[m-1][n-1]==1)
return -1;
if(m==1 && n==1 && mat[0][0]==0)
return 1;
int dx[]={-1,-1,0,+1,+1,+1,0,-1};
int dy[]={0,+1,+1,+1,0,-1,-1,-1};
for(int i=0;i<8;i++){
q.push({dx[i],dy[i]});
}
int level=0;//initial level is zero
bool reached=false;
while(!q.empty()){
int sz=q.size();
level++;
for(int k=0;k=0 && j>=0 && i mat[i][j]=level;
visited[i][j]=true;
if(i==m-1 && j==n-1)
{
reached=true;
break;
}
for(int l=0;l<8;l++){
q.push({i+dx[l],j+dy[l]});
}
}
}
if(reached)
break;
}
return reached?level+1:-1;
}
};

Try solving now

2. Operating System Questions

What are semaphores.
What are different scheduling algorithms .
What is better Round Robin or SJF.
What is multithreading .
What is virtual memory .
What is paging .
What is deadlock and eg of its real world scenario.

Problem approach

Tip 1 : Revise OS concepts thoroughly from Gate Smashers/Knowledge Gate.
Tip 2 : Make notes which you can easily revise from few days before the interview.

3. DBMS Questions

What is normalisation .
Difference between 1NF,2NF,3NF .
Some SQL queries to write .
Different types of joins .

Problem approach

Tip 1 : You can practice SQL queries from hackerrank and leetcode.
Tip 2 : Watch DBMS playlist of Gate Smashers/Knowledge Gate

SDE - Intern

Interview preparation journey

Interview rounds

1. Partition a set into two subsets such that the difference of subset sums is minimum.

You are given an array 'arr' containing 'n' non-negative integers.

Your task is to partition this array into two subsets such that the absolute difference between subset sums is minimum.

You just need to find the minimum absolute difference considering any valid division of the array elements.

Note:

Example:

2. Find Maximum number possible by doing at-most K swaps

You are given an array of 'N' non-negative integers, representing the digits of a number, and an integer 'K'. Your task is to find the maximum possible number that can be made by swapping the digits of the given number at most 'K' times.

Note :

3. Maximum Score

Ninja is playing a board game in which two lists of distinct numbers ‘A’ and ‘B’ arranged in a non-descending order are given. The game has certain rules and the player has to pick some numbers from the given list and the score is the sum of unique picked numbers. The rules are:

You are given arrays,’A’ and ‘B’ of size ‘N’ and ‘M’ respectively. Your task is to find the maximum score Ninja can achieve.

For Example

1. Decode String

Ninja requests a PS5 from Santa on Christmas. Santa decides to give Ninja a brand new PS5, but he locks it in a safe and gives Ninja a string SECRETCODE. The password to open the safe is the length of the longest palindromic subsequence present in SECRETCODE.

A palindromic subsequence is a subsequence (generated by deleting some character of a given string without changing its order) which is a palindrome. For example: ‘ABBA’ is the longest palindromic subsequence for ‘CACBDBA’.

As Ninja is busy sending Christmas presents to his friends, he asks you for help. Can you help Ninja open the safe and retrieve his PS5?

Note:

1. Shortest Path in a Binary Matrix

You have been given a binary matrix of size 'N' * 'M' where each element is either 0 or 1. You are also given a source and a destination cell, both of them lie within the matrix.

Your task is to find the length of the shortest path from the source cell to the destination cell only consisting of 1s. If there is no path from source to destination cell, return -1.

Note:

For example -

2. Operating System Questions

3. DBMS Questions