randomx_123's blog

By randomx_123, history, 3 years ago, In English

I have been using the extension "CppFastOlympicCoding" on sublime text for quite some time now. Today, I was trying to set up a new build system on sublime text so that I can get the output in a separate file (since we have Google Hashcode today). I referred to This video.

After successfully doing this, now when I press Cntrl + B on my mac, it just gets stuck on 'Compiling'. I have tried to uninstall and install again, to no help. Does anyone have a fix for this? any help will be much appreciated.

Screenshot for reference :

Full text and comments »

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

By randomx_123, history, 3 years ago, In English

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!

Full text and comments »

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