abhi4gupta's blog

By abhi4gupta, history, 4 years 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
  • +14
  • Vote: I do not like it

| Write comment?
»
4 years 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?

  • »
    »
    4 years 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.

»
4 years 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?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 years 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)

»
4 years 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.

»
4 years 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

»
4 years 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?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Counterexample: cadccbb 3

    Answer is dccb, your answer will be cdcc.

»
4 years 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.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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