Google's Online Challenge - Coding - Intern Questions approach help

Today i wrote Google’s Online Challenge - Coding - Intern challenge. As contest is ended i’m sharing questions here. Please suggest your approaches to solve these questions.

Thanks in advance :upside_down_face:

9 Likes

hey, there will be future rounds of those who werent called in today. Pls dont give away questions like this!

1 Like

how to apply ? can you share the details

Google conducts on Hackerearth!! Weird!!

5 Likes

Applications are now closed.

1 Like

There will be different questions. So, I don’t think it’s a problem.

2 Likes

Ok

I don’t know the excat approach, but we should try to maximize the sum to the highest number of form 2^i-1, because this have maximum 1’s, because OR is a kind of summation in binary, for example (3,4) and (5,2) in sample case has sum 7 which has 3 0’s in it. If that type of sum is not possible we can try to make the sum equal to the nearest highest power of 2 that we can get from taking 1 or more elements. for example if sum 7 is not possible we can make 5 or 6 as sum which is greater then 3 ( 2^2-1), because both of them has same number of 1’s. If someone could verify this solution, then please reply weather it’s correct or not.

1 Like

FIrst problem was pretty standard, can be solved by dfs and maintaing the ancestors nodes, although i got TLE in one of the subtasks.

The second problem was very interesting though, the max or value will definitely be the ors of all the array elements, now to choose the smallest subset, i couldn`t think of any good approach other than the testing all subsets, later in gfg i saw the same problem but there it is solved just like the subset sum problem with complexity of n^2 which i think will not fit here due to the value beign of order 10^5. How did you guys solve it ??

2 Likes

Yeah I thought so too because they have their specifiec interview site too other than competitive sites.

1 Like

Oh god missed a great opportunity, could you share the procedure of applying, since I tried to Google but couldn’t find anything related to it and is there a way of getting notified about such events in the future. My college isn’t even aware about this, they want us to learn LaTeX and outdated syllabus FFS , feel like crying now : - (

go to careers section of whatever company you like and there you can create account and get notified about opportunities.

I guess, integer distribution can be solved using dp and bitmasking.

Integer distribution can be solved by dp and Bit manipulation.
But I have dought in first question . I found a post whether the solution is greedy not passing all test cases …

First will not pass with greedy, with two state dp you will get tle, only solution afaik is using fft.

2 Likes

The question wasn’t solvable with the given constraints … it was a variation of subset cover which is NP hard … I geuss you should raise a ticket to google to notify them of the same as many of us have also done.

Just btw : Due to weak test cases … just checking subsets of size 1 , 2 , 3 gives AC … which is another fallacy at google’s end

9 Likes

Do you have any idea how many questions do we need to solve to get round 1 clear?

How to check for subset of size 3?

1 Like

Careful with the chosen words. Anyways its solvable under given constraints.
https://codeforces.com/blog/entry/76177#comment-606407

1 Like

Would you mind elaborating on the explanation there or pointing to the core concepts being used. Also where does binary lifting come into the picture in this?

1 Like