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);

}

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);
}
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 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)).

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...