abhi4gupta's blog

By abhi4gupta, history, 32 hours ago, In English,

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

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
32 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

Hey, how did you guys know about this test? Are there more tests to be held, and can we still apply for the intern?

  • »
    »
    29 hours ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

»
32 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
32 hours ago, # |
  Vote: I like it 0 Vote: I do not like it
»
32 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by abhi4gupta (previous revision, new revision, compare).

»
31 hour(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

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)

  • »
    »
    30 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

  • »
    »
    26 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Much simpler approach.

»
30 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
30 hours ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

»
30 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by abhi4gupta (previous revision, new revision, compare).

»
29 hours ago, # |
  Vote: I like it +6 Vote: I do not like it

I made a Hindi video editorial of all 3 problems from the test. You can find it here https://youtu.be/56B0HkJfx38

»
28 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    28 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Counterexample: cadccbb 3

    Answer is dccb, your answer will be cdcc.

»
26 hours ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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()]<s[i] && cnt--)
{
st.pop();
// cnt--;
}

Thanks for the codes btw...

  • »
    »
    24 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it was by mistake. I fixed it. btw thank you for pointing out.

»
23 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.