### abhi4gupta's blog

By abhi4gupta, history, 2 years ago,

Here is Question and my Approach of codenation hiring internship held on 1 Aug 2020 you may discuss your Approach in Comment Section to make it better.

1. find the greatest lexicographical string after erasing exactly k character from given string. (Expected time complexity O(N).)

My Approach:

it is similar to find next greter element. with every pop operation i decrease the count with one because we need to remove exactly k element. if in ans string size excced return first n-k character.

string greaterstring(int k, string s){
int n=s.size();
stack<int> st;
int cnt=k;
for(int i=0;i<n;i++){
while(!st.empty()&&s[st.top()]<s[i]&&cnt--){
st.pop();
}
st.push(i);
}
string ans;
while(!st.empty()){
ans.push_back(s[st.top()]);
st.pop();
}
reverse(ans.begin(),ans.end());
return ans.substr(0,n-k);

}

1. find min insertion to make first Array to second Array. To obtain second Array you can delete and insert Any no of element in first Array . you have to minimize the insertion. one intersting fact is that each element in second Array is distinct. expected time complexity (NlogN)

MY Approach: data structure used map and BIT tree

you can map every element of first Array with their indexes. then iterate second Array and find index of each element in map. let's say X you have to find max ele till (x-1) index in Bit tree and increment that value and put that value at index X. you noticed that there is multiple index corresponding to a single element for that you have keep indexes in decreasing order. And return max of BIT tree.

int bit[100005]={0};
int query(int n){
int ans=0;
for(; n>0 ;n -= n&-n)
ans=max(ans,bit[n]);
return ans;
}
void update(int x,int change){
for(;x<=100003;x += x&-x)
bit[x]=max(bit[x],change);
}
int getMINinsertion(vector<int> &f,vector<int> &s){
int n=f.size();
int m=s.size();
unordered_map<int,set<int,greater<int>> > mp;

for(int i=0;i<n;i++) mp[f[i]].insert(i);
for(int i=0;i<m;i++){
if(mp.count(s[i])){
for(auto it:mp[s[i]]){
int k=query(it);
update(it+1,k+1);
}
}
}

return m-query(n+3);

}

1. you have given an Array and query. in each Query there is 4 integer l r s t you have to find no of subarray in range [l,r] of size s whose bitwise and value is greater or equal than t. expected time complexity: O(N*Q*log(MAX)). may be it gives TLE for strict cases because it gives Approx 1.6*10^8 iteration. more reliable to do it in N*Q.

My Approach:

it can be solve by Sparse table easily which build complexity is NlogN and for each query take O(1) for idempotent function so (time complexity for that approach is min(N*Q,NlogN)(efficient) . but another approach is that to maintain frequency Array for every bit for each query. now traverse l to r count the subarray of size s whose bitwise and value >= t. Time Complexity for that Approach is O(N*Q*log(MAX)).

vector<int> func(vector<int> &a,vector<vector<int>> &q){
int n=a.size();
int m=q.size();
vector<int> ans;
for(int i=0;i<m;i++){
int cnt=0;
vector<int> v=q[i];
int l=v[0];
int r=v[1];
int s=v[2];
int t=v[3];
int fq[32]={0};
for(int i=l;i<l+s;i++){
for(int j=0;j<32;j++){
if(a[i]&(1<<j)) fq[j]++;
}
}
int an=0;
for(int j=0;j<32;j++){
if(fq[j]==s.size()) an+=(1<<j);
}
if(an>=t) cnt++;
for(int i=l+s;i<=r;i++){
int an=0;
for(int j=0;j<32;j++){
if(a[i-s]&(1<<j)) fq[j]--;
if(a[i]&(1<<j)) fq[j]++;
}
for(int j=0;j<32;j++){
if(fq[j]==s.size()) an+=(1<<j);
}
if(an>=t) cnt++;
}
ans.push_back(cnt);
}
return ans;
}


Thank you...

• +14

 » 2 years ago, # |   +5 Hey, how did you guys know about this test? Are there more tests to be held, and can we still apply for the intern?
•  » » 2 years ago, # ^ |   +10 I think this was On Campus Hiring Contests so only available for colleges where they visit. To know Codenation Off Campus Hiring Contests , you can follow their page on Facebook.
 » 2 years ago, # |   0 Hi there, Are you sure about the expected time complex. of 3rd question? I have used segment tree(build-n*log(n) and Query-Q*N*log(n) ) instead of sparse table about But it only passed 7-8 test cases. Does your code passes all testcases?
•  » » 2 years ago, # ^ |   0 sorry i Correct it..
•  » » 2 years ago, # ^ |   0 that was my Approach in Contest..
 » 2 years ago, # |   0 You can watch out this: https://www.youtube.com/watch?v=56B0HkJfx38
 » 2 years ago, # |   0 Auto comment: topic has been updated by abhi4gupta (previous revision, new revision, compare).
 » 2 years ago, # |   +10 Second question can be done in more simple way . Map second array according to it's index from 1 to N . Now iterate over 1st array , elements which are not present in second array can be simply ignored (as they count in insertions ) while other which are present in second array , replace those numbers with the corresponding mapped value . Now simply find LIS of the new array formed, which can be done in nlogn . overall complexity O(NlogN)
•  » » 2 years ago, # ^ |   0 yeah that is correct.. And that is the formal way to do that but using BIT Tree is my favourite. it does not change time Complexity .
•  » » 2 years ago, # ^ |   0 Much simpler approach.
 » 2 years ago, # |   0 How you guys get to know about these, as it is not updated in the Codenation site or Facebook page. If there is any group where we can get this information please share it, so that everybody will be benefitted.
 » 2 years ago, # |   +18 Please don't get me wrong but I think you should first confirm from your college placement policy about posting any information related to companies on any media,platform. Bczz one of student of our college get strict warning by just posting small comment about which company visited college.But if it is off campus or your college policy allow then no problem. BTW nice sols.
 » 2 years ago, # |   0 Auto comment: topic has been updated by abhi4gupta (previous revision, new revision, compare).
 » 2 years ago, # |   +6 I made a Hindi video editorial of all 3 problems from the test. You can find it here https://youtu.be/56B0HkJfx38
 » 2 years ago, # |   0 In first one, we can create an array for keeping count of all 26 characters and then delete k characters from the start (starting from 'a'). Is this approach correct?
•  » » 2 years ago, # ^ |   0 Counterexample: cadccbb 3Answer is dccb, your answer will be cdcc.
 » 2 years ago, # | ← Rev. 2 →   0 I think in the 1 question you have written another cnt-- in the while loop which is giving wrong answer. Is it intentional or a mistake... please clarify. while(!st.empty() && s[st.top()]
•  » » 2 years ago, # ^ |   0 it was by mistake. I fixed it. btw thank you for pointing out.
 » 2 years ago, # |   0 Can someone please tell me that whether this test was for SDE-1 Role or SDE Intern? Asking this because it was notified for SDE-1 In our campus and not for intern.
•  » » 2 years ago, # ^ |   0 abhi4gupta can u plz confirm this?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Test was Same for FTE and Internship.
 » 2 years ago, # |   0 Can someone explain solution 2 in a lucid way? I know BIT as RSQ (summation in invertible operation). How max (non-invertible) can be used in a BIT? How bit[n] is giving LIS?
 » 2 years ago, # |   0 I think in the first problem you forgot to write a condition that count > 0 in the while loop
 » 6 months ago, # | ← Rev. 3 →   0 I think first Question can also be solved by using list in c++. Same like we do in Sliding Window. Please let me know if I am wrong at some point. string ans; list l; int i = 0, n = s.length(); while(i=k){ ans.puhs_back(s[l.front()]; l.pop_front(); } i++; } return ans.substr(0, n-k); 
 » 6 weeks ago, # |   0 Thanks for sharing this problem, it looks standard but is a bit hard.$O(n)$ solution: https://ideone.com/sOowFL$O(n \log n)$ solution using max char segment tree: https://ideone.com/XriSwK
 » 6 weeks ago, # |   0 SECOND QUESTION Can we just find the longest common subsequences (l) and the answer becomes MinInsertion = l-(length of second array)