So I gave the on-campus Google hiring test yesterday and when I saw the 2 problems I had to solve in an hour, I was really excited since they looked doable. However, things took a turn when I actually started to think about optimizations. Anyways, here goes : ↵
↵
**Problem -1**↵
==============↵
We have an array A of N elements. We will be asked Q queries. each query is in the form of a single integer, X, and we have to tell whether there exists an index i in the array such that the **bitwise AND** of A[i] and X equals 0.↵
If such an index exists print YES, otherwise print NO.↵
↵
**Constraints** : 1<=N<=1e5,↵
1<=Q<=1e5,↵
1<=A[i]<=1e5↵
↵
↵
↵
**Problem 2**↵
=============↵
We have a binary string S of length N, and we have to find the number of substrings(that is, a contiguous range i to j) in which the frequency of 1 is strictly greater than the frequency of 0.↵
↵
**Constraints** : 1<=N<=1e6;↵
↵
I have spent a lot of time on them but could not come up with an optimal approach for either. I realize that the 2nd problem can be solved in O(NlogN) in a similar fashion in which we solve LIS in NlogN time, But other than that, I am clueless about both problems. Any help will be appreciated, Thanks!
↵
**Problem -1**↵
==============↵
We have an array A of N elements. We will be asked Q queries. each query is in the form of a single integer, X, and we have to tell whether there exists an index i in the array such that the **bitwise AND** of A[i] and X equals 0.↵
If such an index exists print YES, otherwise print NO.↵
↵
**Constraints** : 1<=N<=1e5,↵
1<=Q<=1e5,↵
1<=A[i]<=1e5↵
↵
↵
↵
**Problem 2**↵
=============↵
We have a binary string S of length N, and we have to find the number of substrings(that is, a contiguous range i to j) in which the frequency of 1 is strictly greater than the frequency of 0.↵
↵
**Constraints** : 1<=N<=1e6;↵
↵
I have spent a lot of time on them but could not come up with an optimal approach for either. I realize that the 2nd problem can be solved in O(NlogN) in a similar fashion in which we solve LIS in NlogN time, But other than that, I am clueless about both problems. Any help will be appreciated, Thanks!
