Total 3 Rounds :
1.Online Assessment
2.F2F Interview 1
3.F2F Interview 2
Round 1 Interview:
The interview started with a brief introduction and then went for 1hr 20mins with 2 DSA questions.
Question 1: Find the first missing positive (Leetcode Hard)
https://leetcode.com/problems/first-missing-positive/
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int>&arr)
{
// We swap until the elements are in correct place, if the index and arr[index] are not same we can say that
// this the first element which is missing
int n=arr.size();
for(int i=0;i<n;i++)
{
while(arr[i]>=1 && arr[i]<=n && arr[i]!=arr[arr[i]-1])
{
swap(arr[i],arr[arr[i]-1]);
}
}
for(int i=0;i<n;i++)
{
if(arr[i]!=i+1)
{
cout<<i+1<<endl;
break;
}
}
}
int main()
{
int n;
cin>>n;
vector<int>arr(n,0);
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
solve(arr);
return 0;
}Question 2: Find the final path when the shell commands are given.
Given test case for example:
Number of commands= 7
Shell commands=> ab cd .. e . f ..
Output:
ab/e
#include <bits/stdc++.h>
using namespace std;
void solve(vector<string>&arr)
{
stack<string>st;
for(int i=0;i<arr.size();i++)
{
if(arr[i]==".." && !st.empty())
{
st.pop();
}
else if(arr[i]=="." && !st.empty()){}
else
{
st.push(arr[i]);
}
}
string ans="";
while(!st.empty())
{
ans=st.top()+"/"+ans;
st.pop();
}
ans.pop_back();
cout<<ans<<endl;
}
int main()
{
int n;
cin>>n;
vector<string>arr;
for(int i=0;i<n;i++)
{
string s;
cin>>s;
arr.push_back(s);
}
solve(arr);
return 0;
}Round 2: This was final round unfortunately I was rejected in this round. It took place for 1hour and was based around 2 DSA question's and resume and projects
Question 1: Given an sorted array find the frequency of given Key.(Optimal Solution)
// Given test case for example:
/*
Size of Array=7
Key=2
Array Elements=> 1 2 2 2 3 4 5
*/
#include <bits/stdc++.h>
using namespace std;
// Lower bound return's the first element of the given element so for K=2 it will return 5 instead of 4
int lower_bound(vector<int>&arr,int k)
{
int low=0,high=arr.size()-1;
int mid;
while(high-low>1)
{
mid=(high+low)/2;
if(arr[mid]<k)
{
low=mid+1;
}
else
{
high=mid;
}
}
if(arr[high]>=k)
{
return high;
}
if(arr[low]>=k)
{
return low;
}
return -1;
}
// Upper bound strictly return's the next element of the given element so for K=2 it will return 5 instead of 4
int upper_bound(vector<int>&arr,int k)
{
int low=0,high=arr.size()-1;
int mid;
while(high-low>1)
{
mid=(high+low)/2;
if(arr[mid]<=k)
{
low=mid+1;
}
else
{
high=mid;
}
}
if(arr[high]>k)
{
return high;
}
if(arr[low]>k)
{
return low;
}
return -1;
}
void solve(vector<int>&arr,int k)
{
int low=lower_bound(arr,k);
int high=upper_bound(arr,k)-1;
std::cout << abs(high-low) << std::endl;
}
int main()
{
int n,k;
cin>>n>>k;
vector<int>arr(n,0);
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
solve(arr,k);
return 0;
}Question 2: A variant of 2 sum, where I had to print all the pairs which had a sum equal to K
Given test case for example:
Size of Array=7
Sum=5
Array Elements=> 1 2 3 3 4 5
Thus the pairs will be (1,4) , (2,3), (3,2) , (3,2) , (4,1)#include <bits/stdc++.h>
using namespace std;
void solve(vector<int>&arr,int sum)
{
unordered_map<int,int>mp;
for(auto x:arr)
{
mp[x]++;
}
for(auto x:mp)
{
while(x.second--)
{
if(mp.find((sum-x.first))!=mp.end())
{
cout<<x.first<<" "<<sum-x.first<<endl;
}
}
}
}
int main()
{
int n,k;
cin>>n>>k;
vector<int>arr(n,0);
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
solve(arr,k);
return 0;
}The reason I might have gotten rejected is that I was unable to implement the lower and upper bound fuctions from scratch .
I had given the solution using STL and the interviewer asked me to implement both the functions and I was unable to do that.
[Note: Always make sure you know to implement all the basic STL functions like sort,upper_bound,lower_bound etc.]