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();↵
cnt--;↵
}↵
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);↵
↵
}↵
~~~~~↵
↵
↵
↵
2. 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);↵
}↵
string 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 query(n+3);↵
↵
}↵
~~~~~↵
↵
3. 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(n))↵
↵
↵
My Approach:↵
↵
it can be solve by Sparse table easily which build complexity is NlogNMAX)). 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)). ↵
↵
~~~~~↵
string 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...↵
↵
↵
↵
↵
↵
↵
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();↵
cnt--;↵
}↵
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);↵
↵
}↵
~~~~~↵
↵
↵
↵
2. 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);↵
}↵
string 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 query(n+3);↵
↵
}↵
~~~~~↵
↵
3. 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(
↵
↵
My Approach:↵
↵
it can be solve by Sparse table easily which build complexity is NlogN
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)). ↵
↵
~~~~~↵
string 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...↵
↵
↵
↵
↵
↵
