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

23

were can i get notification of such google or any other companies online coding challenges rounds??
plzz share the details with us :pray:

24

Be active on LinkedIn or forums like discuss.

25

I was able to get both question accepted
these were my questions
if someone solved both and is contacted for interview plz share with me here

also i would like to know about the difficulty of questions so please share how many you were able to solve

Thanks…

Q1
Q12736×1495 355 KB
Q2
Q22736×1504 347 KB

1 Like
26

The number of ways to divide n objects in n/2 pairs is = n!/(2^(n/2)(n/2)!)
which for n=20 comes out to be around 6 10^8;
Wont it give TLE.

27

Yeah that’s brute force, I knew and it would be around 6*10^8, so it should give TLE…

28

I didn’t give the test but these problems are very standard. The first one is O(T*N*100) using dfs+dp and second one can be solved by keeping which index is at the starting position.

29

For the smallest subset problem you could perform dp. You can use Kadane’s algorithm to solve the problem.

30

I got the 2nd problem… it was nice

31

I got the second question as yours… My first question was different… I solved both of them in about 25 minutes… If you get a call back from Google… plz share here…
Thank you

1 Like
32

Can you please share your approach for 2nd one?

33

Could you share some more insights on your approach and also do u know about the " binary lifting" approach that people are talking about? I do not see how that can be applied here.

34

first one can be solved by dsu on trees also

35

Will there be another round for candidates, as I didn’t receive the test link but I had applied.

38

Try to use dp, dp[i] = Math.max(arr[i], dp[i-1]|arr[i]), and if dp[i] is greater than or equal to dp[i-1], the maxsizesubarr[i] = 1, else maxsizesubarr[i] = 1+maxsizesubarr[i-1]. Take it as a hint and try to solve.

If I am wrong, feel free to correct me.

39

I don’t think the dp recurrence would be this simple for this problem. Ive seen posts discussing FFT’s and repeated convolutions to solve this problem

1 Like
40

Look I have already given you an approach… many people has many solutions… but google won’t give that hard like FFT in their interview. Basic DP approach would work.

The proof is simple at any given index, OR value will always be less or equal to the number of bits in the maximum value in the array.

41

what will be your algorithms output for the array [1,2,4,6] . Please mention dp values at each index

42

First one is done by keeping a position array of size 100 and passing it down the tree in O(n*100) and for second one, I guess keeping an offset variable would be enough. Each time there’s a left rotate or right rotate, the offset inc/dec and to access a positon we do (pos+offset)%(size of array).

I have my test on 22nd, Hope I’m able to do both

2 Likes
43

What was your approach for 1st one ?? Can you share your logic??

44

Can you elaborate your first approach?