Tip 1 : Prepare all the topics by solving adequate amount of problems
Tip 2 : Give mock interviews
Tip 3 : Work on soft skills
Tip 1 : Should have an idea about software engineering concepts like SDLC,Scrum.
Tip 2 : Try to solve problems in given time with efficient approach
It was 100 minutes round, it had 3 Coding problems
Note that the given operation will be performed only 'N'-1 times, where 'N' is the size of the given array.
Traverse in reverse order in the given array and keep maintaining the increasing property. If any element is smaller than the maximum of existing elements till that index then, we need to make some decrement operation on that maximum element so that it also follows the increasing property from back traversal and add the required operation in the answer.
3,5 and 5,3 are not distinct combinations.
USING DP -
int dp[1001][1001];
const int mod=1e9+7;
int solve(int a[],int n,int N,int W){
if(W==0)
return 1;
if(n==0 || W<0)
return 0;
if(dp[n][W]!=-1)
return dp[n][W];
if(a[n-1]<=W)
return dp[n][W]=(solve(a,n-1,N,W)%mod+solve(a,N,N,W-a[n-1])%mod)%mod;
return dp[n][W]=solve(a,n-1,n,W)%mod;
}
int countWays(int a[], int n, int W) {
//code here.
memset(dp,-1,sizeof(dp));
return solve(a,n,n,W);
}
bool possibleBipartition(int n, vector>& dislikes) {
vector color(n+1,0);
vector adj[n+1];
for(int i=0;i q;
q.push(i);
while(!q.empty()){
int node=q.front();
q.pop();
for(int child:adj[node]){
if(color[child]==color[node])return false;
if(!color[child]){
q.push(child);
color[child]=-1*color[node];
}
}
}
}
}
return true;
}
It was conducted in morning at 11am. Interviewer asked question related to DSA, projects mentioned in resume and some software engineering concepts like SDLC, Scrum, Software Testing.
1. The grid has 0-based indexing.
2. A rotten orange can affect the adjacent oranges 4 directionally i.e. Up, Down, Left, Right.
Create a visited grid to store the state of the cell (fresh, rotten, or empty).
Initialize a queue to store the rotten oranges and count the number of fresh oranges.
Check if there are no fresh oranges, return 0, or if there are no rotten oranges, return -1.
Loop while the queue is not empty.
a. Store the size of the queue.
b. Loop through the size of the queue.
i. Get the front cell of the queue.
ii. Check all four directions of the cell to see if there are any fresh oranges.
iii. If there is a fresh orange, change its state to rotten and decrement the count of fresh oranges, and push the cell into the queue.
c. Increment the minutes.
If there are no fresh oranges, return the minutes.
If there are still fresh oranges, return -1.
We can solve this problem using Array + Backtracking.
void solve(vector &ans, int n , int open , int close,string output){
if(output.length() == 2*n){
ans.push_back(output);
return;
}
// open
if(open generateParenthesis(int n) {
vector ans;
solve(ans,n,0,0,"");
return ans;
}
It was 2nd and final interview, it was based on problem solving along with system design and computer science fundamentals.
Elevator System Design-
The interviewer asked me to design functions that should be used for designing an elevator. He just asked for the normal working not to go in very deep as time restriction was there. He was expecting me to provide the Data Structure that would be best suited, different classes & relationships between them, etc.
Tip 1 : This is a OO design question
Tip 2 : Think in terms of classes and objects
Tip 3 : Try to establish relation between objects and methods
‘N’ = 4, ‘K’ = 2
‘ARR’ = [1, 1, 2, 3]
There are ‘3’ subarrays with ‘2’ distinct elements, which are as follows: [1, 2], [2, 3], [1, 1, 2].
Thus, you should return ‘3’ as the answer.
To directly count the subarrays with exactly K different integers is hard but to find the count of subarrays with at most K distinct integers is easy. So the idea is to find the count of subarrays with at most K different integers, let it be C(K), and the count of subarrays with at most (K – 1) Different integers, let it be C(K – 1) and finally take their difference, C(K) – C(K – 1) which is the required answer.
Count of subarrays with at most K different elements can be easily calculated through the sliding window technique. The idea is to keep expanding the right boundary of the window till the count of distinct elements in the window is less than or equal to K, and when the count of distinct elements inside the window becomes more than K, start shrinking the window from the left till the count becomes less than or equal to K. Also for every expansion, keep counting the subarrays as right – left + 1 where right and left are the boundaries of the current window.
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?