Google Online challenge -Internship 2021( Today's round questions)

Hii guys today I took part in Google Online Challege for summer internship 2021 . The challenge was invitational . I got invite for it last week . I am sharing the questions for practise purpose of others . Enjoy and Share your answers on comment sections.

Constraints of Q1:-
1<=t<=100
1<=N<=100000
1<=starting node,ending node<N
1<=weight of node<=1e9


Constraints of Q2:-
1<=t<=10
1<=N<=100000
1<=C<=1e15
1<=A[i]<=1e9
1<=B[i]<=1e9

3 Likes

Question 1 is on net ,( hackerrank) , dp on tree.

Also how many u solved?

2 Likes

partially solved both . For the second question I want to see efficient approach( something
like O(N log N) ) . I have seen similar type of question in past Hackerearth contest .

Question 1 as said by @ssrivastava990 is available on hackerrank and you might find it on codechef/codeforces also.
In question 2, for each index i, we can do a binary search on K, using sparse table and prefix array you can calculate the value of objective function in O(1) time, therefore total time complexity would be O(N*log(N)).

3 Likes

Thanks buddy but still I have a doubt on 2nd one . I got that we can use prefix sum to get the second part of equation in O(1). But finding the subarray of K and then the maximum value of it using Binary search I didn’t fully got it . Can you code it with comments . It would be very helpful.

ans = 0
for i in range(1, n):
      start = i, end = n, val = i - 1
      while(start <= end):
           mid = (start + end)/2
           cost = max(B[i],.....B[mid]) + (mid-i+1)*(prefix[mid] - prefix[i-1])
           if(cost <= c):
              val = mid, start = mid + 1
           else:
              end = mid - 1
      ans = max(ans, val - i + 1)
return ans

Please note that to find max(B[i],.....B[mid]), you need to use sparse table O(1) approach.

3 Likes

Oh thanks mate I didn’t knew about sparse table can be used to find the max in O(1) time . My bad.

How to solve this question?? The best i could come up with was to emulate the process repeatedly by selecting k most frequent elements using a multiset.

2 Likes
1 Like

One of my friend sent me this problem, wasn’t able to solve, @everule1 @ssjgz @carre could you please give some hints for this?? (1 \leq k \leq 10^5)
Thanks

2 Likes

I can not see the constraint for k

could this work?:

  • sort the elements by c[i] value (non-decreasing)

  • then:

     for i=0 to n-k:
        add(c[i])
        substract c[i] for k-1 elements greater than i  (segment tree to do this)

I got the same problem. I guess i passed some test cases using basic permutations and combinations ig. It was like - 1. nCk ways to select k diff groups 2. find num of ways to select each group. 3 multiply 1 and 2

1 \leq k \leq 10^5

I edited the post, could that approach work?

Taking the sample:
N = 4, K = 2, c = [7, 7, 8, 17]
Then the answer we will get from your algo is 7 + 8 = 15(if I understood correctly). But answer is 19.

That algorithm does give 19, and I can show it to be optimal for k=2.

It is in fact min(2*mx, 2*(sum-mx)) for k=2.

How?? Please explain…

Look up stoned game on cf.

1 Like

I am Assuming mx is maximum element, assume only 2 elements in array [1, 100] and K = 2, the best you can get is only 1 group.

1 Like

N=6, K = 4
2 3 4 7 9 9 13
Ans is 11.